思想

在之前的BFS习题中，有一类 知道搜索起点和终点的BFS（如八数码，开锁等） 值得注意。可以用双向BFS的方法提高一点效率。

双向BFS：从起点和中点同时开始BFS，当两边有交集时结束。

可以发现，使用双向BFS后，可少搜索一些节点，以提升搜索效率。

思想

把一些问题抽象成图，从一个点开始，向四周扩散，然后问你求最短路。当边权为1时，才能用BFS。BFS找到的路径一定是最短的，但代价就是空间复杂度可能比DFS大得多。

BFS的代码框架如下：

queue.push(初始状态)
while (队列不空)
{
	取队头t
    拓展队头t
}

本文复习一下Shadow Map是怎么做的，它的问题与解决方法，以及他背后的数学。

思想

DFS算法，也称回溯算法，本质上就是一种暴力穷举算法。解决一个回溯问题，实际上就是一个决策树的遍历过程，站在决策树的一个节点上，只需要思考以下三个问题：

1. 路径：已经做出的选择；
2. 选择列表：当前可做出的选择；
3. 结束条件：已经到达决策树底层，无法再做出选择。

DFS算法的代码框架如下：

result = []
def dfs(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做出选择
        dfs(路径, 选择列表)
        撤销选择

其核心就是for循环里的递归，在递归调用前“做出选择”，在递归调用后“撤销选择”。

我人生中第一次面试，结结巴巴的，暴露出很多不足！