undefined

初级搜索

1. 朴素搜索
2. 优化方式：不重复(fibonacci)、剪枝(生成括号问题)
3. 搜索方向：DFS、BFS

剪枝

leetcode 36、37
数独问题
只需要去递归需要的

双向BFS

从起点和终点向中间推进

leetcode 127 单词接龙问题 google 考过很多次，一定要会

启发式搜索(A*)

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

A* search

def AstarSeach(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 visited]
        pq.push(unvisited) 

实战题目：leetcode 109