无告知搜索算法（Python）

无告知搜索（Uninformed Search）

无告知搜索算法在搜索过程中不使用除了问题定义之外的任何附加信息。它们仅根据节点扩展的顺序来区分。常见的无告知搜索算法包括：

1. 深度优先搜索（Depth-First Search, DFS）
   • 从根节点开始，尽可能深地搜索树的分支。
   • 使用栈存储待访问的节点。
   • 深入探索节点的子树，直到没有节点可以访问，然后回溯。
2. 广度优先搜索（Breadth-First Search, BFS）
   • 从根节点开始，逐层遍历所有节点，直到找到目标节点。
   • 使用队列存储待访问的节点。
   • 保证找到的第一个解是距离起点最近的解，但不一定是最优解。
3. 一致代价搜索（Uniform-Cost Search, UCS）
   • 在图中搜索时，总是扩展代价最低的节点。
   • 如果图中的边的代价相同，找到的解将是最优的。
4. 迭代加深搜索（Iterative Deepening Search, IDS）
   • DFS的改进版本，通过逐渐增加搜索深度来平衡深度优先和广度优先搜索的优缺点。
   • 以较低的空间复杂度找到最优解。

这些算法的主要区别在于它们如何遍历搜索空间以及它们对解的最优性的保证。无告知搜索算法通常更容易实现，但可能不如有告知搜索算法高效，尤其是在解空间较大的情况下。

代码实现

下面使用python来实现上面的代码。

首先我们要试验搜索算法，显然需要一个图结构，来让我们进行遍历搜索。

深度优先搜索和广度优先搜索

图结构

图的结构原理：字典。
其中的键值对，键为节点，对应的值为该节点所相连的节点列表。
如下图创建的图，所需代码如下。
（本文不考虑路径权值）
（目前定义成有向图还是无向图不影响我们的学习）

为了方便查看图结构，还创建了一个展示的函数。结果如下

# 首先创建和定义图
# 图的原理：图是一个字典，然其中的键是节点，对应的值是列表，用列表来存放这个节点相接的节点
class Graph :def __init__(self) :self.graph = {}def add_path(self, start, terminal) :# 如果已有开始节点，则将terminal添加到其邻接链表里if start in self.graph :self.graph[start].append(terminal)else :self.graph[start] = [terminal]def show(self) :print("图的结构如下：")for node in self.graph :print(node, end=": [")neighbours = self.graph.get(node, [])for neighbour in neighbours :print("'" + neighbour + "'", end=" ")print("]")# self是一个指向对象的引用。
# 在python中，每当定义一个类的方法时，通常需要在方法的第一个参数中使用self来引用类的一个实例，这样就可以访问类的属性和方法了。
# self.graph = {} 在Graph类的实例中创建了一个名为graph的属性，初始化为一个空字典，将用来存储图的数据。# 图结构的初始化
g = Graph()
g.__init__()
# 往图中添加节点
g.add_path('0','1')
g.add_path('0','2')
g.add_path('1','3')
g.add_path('1','4')
g.add_path('2','5')
g.add_path('2','6')
g.add_path('5','6')
g.add_path('3','7')
g.add_path('4','7')
# 展示图
g.show()

接下来分别实现深度优先搜索和广度优先搜索：

from collections import deque# 首先创建和定义图
# 图的原理：图是一个字典，然其中的键是节点，对应的值是列表，用列表来存放这个节点相接的节点
class Graph :def __init__(self) :self.graph = {}
# 图的插入函数和展示函数
...     # self是一个指向对象的引用。
# 在python中，每当定义一个类的方法时，通常需要在方法的第一个参数中使用self来引用类的一个实例，这样就可以访问类的属性和方法了。
# self.graph = {} 在Graph类的实例中创建了一个名为graph的属性，初始化为一个空字典，将用来存储图的数据。# 深度优先搜索，Depth First Search，即按着一条路径一直遍历到底，难点为判读节点是否已经遍历
# 创建一个集合来记录已经访问的节点。
# 这里深层实际是用递归的系统栈来模拟栈存储数据def dfs(self, start, visited=None) :if visited is None :visited = set()visited.add(start)print(start, end=' ')for neighbour in self.graph.get(start, []) :if neighbour not in visited :self.dfs(neighbour, visited)return visited# 广度优先搜索，Breadth First Search，即先将节点的所有相连节点遍历完，再回溯遍历未遍历的下一层的节点。
# 创建一个队列来存储带访问的节点
# 遍历队列，若该节点未访问过，则加入到列表中，并将节点的邻接矩阵加入队列def bfs(self, start) :# 创建一个双端队列存储待访问的节点，并将开始节点放进去queue = deque([start]);# 创建一个集合来记录已经访问的节点visited = set([start]);let = []while queue :# 取出队首的节点current = queue.popleft()let.append(current)for neighbour in self.graph.get(current, []) :if neighbour not in visited:queue.append(neighbour)visited.add(neighbour)for i in let:print(i, end=" ")# 图结构的初始化
...print("深度优先搜索（从节点 '0' 开始）:")
g.dfs('0')
print()
print("广度优先搜索（从节点 '0' 开始）:")
g.bfs('0')

