搜索方法学习教案

1、会计学1搜索搜索(su su)方法方法第一页，共44页。第2页/共44页第二页，共44页。第3页/共44页第三页，共44页。第4页/共44页第四页，共44页。第5页/共44页第五页，共44页。第6页/共44页第六页，共44页。第7页/共44页第七页，共44页。第8页/共44页第八页，共44页。第9页/共44页第九页，共44页。这个结构是普遍适用(shyng)的。任何递归的DFS程序都能套进去。第10页/共44页第十页，共44页。第11页/共44页第十一页，共44页。输入输入(shr)：4 7 4 4 3 2 2 1 1输出：输出：Sums of 4:43+12+22+1+1输入(shr)：5

2、3 2 1 1输出：Sums of 5:NONE第12页/共44页第十二页，共44页。4041-1取4不取4取34不取3取21不取2-1取21不取20取11不取10取11不取1输入：4 6 4 3 2 2 1 1搜索树如下：第13页/共44页第十三页，共44页。输入输入(shr)：madamadamm 输出输出(shch)：i i i i o o o i o oi i i i o o o o i oi i o i o i o i o oi i o i o i o o i o 第14页/共44页第十四页，共44页。输入输入(shr)：68输出：输出：Case 1:1 4 3 2 5 61 6 5

3、 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2第15页/共44页第十五页，共44页。输入输入(shr)：1210200输出输出(shch)：NNONONPNOPNPONONPNOPNPONOPNONPNOP第16页/共44页第十六页，共44页。V3V2V4V1V6V5广度优先(yuxin)遍历V3V2V4V1V6V5第17页/共44页第十七页，共44页。这个结构是普遍适用的。任何(rnh)非递归的BFS程序都能套进去。第18页/共44页第十八页，共44页。V3V2V4V1V6V5给图定义(dng

4、y)邻接矩阵int G66：0 1 0 1 1 11 0 1 1 0 00 1 0 1 1 11 1 1 0 0 11 0 1 0 0 11 0 1 1 1 0第19页/共44页第十九页，共44页。v10V1队列结点记录两个(lin )信息1：顶点编号2：步数第20页/共44页第二十页，共44页。v10V1第21页/共44页第二十一页，共44页。v10V1v10第22页/共44页第二十二页，共44页。v10V1v10V1不是(b shi)终点第23页/共44页第二十三页，共44页。v10V2V4V1V6V5v21v41v51v61v10第24页/共44页第二十四页，共44页。v10V2V4V1

5、V6V5v21v41v51v61第25页/共44页第二十五页，共44页。v10V2V4V1V6V5v21v41v51v61v21第26页/共44页第二十六页，共44页。v10V2V4V1V6V5v21v41v51v61V2不是(b shi)终点v21第27页/共44页第二十七页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32v21第28页/共44页第二十八页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32第29页/共44页第二十九页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32v41第30页/共44页第三十页，共44页。

6、v10V2V4V1V6V5v21v41v51v61V3v32v41V4不是(b shi)终点第31页/共44页第三十一页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32v41第32页/共44页第三十二页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32v51第33页/共44页第三十三页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32v61第34页/共44页第三十四页，共44页。v10V2V4V1V6V5v21v41v51v61V3v32v32第35页/共44页第三十五页，共44页。v10V2V4V1V6V5v21v41v51

7、v61V3v32v32V3是终点，结束搜索(su su)，输出2第36页/共44页第三十六页，共44页。第37页/共44页第三十七页，共44页。输入输入(shr)：a1 h8输出：输出：To get from a1 to h8 takes 6 knight moves. a b c d e f g h12345678h8a1第38页/共44页第三十八页，共44页。输入(shr)：24 717 5 -21 154 517 5 -21 15输出(shch)：Divisible Not divisible第39页/共44页第三十九页，共44页。输入输入(shr)：5 6 44 14 23 23 13

8、2 33 33 40 0 0输出输出(shch)：Case 1: 9第40页/共44页第四十页，共44页。输入输入(shr)：3 3 41 21 33 21 21 32 13 22 1 22 11 11 20 0 0输出输出(shch)：Villa #1The problem can be solved in 6 steps:- Switch on light in room 2.- Switch on light in room 3.- Move to room 2.- Switch off light in room 1.- Move to room 3.- Switch off light in room 2.Villa #2The problem cannot be solved.第41页/共44页第四十一页，共44页。4 5