2019数据结构C++第5章第10讲(tree) .pptx

回溯法的基本使用，重点原理人工智能的基本思路之一，穷举队列与循环队列本次课重点练习热身（2’）试将下列递推过程改写为递归过程。void?ditui(int n){i=n;?while(i1) printf(i--);}(3,A,B,C)参数映射过程A,B,CA,B,C(2,A,C,B)A-C(2,B,A,C)A-CA,B,CA,B,CA,B,CA,B,C(1,A,C,B)(1,B,A,C)(1,A,C,B)(1,B,A,C)A-CA-CA-BB-CA-CA-CA-CA-CA-BA-CA-BB-AB-CC-BB-CA-C递归与回溯对一个包含有许多结点，且每个结点有多个分支的问题，可以先选择一个分支进行搜索。当搜索到某一结点，发现无法再继续搜索下去时，可以沿搜索路径回退到前一结点，沿另一分支继续搜索。如果回退之后没有其他选择，再沿搜索路径回退到更前结点，…。依次执行，直到搜索到问题的解，或搜索完全部可搜索的分支没有解存在为止。回溯法与分治法本质相同，可用递归求解。n皇后问题在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n 皇后问题是指找到这 n 个皇后的互不攻击的布局。0#次对角线2#次对角线4#次对角线6#次对角线k = i+j1#次对角线3#次对角线5#次对角线0 1 2 3 0123???0#主对角线2#主对角线4#主对角线6#主对角线1#主对角线3#主对角线5#主对角线?k = n+i-j-1解题思路安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) 在第 j 列安放一个皇后：如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] : q[i] 记录第 i 行皇后在第几列x1=12x2= 23N皇后问题 开始把根结点作为唯一的活结点, 根结点就成为E-结点而且路径为( ); 接着生成子结点, 假设按自然数递增的次序来生成子结点, 那么结点2被生成, 这条路径为(1), 即把皇后1放在第1列上.1结点2变成E-结点, 它再生成结点3, 路径变为(1, 2), 即皇后1在第1列上,王后2在第2列上, 所以结点3被杀死, 此时应回溯.kill1121x1=12x2= 2x2= 383killx3=4x3=2911N皇后问题 回溯到结点2生成结点8, 路径变为(1, 3), 则结点8成为E-结点, 它生成结点9和结点11都会被杀死(即它的儿子表示不可能导致答案的棋盘格局), 所以结点8也被杀死, 应回溯.123112312killkill1x1=12x2= 4x2= 2x2= 31383x3=2killx3=3x3=4x3illkillx4=315N皇后问题 回溯到结点2生成结点13, 路径变为(1, 4), 结点13成为E-结点, 由于它的儿子表示的是一些不可能导致答案结点的棋盘格局, 因此结点13也被杀死, 应回溯1123123412killkill1x1= 2x1=1182x2= 4x2= 1x2= 2x2= 3x2= 319132483x3=2killx3=4x3=3x3illkillkillx4=315killN皇后问题 结点2的所有儿子表示的都是不可能导致答案的棋盘格局, 因此结点2也被杀死; 再回溯到结点1生成结点18, 路径变为(2).结点18的子结点19、结点24被杀死, 应回溯.121killkill121x1= 2x1=1x2= 4182x2= 429x2= 1x2= 2x2= 3x2= 3x3=119132483x3=2killkillkillx3=3x3=4x3=230x4illkillkill31x4=315kill结点18生成结点29, 结点29成为E-结点, 路径变为(2,4);结点29生成结点30, 路径变为(2,4,1)结点30生成结点31, 路径变为(2,4,1,3), 找到一个4-王后问题的可行解11234可行解12123int check_pos_valid(int loop, int value){ int index; int data; for(index = 0; index loop; index ++){ data = gEightQueen[index]; if(