算法训练营-高级搜索

剪枝的实现和特性

初级搜索

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

双向BFS的实现、特性

单向BFS

变形：

双向BFS

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

代码模板

# 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

• https://leetcode-cn.com/problems/word-ladder/
• https://leetcode-cn.com/problems/minimum-genetic-mutation/

启发式搜索

• https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/
• https://leetcode-cn.com/problems/sliding-puzzle/
• https://leetcode-cn.com/problems/sudoku-solver/

参考链接

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