搜索算法的感悟——解空间

练习了将近一个月的搜索算法了，也有了一些小小的感悟。

搜索算法的两个关键问题：

（1）：如何找到整个解空间。

（2）：如何剪枝。

我的感悟是关于解空间的。问题的解往往需要经过一系列操作之后才能得到，而在这一系列的操作中，每一步的操作都会的到一个状态，当最终这个状态与目标状态相同时，此时也就是得到了结果，所以在搜索的过程中，着重需要处理的就是操作和状态。只有考虑了所有可能的操作，才会得到所有可能的状态。下面举例说明。

以NYOJ的21题《三个水杯》为例（这道题的题目及解题报告在本博客中，读着可先阅读题目），问题所包含的所有操作如下图：

每一步都有6种操作方法，那是不是按照这6种操作方法进行搜索，就可以得到结果了呢？先来看看下面这组测试数据：

6 3 1

4 1 1

按照6中操作方法所得的搜索树如下图：

如图中红色箭头所示的搜索路径A→B→A……，A→C→A……，如果按照深度优先进行搜索（当然，这道题最好使用宽度优先搜索，这里只是为了说明问题），这里出现了死循环。那是不是只要避免出现这种搜索路径，就能避免出现死循环呢？遗憾的是出现死循环的路径还可以是更复杂一些的，所以很难通过对操作进行限制来解决出现重复状态。

既然因为同一个状态在搜索树中重复出现，导致搜索的无穷尽。容易想到在状态上做文章，也就是将搜索中出现的状态保存下来，当得到新的状态时，判断该状态是否出现过，出现过则舍弃，如下图：

通过这个例子，发现当考虑了所有的操作时，还要对操作所得状态进行判断，是否已出现过，来避免重复搜索。这道题我纠结了好久，就是因为我想通过限制操作来避免出现重复状态，而出现重复状态的情况有很多，很难考虑全面。其实判断状态是否重复我之前也都做过，就是在搜索迷宫的过程中，操作就是移动的方向，而状态就是位置，为了避免重复搜索就在地图上做标记，当时这样做的时候觉得顺理成章，不过在这题里，却并没有能直接这样做。

总结下，在搜索整个解空间时，首先是考虑所有的操作，然后通过保存已出现状态，来防止重复搜索。如果很容易通过对操作进行限制来防止状态的重复出现，或是保存状态所需的内存空间过大的话，那就不宜保存状态。

本人菜鸟，有高见者请赐教！