0.为什么要树搜索？
有许多问题，它们的解可以表示为树。举个例子：
布尔表达式可满足性问题
q输入：由$x_1,x_2,\cdots,x_n$n个逻辑变元组成的逻辑表达式$A$。
输出：指派$v$，令$A^v=T$，即一种变元赋值，让表达式为真。
对于每一个变元，都有0,1或者F,T两种取值，那么我们可以构造出这样一棵树来：
于是乎，我们可以应用树的相关算法，求解这样的一些问题。
8-puzzle问题
该问题根据每一次挪动，可以被转化为树搜索问题：
首先我们先介绍两个算法：DFS,BFS。之后我们讨论如何优化树搜索的相关算法。
1.深度优先搜索(DFS)
对于一个图，我们想知道两个点之间是否有一条通路，可以使用DFS算法。
DFS算法有种“不撞南墙不回头”的感觉，算法如下：
- 将起点压栈，标记为访问过。（从起点）
- 将一个与栈顶点邻接的，且未被访问过的节点压栈，标记为访问过，递归此步。（一直走下去）
- 如果最后没有没访问过的节点，且目标点没有遍历过，则回溯，将当前节点弹出，重新选择节点压栈。（直到走不通，往回走）
2.广度优先搜索(BFS)
BFS相比于DFS,就灵活很多，它有种“扩散”的感觉，算法如下：
- 将起点入队，标记为访问过。（从起点）
- 将与起点所有邻接点入队，标记为访问过，同时将起点出队，递归此步。（扩散）
3.爬山法
对于一个可以用树搜索+DFS解决的问题，在深度优先搜索中，如何判定令哪个节点入栈最优呢？
我们可以使用贪心算法，即每一步都选令局部最优的那个解。
对于8-puzzle问题中的每一个步骤，我们可以编写出一个代价判据，每次都根据栈顶点，选择让这个代价判据最小的新点入栈。
通俗的来讲，就是在DFS“一直走下去”的过程中，每次都选择最“方便”的那一个点。
举个例子，我们让代价判据为“所有处于错误位置的方块数”，那么应用爬山法：
就可以找到一个解啦。
4.Best-First搜索算法
但是，这不够好，贪心是局部最优的，有的时候局部最优显然不是全局最优解，Best-First算法就是为了解决这个情况而生的。
我们同样设立一个代价判据，但是，在所有节点中选择令代价判据最小的方案。
同样对于8-puzzle问题，如果应用这个算法：
- 先走第一层，出现3,3,4,4的代价。
- 让两个3代价的展开，出现3,4,2,4的代价。
- 展开2代价的点。
- $\cdots$
5.分支限界法
除此之外，我们可以采用这样的模式：把不可行的解都排除，只留下可行的解，再在可行解空间内讨论最优解。
6.旅行商问题（TSP）
思路
给定一个有向图，这个图满足如下条件：
- 每个节点都没有到自己的边。
- 每对节点间都有一条非负加权边。
输出从任意一个节点开始，经过每个节点一次，最终返回开始节点的最短路径。
对于这个问题，我们采用如下的步骤求解：
- 将所有解集合作为树根，设定一个基础代价，由代价矩阵计算所有解的代价的下界。
- 用爬山法递归地划分解空间，得到二叉树。
划分过程：
- 选择图上的任意一条边$(i,j)$划分，该划分要让左子树代价下界不变，右子树代价下界增加最大；且所有不包含$(i,j)$的解集合作为左子树，不包含的解集合作为右子树。
- 计算左右子树代价下界。
划分到最后会出现一个解，这个解的代价$\alpha$是所有解的代价上界，如果对于其他子节点来说，它们的下界超过了$\alpha$，就停止继续划分。
这样的求解方法相当于：先将所有解汇总起来，通过二叉树的搜索方法，排除掉那些代价高的，最终筛选出一个低代价的解。
基础代价的设定
代价矩阵里，包括着两点间每一条边的长度，如果不存在边，就设为$\infty$，举个例子：
$$
\left[
\begin{matrix}
\infty & 3 & 5 & 9\
4 & \infty & 6 & 8\
7 & 3 & \infty & 2\
3 & 5 & 7 & \infty\
\end{matrix}
\right]
$$
第$i$行，第$j$列的点表示$(i,j)$的长度。
基础代价肯定是几条边的长度的和，怎么选呢？我们不妨选择一些最小边，让每一行、每一列都有被选择出来的边。后续根据这些边再构造解。
我们在每一行都减去一个最小值：
$$
\left[
\begin{matrix}
\infty & 0 & 5 & 9\
0 & \infty & 6 & 8\
7 & 3 & \infty & 0\
0 & 5 & 7 & \infty\
\end{matrix}
\right]
$$
同时把所有减去的值加起来。这是为什么？
此外，要求：每一列都有0,每一行都有0。因为我们最终要把每个点都跑一遍。于是矩阵变成：
$$
\left[
\begin{matrix}
\infty & 0 & 0 & 9\
0 & \infty & 6 & 8\
7 & 3 & \infty & 0\
0 & 5 & 7 & \infty\
\end{matrix}
\right]
$$
初始代价为$3+4+2+3+5=17$。这就是我们的代价下界。
划分
选择让右子树代价下界增加最多的划分边$(i,j)$，这又怎么选呢？
左子树代价不能变，所以只能从矩阵中那些为0的边中选择。其次，右子树是不包括划分边的，我们可以在矩阵中把划分边所在的行、列都不予考虑，重新构造代价下界，让剩下的每一行、每一列都出0。
之后在左右子树内都不断再分，可以选择先分割左子树，最终得到一个代价上界。
7.A*算法
一个很有效的搜索最短路径的算法。
原理：
$$
f(n)=g(n)+h(n)
$$
其中，对于任一节点$n$，$f(n)$是经过节点$n$到目标节点的代价，$g(n)$是从起始节点到节点$n$的代价，$h(n)$是从节点$n$到目标节点的最小估计代价。
我们可以采用Best-First算法和BFS算法结合实现对$h(n)$的估计，从起始节点开始跑BFS,每一个节点的$h(n)$就是这个节点所有未被遍历过的边的最小值。