Uninformed search Python实现【译】

译自 Uninformed search algorithms in Python 版权所有,如需转载,请联系译者

图的搜索可以分为uninformed搜索和informed搜索,两者的区别是前者是的搜索是盲目的,它不知道目标节点在哪,而后者是启发式的搜索。

主要的uninformed 搜索分为以下三类:

  • 深度优先搜索(DFS)
  • 广度优先搜索(BFS)
  • 一致代价搜索(UCS)

创建图

使用邻接矩阵的形式创建图,为简便起见,这里省去节点的其他信息,直接使用一个字典表示,key表示节点,value表示邻接节点:

small_graph = {
    'A': ['B', 'C'],
    'B': ['D', 'A'],
    'C': ['A'],
    'D': ['B']
}

深度优先搜索

深度优先搜索会优先检索第一个邻接节点,然后重复这个过程,直到到达分支的底部,然后回溯。DFS可以通过递归实现,也可以通过递归实现。

具体实现需要保存已经访问的节点,同时判断边缘条件:

def dfs(graph, start, goal):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)

            if node == goal:
                return
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

广度优先搜索

实际上,只需要将上面算法中的stack改为queue,即可实现广度优先搜索。深度优先搜索总是会展开最新的节点,而广度优先搜索总是展开最老的节点,这就是他们为什么一个使用栈,一个使用队列的原因。

from collections import deque

def bfs(graph, start, goal):
    visited = set()
    queue = [start]

    while queue:
        node = queue.pop()
        if node not in visited:
            visited.add(node)

            if node == goal:
                return
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.appendleft(neighbor)

一致代价搜索(UCS)

该算法主要针对的是加权图,加权图每条边都有一个权值,权值低的边优先遍历,首先,我们创建一个加权图类:

class Graph:
    def __init__(self):
        self.edges = {}
        self.weights = {}

    def neighbors(self, node):
        return self.edges[node]

    def get_cost(self, from_node, to_node):
        return self.weights[(from_node + to_node)]

UCS跟广度优先搜索类似,也使用一个queue实现,但是使用的是加权队列

from queue import PriorityQueue

当每条边的cost相同时,UCS实际上就是BFS。

def ucs(graph, start, goal):
    visited = set()
    queue = PriorityQueue()
    queue.put((0, start))

    while queue:
        cost, node = queue.get()
        if node not in visited:
            visited.add(node)

            if node == goal:
                return
            for i in graph.neighbors(node):
                if i not in visited:
                    total_cost = cost + graph.get_cost(node, i)
                    queue.put((total_cost, i))

总结

UCS会检索一条权重之和最小的路径,而BFS会检索出一条边最少的路径。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

搜索(8)

18640
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

459100
来自专栏禹都一只猫博客

Python科学计算:在Numpy的边缘试探(入门学习)

22580
来自专栏数据结构与算法

P1008 三连击

题目背景 本题为提交答案题,您可以写程序或手算在本机上算出答案后,直接提交答案文本,也可提交答案生成程序。 题目描述 将1,2,…,9共9个数分成三组,分别组成...

43690
来自专栏数据结构与算法

1265. [NOIP2012] 同余方程

1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

34760
来自专栏尾尾部落

[LeetCode]Palindrome Number回文

链接:https://leetcode.com/problems/palindrome-number/#/description 难度:Easy 题目:De...

13220
来自专栏小樱的经验随笔

浅谈String模块ascii_letters和digits

本文介绍string模块ascii_letters和digits方法,其中ascii_letters是生成所有字母,从a-z和A-Z,digits是生成所有数字...

46780
来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

34840
来自专栏owent

HDU HDOJ 3398 String 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3398

8330
来自专栏V站

Python科学计算:在Numpy的边缘试探(入门学习)

21960

扫码关注云+社区

领取腾讯云代金券