回溯与搜索初步.ppt

《回溯与搜索初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、回溯与搜索初步第一部分　回溯一、回溯的概念从问题的某种可能情况出发，搜索所有能到达的可能情况，然后以其中一种可能的情况为新的出发点，继续向下探索，当所有可能情况都探索过且都无法到达目标的时候，再回退到上一个出发点，继续探索另一个可能情况，这种不断回头寻找目标的方法称为“回溯法”。一、回溯的概念回溯算法是一种有条不紊的搜索问题答案的方法，是一种能避免不必要搜索的穷举式的搜索算法，其基本思想就是穷举搜索。常用于查找问题的解集或符合某些限制条件的最佳解集。一、回溯的概念回溯算法常被用来解决自然数排列问题、皇后问题、迷宫问题、数的拆分、0/1背包问题、骑士问题、货船装箱

2、问题和图形覆盖问题等。下面我们来看一段走迷宫的演示，初步体会一下回溯的思路。二、回溯的一般描述procedurerbacktrack(k);beginifk>nthenreturnelseforeachx(k)，如果x(k)∈t(x(1)…x(k-1))且b(x(1)…x(k))=truedobeginifx(1)…x(k)是一个解thenwrite(x(1)…x(k)elserbacktrack(k+1);end;end;二、回溯的一般描述procedurebacktrack(n);begink:=1;whilek>0andk<=ndoif对于没有试过的值x(

3、k)，x(k)∈t(x(1)…x(k-1))且b(x(1)…x(k))=truethenbeginifx(1)…x(k)是一个解thenwrite(x(1)…x(k));inc(k);endelsedec(k);//回溯end;三、回溯的一般步骤首先需要为问题定义一个解空间（solutionspace），这个空间必须至少包含问题的一个解；然后我们需要组织解空间，以便它能被容易地搜索。典型的组织方法是图或树。最后对这个空间即可按深度优先的方法从开始节点进行搜索。三、回溯的一般步骤开始节点既是一个活节点又是一个E-节点（expansionnode、扩展节点）。从E-

4、节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。三、回溯的一般步骤定义一个解空间，它包含问题的解；用适于搜索的方式组织该空间；用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。四、应用举例—n皇后问题我们在前面已经讨论过n皇后问题，现在我们用回溯的思路

5、来分析一下n皇后问题，看看是否能枚举较少的排布。我们仍旧规定第k个皇后位于第k行。既然回溯算法是由一个节点开始扩展的，因此我们现在一个一个的把皇后放到棋盘上。n皇后问题首先要把第一个皇后放到棋盘上由于第一个皇后有n列可以放，因此可扩展出n种情况。先选其中一列放下这个皇后；然后开始放第二个皇后。同样第二个皇后也有n列可以放，因此也能扩展出n种情况，但第二个皇后可能会和第一个皇后发生攻击，而一旦发生攻击，就没有必要往下扩展第三个皇后，而如果没有发生攻击，则继续放第三个皇后；依此类推，直到n个皇后全都放下后，即得到一组可行解。扩展全部完成后即可得到结果。n皇后问题n皇

6、后问题n皇后问题的解空间就应该是1～n全排列的一部分。解空间的长度是n。解空间的组织形式是一棵n叉树，一个可行的解就是从根节点到叶子节点的一条路径。控制策略则是当前皇后与前面所有的皇后都不同列和不同对角线。n皇后问题（边界判定）functioncheck(pos:integer):boolean;vari:integer;begincheck:=true;fori:=1topos-1doif(x[pos]=x[i])or(abs(x[pos]-x[i])=abs(pos-i))thenbegincheck:=false;break;end;end;n皇后问题（递

7、归）proceduresearch(k:integer);vari:integer;beginifk>nthen//是否前n个皇后都已经放下inc(count)else//还有皇后没放fori:=1tondo//从第1列开始逐列尝试beginx[k]:=i;//把第k个皇后放在第i列ifcheck(k)then//第k个皇后是否可以放在第i列search(k+1);//可以放，继续处理第k+1个皇后end;end;n皇后问题（非递归）top:=1;//从第一个皇后开始尝试while(top>0)do//当还有活动节点时循环if(top>n)then//是否n个皇

8、后都放置在棋盘了begi