结果如上，可以看到还是正确的。

一致代价搜索

不同于深度优先搜索和广度优先搜索，一致代价搜索Uniform Cost Search, UCS虽然是从BFS的基础上拓展而来，但是思想上有较大的区别。
深度优先搜索和广度优先搜索是从面临节点的路径选择不同，一个是沿着一条路一直都下去，一个是一层一层搜索。而一致代价搜索，是旨在寻找从初始状态到目标状态的全局最优解，即到目标的代价最小的路径。
一致代价搜索有下面几种特性：

1. 全局最优：UCS旨在寻找从初始状态到目标状态的全局最优解，即代价最小的路径。它通过维护一个优先级队列来确保总是首先扩展代价最小的节点。
2. 非负代价：UCS假设所有边的代价都是非负的，这保证了一旦找到一条路径，这条路径就是最优的。
3. 路径代价：UCS考虑的是到达每个节点的完整路径代价，而不仅仅是下一步的代价。
4. 回溯：当目标状态被扩展时，UCS会回溯以构建从初始状态到目标状态的最低代价路径。

一致代价搜索的图结构代码差别不大，不过再记录路径时需添加权值，毕竟一致代价搜索算法的目标就是权值最优：

代码实现如下：

import heapqclass Graph :def __init__(self):self.graph = {}def add_edge(self, start, terminal, cost) :# 添加节点if start not in self.graph :self.graph[start] = []if terminal not in self.graph :self.graph[terminal] = []# 往开始节点的键中添加终节点和路径权值self.graph[start].append((terminal, cost))# 获取该节点的邻居以及对应路径权值def get_neighbours(self, start) :return self.graph.get(start, [])def print_graph(self):for node in self.graph:print(f"{node} -> {[node_v for node_v, _ in self.graph[node]]}")# 在Python中，f或F前缀用于创建格式化字符串字面量，也称为f-string（Python 3.6+）。这是一种新的字符串格式化机制，它允许你直接在字符串中嵌入表达式。def ucs(graph, start, goal) :# 使用堆来存储优先级队列，优先级队列中的元素为 (路径代价, 节点)priority_queue = []# 首先将开始节点加入队列中，并且因为是起点所以代价为0heapq.heappush(priority_queue, (0, start))# 记录到达每个节点的最小代价cost_so_far = {start:0}while priority_queue :# 循环取出当前代价最小的节点，直到找到终点current_cost, current_node = heapq.heappop(priority_queue)# 如果找到了终点，则返回路径代价if current_node == goal : return current_cost# 若没找到，遍历邻居节点for neighbour, edge_cost in graph.get_neighbours(current_node) :new_cost = current_cost + edge_cost# 如果找到更小的代价，更新代价并将其加入优先级队列,或者找到新路径if neighbour not in cost_so_far or new_cost < cost_so_far[neighbour] :cost_so_far[neighbour] = new_costheapq.heappush(priority_queue, (new_cost, neighbour))# 没有找到路径，则返回Nonereturn None# 创建图并添加边
graph = Graph()
graph.add_edge('A', 'B', 1)
graph.add_edge('B', 'C', 2)
graph.add_edge('A', 'C', 4)
graph.add_edge('C', 'D', 1)
graph.print_graph()
# 执行一致代价搜索
start_node = 'A'
goal_node = 'D'
cost = ucs(graph, start_node, goal_node)
print(f"The cost to reach {goal_node} from {start_node} is {cost}")

这里发现一致代价搜索算法跟我之前做的Kruskal算法博客以及Prim算法博客有差不多的思想，不过是使用C语言与邻接矩阵表示图，有兴趣的可以去看看。

但是UCS是基于BFS拓展的搜索算法，而Prim算法和KrusKal算法是寻求生成最小生成树的算法，两者的目的不同。

迭代加深搜索（Iterative Deepening Search, IDS）

接下来讲讲迭代加深搜索。

迭代加深搜索的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 d，当 d 达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度加一，重新从根开始。（转载于OI Wiki博客，里面对算法的讲解很好）

也就是说在DFS的函数参数中，加了一个递归深度，如果这个深度到达一定的限制，则会直接返回，不进行操作。
那么基于DFS的代码应该修改为：

    def dfs(self, start, visited=None, depth) :# 这里的limit应该为全局变量，或直接以参数形式if depth > limit :return if visited is None :visited = set()visited.add(start)print(start, end=' ')for neighbour in self.graph.get(start, []) :if neighbour not in visited :self.dfs(neighbour, visited)return visited