谁能告诉我回溯算法应用的依据和意义啊

Question

100全送！

Answer 1

所谓回溯：就是搜索一棵状态树的过程，这个过程类似于图的深度优先搜索（DFS），在搜索的每一步（这里的每一步对应搜索树的第i层）中产生一个正确的解，然后在以后的每一步搜索过程中，都检查其前一步的记录，并且它将有条件的选择以后的每一个搜索状态（即第i+1层的状态节点）。 需掌握的基本算法： 排列：就是从n个元素中同时取r个元素的排列，记做P(n,r)。（当r=n时，我们称P(n,n)=n!为全排列）例如我们有集合OR = {1,2,3,4},那么n = |OR| = 4,切规定r=3，那么P(4,3)就是： {1,2,3}; {1,2,4}; {1,3,2}; {1,3,4};{1,4,2};{1,4,3};{2,1,3};{2,1,4}; {2,3,1}; {2,3,4}; {2,4,1}; {2,4,3}; {3,1,2}; {3,1,4}; {3,2,1}; {3,2,4}; {3,4,1}; {3,4,2}; {4,1,2}; {4,1,3}; {4,2,1}; {4,2,3}; {4,3,1}; {4,3,2} 算法如下： int n, r; 
char used[MaxN]; 
int p[MaxN]; void permute(int pos) 
{ int i; 
/*如果已是第r个元素了，则可打印r个元素的排列 */ 
if (pos==r) { 
for (i=0; i cout << (p[i]+1); 
cout << endl; 
return; 
} 
for (i=0; i if (!used[i]) { /*如果第i个元素未用过*/ 
/*使用第i个元素，作上已用标记，目的是使以后该元素不可用*/ 
used[i]++; 
/*保存当前搜索到的第i个元素*/ 
p[pos] = i; 
/*递归搜索*/ 
permute(pos+1); /*恢复递归前的值，目的是使以后改元素可用*/ 
used[i]--; 
} 
}