回望全排列

回溯全排列

回溯的实质是在问题的解空间进行深度优先搜索。DFS是个图的算法，但是回溯算法中的图在哪里呢？我们把解空间中的一个解状态当成一个节点，由于解空间非常庞大，所以这个图也就大到无法想象了。

举个例子吧，比如全排列问题，对于n个元素进行全排列，一共有n!种可能，比如n=9时，一共有9! = 362880种排列。初始化，我们什么都没有，定义如下状态

此时，再想扩展黄色节点时，发现m_arranged已经是3了，这时表明这是一个最终的节点，无法再扩展了，于是得到了一个排列。那么其他排列如何得到呢？回到黄色节点上面的蓝色节点，我们发现第三位除了3再也不能填其他数了，没法继续扩展，没办法，再回到上面的紫色节点，这时发现，紫色节点中的第二位还能填3，于是可以顺利扩展到下面的第二个蓝色节点。这个过程便是回溯和扩展节点的主要过程。

在编程实现时，由于我们无法存储所有的状态节点，只能保持一个当前状态，然后通过扩展到下一个节点，来修改当前节点的状态，但是当扩展完一个节点时，必须得恢复到原来节点的状态，才能进行下一个扩展。这个逻辑写成代码便是如下形式：

#include "stdafx.h"#include "..\Utility\GFClock.h"// 1-9const int PT_SIZE = 10;class PTState{public:PTState(){m_arranged = 0;memset(m_used, 0, sizeof(int) * (PT_SIZE + 1));}bool IsFinal(){return m_arranged == PT_SIZE;}void PrintSolution(){for (int i = 0; i < PT_SIZE ; i++){cout << m_solution[i];}cout << endl;}bool CanPlace(int i){if (m_used[i] == 0){return true;}return false;}void Place(int i){m_used[i] = 1;m_solution[m_arranged++] = i;}void Remove(int i){m_arranged --;m_used[i] = 0;}int m_solution[PT_SIZE];int m_arranged;int m_used[PT_SIZE + 1];};int gCount = 0;void Solve(PTState& state){if (state.IsFinal()){//state.PrintSolution();gCount ++;return;}for (int i = 1; i <= PT_SIZE; i++){if (state.CanPlace(i)){state.Place(i);Solve(state);state.Remove(i);}}}int _tmain(int argc, _TCHAR* argv[]){GFClock clock;PTState state;Solve(state);cout << gCount << endl;cout << clock.Elapsed() << endl;}