不会飞的章鱼

熟能生巧,勤能补拙;念念不忘,必有回响。

算法训练营-高级搜索

剪枝的实现和特性

初级搜索

  • 1,朴素搜索:暴力搜索;
  • 2,优化方式:不重复(fibonacci)、剪枝(生成括号问题);
  • 3,搜索方向:深度优先搜索、广度优先搜索、双向搜索、启发式搜索。

双向BFS的实现、特性

单向BFS

变形:

双向BFS

启发式搜索的实现、特性 - Heuristc Search(A*)

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
# Python
def AstarSearch(graph, start, end):
pq = collections.priority_queue() # 优先级 —> 估价函数
pq.append([start]) 
visited.add(start)
while pq: 
node = pq.pop() # can we add more intelligence here ?
visited.add(node)
process(node) 
nodes = generate_related_nodes(node)   
unvisited = [node for node in nodes if node not in visited]
pq.push(unvisited)

估价函数

启发式搜索:h(n),它用来评价哪些结点最有希望的是一个我们要找的结点,h(n)会返回一个非负实数,也可以认为是从结点n的目标结点路径的估计成本。
启发式搜索是一种告知搜索方向的方法。它提供了一种明智的方法来猜测哪个邻居结点会导向一个目标。

题目

双向BFS

启发式搜索

参考链接

AlphaZero Explained
棋类复杂度
A*代码模板
相似度测量方法
二进制矩阵中的最短路径的 A* 解法
8 puzzles 解法比较

------ 本文结束------
如果本篇文章对你有帮助,可以给作者加个鸡腿~(*^__^*),感谢鼓励与支持!