Algorithm

树的搜索策略

Posted by Surflyan on 2017-07-13

许多实际问题的解空间可以组织成一棵树，那么问题的优化解变成了搜索解空间对应的搜索树。这里介绍五种典型搜索策略。

1. 广度优先搜索

1.1 算法思想

广度优先搜索从树根开始，逐层访问树中的结点。在第k层处理完之后，再处理第k+1层的节点。由此，广度优先搜索使用队列来扩展节点，在处理完该结点之后就将该节点的孩子节点添加到队列中，使得第k+1层节点按序分布；

1.2 算法步骤

  1. 构造由根组成的队列Q；
  2. If Q的第一个元素x是目标节点 Then 停止;
  3. 从Q中删除x，把x的所有子节点加入Q的末尾;
  4. If Q空 Then 失败 Else goto 2.

2. 深度优先搜索

2.1 算法思想

深度优先搜索从根节点开始，总是首先扩展其子节点，往更深的方向搜索，直到不能访问为止；若最近访问的节点的所有孩子都已访问过，则回溯到其兄弟节点继续深度优先搜索；由此，深度优先搜索采用栈结构扩展结构。

2.2 算法步骤

  1. 构造一个由根构成的单元素栈S;
  2. If Top(S)是目标节点 Then 停止;
  3. Pop(S), 把Top(S)的所有子节点压入栈顶;
  4. If S空 Then 失败 Else goto 2.

3. 爬山法

3.1 算法思想

在深度优先搜索过程中, 经常遇到多个节点可以扩展的情况, 爬山策略使用贪心方法确定搜索的方向,使用启发式测度来排序节点扩展的顺序。对于每一个节点有一个隐式约束P(X)，不仅可以判断x是否为目标节点，还可以判断距离目标节点的距离。爬山法在深度优先搜索时每次先扩展距离目标节点近的节点，使得目标节点能尽早被发现。

3.2 算法步骤

  1. 构造由根组成的单元素栈S;
  2. If Top(S)是目标节点 Then 停止;
  3. Pop(S);
  4. S的子节点按照其启发测度由大到小的顺序压入S;
  5. If S空 Then 失败，Else goto 2.

爬山法发现的解为可行解；

4. 最佳优先搜索

4.1 算法思想

最佳优先搜索同爬山法不同的是，它每次从全局范围内选取扩展方向。即从当前所有的可扩展节点中选取隐式约束P(X)最小的节点作为扩展方向。最佳优先搜索使用堆结构扩展节点。

4.2 算法步骤

  1. 使用评价函数构造一个堆H, 首先构造由根组成的单元素堆;
  2. If H的根r是目标节点 Then 停止;
  3. 从H中删除r, 把r的子节点插入H;
  4. If H空 Then 失败 Else goto 2.

最佳优先搜索找到的是可行解；

5. 分支限界法

5.1 算法思想

分支限界法要点为： 利用已发现的可行解的代价剪除不能取得优化解的分支，从而避免对不能产生优化解的分支进行搜索。

分支限界法具有两个要素：

  1. 产生可行解的策略。可以选择爬上法、DFS、BestFS策略，值得注意的是不能采用BFS，自行体会。
  2. 剪除分支的策略。如何判定节点为根的子树任意可行解的代价大于已知可行解的代价。这需根据具体问题建立绑定函数。

5.2 算法步骤

  1. 建立根节点, 其权值为解代价下界;
  2. 使用爬山法, 类似于拓朴排序序列树生成算法求解问题, 每产生一个节点, 其权值为加工后的代价矩阵对应元素加其父节点权值;
  3. 一旦发现一个可能解, 将其代价作为界限, 循环地进行分支界限搜索: 剪掉不能导致优化解的子解, 使用爬山法继续扩展新增节点, 直至发现优化解.

分支界限法要想取得比较好的效果，可从两个方面考虑：

  1. 如何尽快找到一个相对较优的可行解。 以便剪除较多的分支。
  2. 如何尽早的剪除分支，也就是越在靠近根节点的地方剪除，越能产生良好的效果。可考虑一开始就对代价矩阵进行变换，给根节点一个代价下界。

请多多指教！

CATALOG
    FEATURED TAGS
    Algorithm
    <