02年05月09日回溯策略

1、穷举策略基本思想：第一步只考虑问题的部分条件，根据这些条件，找到所有的满足这些部分条件的解，称为可行解。然后用尚未考虑的条件去一一检验那些可行解，删去不符合条件的解，留下符合条件的解，就是整个问题的解。例 如图的八个格子中放入1至8八个数字，使得相邻的和对角线的数字之差不为1.编程找出所有放法。b1b2b3b4b5b6b7b8b1b2b3b4b5b6b7b812345678910111213141112223334556723435646776878ij12354668151617b1b2b3b4b5b6b7b8条件1：b1b8互不相等条件2：相邻数字差不为1穷举策略For b1:=1 to

2、8For b2:=1 to 8For b3:=1 to 8For b4:=1 to 8For b5:=1 to 8For b7:=1 to 8For b8:=1 to 8For b6:=1 to 8如果满足条件1满足条件2打印剪枝策略b1:=2; b3:=8; b6:=1; b8:=7; For b2:=1 to 8For b4:=1 to 8For b5:=1 to 8For b7:=1 to 8如果满足条件1满足条件2打印b1:=7; b3:=1; b6:=8; b8:=2; For b2:=1 to 8For b4:=1 to 8For b5:=1 to 8For b7:=1 to 8如

3、果满足条件1满足条件2打印回溯策略 不是按照某种固定的计算方法来设计算法，而是通过纠正错误来寻找答案。 通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就再逐步往回退，换别的路线再往前试探。编程找出下面字母方阵中所有隐含的单词 SEARCH,单词中字母走向可以是八个方向。打印格式为：（h,v）A1 A2 A3 A4 A5其中Ai是方向编号，向上为1，顺时针方向顺次为2，3，4，5，6，7，8。h,v是第一个字母S的行和列数SEAECHAASREHHERAESECHAHCRCASERAHHRHSFor h:=1 to 6 do第h行v列是S？

4、For v:=1 to 6 doYN存当前位置：si1:=h;sj1:=v;Search(2,h,v)l:=0;fg:=F存i,j和方向Lny打印fg:=falsenyDep=6Until dep=1Until fg or dep=1L:=L+1;求L方向的位置I，J如(i,j)是第DEP个字母,fg:=trueUntil (fg=true)or(L=8)fg=truedep:=dep-1回溯Dep:=dep+1;h:=i;v:=j;Search(dep,h,v)（1，1）33423（1，1）33424（1，1）35463（5，4）38868（6，6）88863（6，6）88868SEAECHAASREHHERAESECHAHCRCASERAHHRHS练习： 骑士周游问题。给定一个n*n的方阵，共有n2个区域，有一个国际象棋的马置于一个区域上，要求找到一条路径，使马按国际象棋的规则，从开始区域出发，不重复地把n2个区域都恰好经过一次。 八皇后问题。在n