回溯回顾

很长一段时间里常常听说 backtrack 这个词,其实一直缺少的是一个形式上的 formulation,这个 formulation 可以帮助我们思考问题,我想通过这篇 blog 完成这个小结,这个思想也能帮助我们求解不少问题。回溯问题一般都是一个搜索问题,其解往往是通过一个序列来进行表示,我们记为 (s_1, \ldots, s_t),我们往往可以根据某种约束来判断当前状态是否为合法的解,而如果不是我们有一个 traverse 的顺序帮助我们寻找下一个 candidate 状态 s_{t + 1},如果尝试失败,就会进行 backtrack。如果认为每一个状态都是 graph 的一个顶点,backtrack 等价于在这个 graph 上进行深度优先搜索(DFS)。因此,将一个问题转换到 backtrack 上来的要素就是:

  • 状态是什么?
  • 怎样获得下一个 candidate?
  • 回溯的策略如何(是否需要 stack)?
  • 如何判断某个状态是不是可接受的以及碰到可接受情况下的策略(终止并返回或者是继续下去?)

我们先从一个简单的 case 开始。

给定几个不同的数字生成所有的排列,这个问题算是比较经典的回溯求解的问题了,比如我们就拿 1,2,3,4 来看,其实不难知道,如果我们把这四个数放下去的情形当作是状态,比如当前放下去 1,2,那么下一个 candidate 就是从 3,4 里面选择,到四个数都放下去的时候就是可接受的状态,因为我们需要继续生成其他的情况,就需要继续下去,这里我们可以把这个也当做是 backtrack,这样比如到了 1234 生成之后,因为最后一位没有选择的 candidate,我们就选择 backtrack,拿走 4 之后第三位存在另一种选择,因此我们有 1243,再之后大家可以尝试…

到了实现的阶段就会有几个问题,如果我们为约束创建一个 set 表示当前还能用数字集合,那么 backtrack 等价于从这个集合拿走和放回去,规则就是如果需要寻找下一个 candidate,set 里面必须存在比当前位置值大的数,找不到就 backtrack。但是是不是真的我们需要这么一个 set 来辅助我们的实现呢。其实我们观察几个情形,1243、1342、1432,你会发现当 2、3、1 需要 backtrack 的时候后面的数字一定是全逆序,否则后面的数字不是这几个数能组成的最大数,换言之出现 backtrack 等价于之后的序列一定是逆序的话,我们就好办了。这时下一个 candidate 一定是后面逆序序列里面比将要 backtrack 元素大的最小的那个,2<->3、3<->4,而1<->2,由于后面是有序的,我们可以用 binary search 找到这个值(其实直接搜也一样,不改变复杂度),这里的一个 trick 是因为换过来的是比原先较小的数,这能保证逆序不变,因此交换之后只需要逆转一下这个序列就得到了下一个接受的状态。所以我们可以隐式的完成 backtrack 的过程。(具体实现参看 STL 的 std::next_permutation,很显然这只需要 bidirectional iterator 就能 in place 实现了)

这个问题的扩展就是 Gauss 八皇后问题,我们知道 8 皇后一共 4 种 constraints,横竖和斜着的。横竖的约束其实很容易解决,我们只需要生成全排列就得到了一组满足横竖约束的解:这怎么说?比如 12345678 就表示第一行放在第一列,第二行放在第二列… 这样一来排列的性质导致每行一个每列也只放一个皇后,剩下的自然就是两个斜着的方向的约束了。很自然我们希望有某种表达能简化这个。其实对矩阵比较熟悉的同学很快就想到这两种对角线无外于 (i + j) = \text{const.}(i - j) = \text{const.},因此我们可以创建两个 bool 数组来检查这约束的情况。比较偷懒的做法自然是干脆直接用 next_permutation 然后包上一层检查约束的算法判定是否输出了。其实 8! 的搜索可能也就一眨眼了…

当然这并不是个好算法,我们回到前面的 backtrack,原先我们通过一个 set 来保证横竖约束,现在无非还需要加上两个 set,这三个 set 的并集决定下一个 candidate 是谁了,不过这里需要注意的是每改变一次状态,我们都有三个 set 的约束需要更新,程序写的不好的话这个地方漏掉了是很难 debug 的。sudoku 的求解其实也是类似的。

下面列举另外两个经典问题:

  • 求解 convex hull 的 Graham 算法,通常我们先从一个 extreme point 入手,保证其他点都在一侧,扫描的顺序一般是通过到 extreme point 的角度来确定的,这样我们就可以开始搜索 convex hull 那些边了,其实原则就是新家的边不能产生 >180 度的夹角,如果发生了,我们就找下一个 candidate(这样一来我们还是可以用一个 bool 数组 track 每个顶点是否在 convex hull 里面了),如果找不到了就进行回溯。这里有一个好处是中间被遗弃的点后面是不可能再用上的,所以回溯只能去找更后面的,于是我们只需要线性时间就能搜索完。麻烦的是前面排序的部分代价还是 O(N\log N) 的。
  • 求解 TSP,求遍历所有图顶点但不重复的最短路径,这本质上是遍历所有的圈,然后取路径最短的算法。

有了这些认识,我们是否能将 backtrack 算法弄成一个 generic pattern,虽然对具体的问题不见得是最优的实现,但是能帮助大家理解清楚 backtracking 机制里面哪些要素一旦提供出来就能求解呢?

——————
And Isaac intreated the LORD for his wife, because she was barren: and the LORD was intreated of him, and Rebekah his wife conceived.

Advertisements
回溯回顾

一个有关“回溯回顾”的想法

  1. zt 说:

    哦,问题不是 generalize 之后的效率,而是希望提供一个快速解决的方案,不是最优可以想办法特化或者引入某些机制来优化。

  2. hxtang 说:
    template <class BidirectionalIterator>
      bool next_permutation (BidirectionalIterator first,
                             BidirectionalIterator last ) {
    
      BidirectionalIterator it=last, itl=last;
      --it;
      do{
        --it; --itl;
      } while (itl != first && *it > *itl);
    
      if (itl==first) return false;
      const BidirectionalIterator pivot = it;
    
      it = last;
      do {
        --it;
      } while (*it < *pivot);
    
      std::swap(*it, *pivot);
      std::reverse(itl, last);
      return true;
    }
    

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s