有很多实际问题可以转换为树搜索问题。比如说魔方求解、0/1背包、最短路径等等问题，都可以通过树搜索来完成。我们可以认为，树搜索是一种暴力搜索(Brute-force search)的方法。当然，配合一些在树搜索上的优化算法，我们可以提高搜索到问题解的速率。

编辑中

将问题转换为树搜索问题

很多问题可以表示为树，我们可以通过树上的搜索来解决这些问题。

1. 布尔表达式的可满足性问题

   有n个布尔变量，需要满足k个表达式，问这些变量该如何赋值。

   转换为树搜索，其实也就是暴力搜索。

   其实很多时候，我们在说暴力搜索，其搜索结构想要枚举出来，往往需要借助栈、队列等，其实这个时候，我们已经建立了一个树结构！

2. 8-魔方问题，怎么移动，才能满足魔方的顺序！

   想不到就是这么通过树来做暴力枚举！

3. 检测（或者找到）图中哈密顿环

   哈密顿环：从一个顶点出发，经过不重复的边，遍历所有的顶点，并回到原来的出发点。这就构成了一个哈密顿环。（这是一个NP完全问题）

   转换为树搜索，暴力搜索。

基础树搜索算法

1. 广度优先搜索(Breadth-First Search , BFS)

   使用队列来完成广度优先搜索。

    init(Q)
    Q <- Root
    while(!Empty(Q))
    {
        node <- Dequeue(Q)
        visit(node) 
        for child in Childs(node) 
        {
            Enqueue(Q , child) 
        }
    }
   

2. 深度优先搜索(Depth-First Search , DFS)

   使用栈来完成深度优先搜索。（因此也可以使用递归来完成）

    init(S)
    S <- Root
    while(!Empty(S))
    {
        node <- Pop(S)
        visit(node) 
        for child in Childs(node)
        {
            Push(S , child)
        }
    }
   

优化的搜索算法

其实优化这个概念在树搜索中还是非常简单的，就是在BFS或DFS的基础上，加上一些比较直观的规则即可。

1. 爬山法(Hill climbing)

   两个关键点：

   1. 使用的基础搜索算法是深度优先（DFS） 。

   2. 使用一个测度函数，排序孩子节的遍历顺序（入栈顺序）。

   测度函数往往是根据启发式规则来制定。

   例如：

   8-魔方问题使用爬山法解决，测度函数可以定义为，选择的状态与最终想要的状态的不同的个数。越小越优先选择（当然越后入栈）。

   爬山法能够在测度函数度量下最快得到局部最优解。（贪心）所以往往可以将爬上法再加上后面要说的分支界限法

2. 最佳优先搜索策略(Best-First Search Strategy)

   关键点：

   1. 使用一个评价函数来度量节点的好坏（一般来说，这个评价函数能够准确地评价各状态的好坏）

   2. 使用堆，保证全局最优搜索

   堆的使用是Best-First的关键。这使得搜索时不再是单纯的深度优先或广度优先，而是每次选择当前最优节点进行扩展。

3. 分支界限策略(Branch-and-Bound strategy)

   这是从另外的维度来优化搜索算法。

   爬山法和最佳优先，往往用来快速找到问题的一个答案。如果是求解优化问题，对于爬上法，还是需要全部搜索的，对于最佳优先，如果我们的评价函数就是代价函数，那么最优价就是第一个扩展出的解。

   而分支界限法主要用于找最优解，方法就是先找到一个界限，然后在遍历时根据界限来剪枝。也是比较直观的方法。

   分支界限的通常做法：

   1. 使用爬上法快速找到一个界限

   2. 继续搜索+剪枝