如图1所示，这是很多人小时候都玩过的彩色转盘玩具。玩法显而易见就是要把打乱的两个转盘归位到图1所示的目标状态。如果要用搜索的办法解这个问题的话（当然，实际的玩法不是硬搜，而是有一定的规律的，在这里只是举一个搜索的例子），有一个特别的优化方法，就是双向搜索。


    有一些搜索问题的目标状态是唯一的，比如这个转盘玩具，目标只有图1所示的这一个状态。对这种问题可以用双向搜索的方法来解，也就是从起点向前搜一段，同时也从目标往回搜一段，如果两边遇到了某个相同的状态，则从起点到终点的一条路径就找到了。

    比如在这个玩具中，每一步都有4种走法：把左（右）边的转盘顺（逆）时针转一格。（实际上每步只有3种走法，因为如果上一步把一个转盘顺（逆）时针转了一格，下一步再把同一个转盘逆（顺）时针转回去一格是没有意义的。）如果步数最少的一个解需要走16步，那要搜索的时间就是O（3¹⁶） ≈ O（10⁷）。但是如果从两边各搜到第8步，每边最多各得到大约3⁹ = 19683个状态（实际上差不多只有一半，有很多是重复的）。看看两边有没有遇到相同的状态（用二叉搜索树之类的结构来保存两边所有状态的话，查找就会很快），如果有的话就说明找到了一个16步以内的解。这样一来时间效率就很快了，大约O（10⁵）。

    可以想像，双向搜索的时间复杂度比单向搜索可以少差不多一半的指数（因为只要搜到一半的深度），所以会快很多。

    还没有试过的请去UVA 704试试吧。