深度、广度和双向搜索优化及其应用.ppt

1、搜索,深度优先搜索 广度优先搜索,枚举,划分解的存在范围 对范围内的元素进行逐一判断 例：求出AI 分别对应的数字(19) 使得下式成立,ABCD E FGHI,枚举解法,枚举ABCDE的值，计算乘积，判断是否符合要求。,搜索复杂的、高级的枚举,枚举: 解空间中的每个元素是一个动作(action)的集合F 将初态S0变换为另一个状态F(S0) F中各动作的执行顺序不影响F(S0) 如果F(S0)是符合要求的S*, 那么F是真解, 否则是伪解,搜索复杂的、高级的枚举,搜索: 解空间的每个元素是一个动作的序列F 将初态S0变换为另一个状态F(S0) 如果F(S0)是符合要求的S*, 那么F是真解,

2、 否则是伪解 有一个规则, 确定在每个状态S下,分别有哪些动作可供选择 采用递归的办法, 产生每个动作序列,搜索,有顺序有策略地产生解空间的元素 每个解空间的元素表现为一定动作的执行轨迹(trace of actions) 采用递归的策略产生解空间的元素，出口条件 轨迹已经达到终点：真解、或者伪解 轨迹不可能导出真解,搜索的过程,两个状态的集合 : 未处理完的状态 : 已处理的状态 状态的处理: 有顺序的尝试备选动作, 每一次的尝试都演化出另一个状态 已处理的状态: 全部备选动作都已经尝试 一个树结构: 状态之间的演化关系 递归的出口 为空 演化出目标状态S* 演化出的状态不属于,影响搜索效率

3、的因素,两个状态的集合 : 未处理完的状态 : 已处理的状态 判重：每次演化出一个状态s时，s是否属于或者 剪枝：状态s的任意演化结果是否都属于 属于，则剪枝 演化出来的状态数量：的大小,深度优先搜索,两个状态的集合 : 未处理完的状态 : 已处理的状态 从中选择被演化状态的原则：离初态S0最远的状态s S0到s的距离：从S0到达s使用的动作数量 实现方法：用stack表示 每次取stack顶部的状态演化 每次演化出的状态s若不属于，则s将压入stack的顶部,POJ1011 木棒问题,问题描述： 乔治拿来一组等长的棍子，将它们随机地裁断（截断后的小段称为木棒），使得每一节木棒的长度都不超过5

4、0个长度单位。然后他又想把这些木棒恢复到为裁截前的状态，但忘记了棍子的初始长度。 请你设计一个程序，帮助乔治计算棍子的可能最小长度。每一节木棒的长度都用大于零的整数表示,输入输出,输入数据 由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，是零。 输出要求 为每个案例，分别输出木棒的可能最小长度，每个案例占一行。 输入样例 9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0 输出样例 6 5,解题思路,初始状态：有N节木棒 最终状态：这N节木棒恰好被拼接成若干根等长的棍子(裁前

5、的东西称为棍子） 注意：棍子长度未知 枚举什么？ 枚举所有有可能的棍子长度。 从最长的那根木棒的长度一直枚举到木棒长度总和的一半。 对每个假设的棍子长度试试看能否拼齐所有棍子：枚举长度是否可以整除棍子总长。,解题思路,在拼接过程中，要给用过的木棒做上标记，以免重复使用 回溯：拼好前i根棍子，结果发现第i+1根拼不成了，那么就要推翻第i根的拼法，重拼第i根.直至有可能推翻第1根棍子的拼法,解题思路,搜索题，首先要解决一个问题：按什么顺序搜索？ 把木棒按长度排序。每次选木棒的时候都尽量先选长的。 因为短木棒比较容易用来填补空缺。一根长木棒，当然比总和相同的几根短木棒要优先使用,Dfs递归搜索函数,

6、Bool Dfs(int nUnusedSticks, int nLeft ) ; Function dfs(nUnusedSticks:longint, nLeft:longint):longint 表示: 当前有nUnusedSticks根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度短了nLeft, 那么在这种情况下能否全部拼成功。,Dfs的基本递推关系：,boolDfs(int nUnusedSticks, int nLeft) . if( nLeft = 0 ) /一根刚刚拼完 nLeft := L; /开始拼新的一根 找一根长度不超过nLeft的木棒（假设长为len）拼在当前棍

7、子上，然后 exit Dfs(nUnusedSticks 1, nLeft len ); ,Dfs的终止条件之一：,boolDfs(int nUnusedSticks, int nLeft ) if( nUnusedSticks = 0 and nLeft = 0 ) exit true; if( nLeft = 0 ) /一根刚刚拼完 nLeft := L; /开始拼新的一根 找一根长度不超过nLeft的木棒（假设长为len）拼在当前棍子上，然后 exit Dfs(nUnusedSticks 1, nLeft len )； ,解题思路,搜索题，还要解决一个问题：如何剪枝 就本题而言，即尽可能

8、快地发现一根拼好的棍子需要被拆掉，以及尽量少做结果不能成功的尝试。,剪枝1,每次开始拼第i根棍子的时候，必定选剩下的木棒里最长的一根，作为该棍子的第一根木棒。 即:就算由于以后的拼接失败，需要重新调整第i根棍子的拚法，也不会考虑替换第i根棍子中的第一根木棒（换了也没用）。如果在此情况下怎么都无法成功，那么就要推翻第i-1根棍子的拚法。如果不存在第i-1根棍子，那么就推翻本次假设的棍子长度，尝试下一个长度,剪枝1,为什么替换第i根棍子的第一根木棒是没用的？ 因为假设替换后能全部拼成功，那么这被换下来的第一根木棒，必然会出现在以后拼好的某根棍子k中。那么我们原先拼第i根棍子时, 就可以用和棍子k同

9、样的构成法来拼，照这种构成法拼好第i根棍子，继续下去最终也应该能够全部拼成功。,剪枝2,不要希望通过仅仅替换已拼好棍子的最后一根木棒就能够改变失败的局面。,剪枝2,让我们考虑接下来的两种策略，一是用更长的木棍来代替当前木棍，显然这样总长度会超过原始木棍的长度，违法。二是用更短的木棍组合来代替这根木棍，他们的 总长恰好是当前木棍的长度，但是由于这些替代木棍在后面的搜索中无法得到合法解，当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替 代木棍也能做到。所以，当出现加上某根木棍恰好能填满一根原始木棍，但由在后面的搜索中失败了，就不必考虑其他木棍了，直接退出当前的枚举。,剪枝3,如

10、果某次拼接选择长度为L1的木棒，导致最终失败，则在同一位置尝试下一根木棒时，要跳过所有长度为L1的木棒。,小结,构造一条木棒长度为L的“路径”：拼接木棒 在未被拼接的木棒中，找出一节最长的，开始拼接 从未拼接的木棒中，选择一个长度合适的木棒，使得拼接后的木棒长度L 找到了 若在前面的拼接过程中曾试图用过相同长度的一节其他木棒，但发现这样拼接不成功，继续寻找能够进行拼接的木棒 /剪枝3 把找到的那节木棒拼接上去。继续进行拼接 继续拼接成功，找到了“路径” 继续拼接不成功，把刚拼接的那节木棒拿下来，继续找下一个合适的未拼接木棒 /剪枝2、1 没有找到：拼接失败,问题,是否还有新的剪枝策略，以进一步

11、加速搜索过程？,剪枝 4,拼每一根棍子的时候，应该确保已经拼好的部分，长度是从长到短排列的 由于取木棒是从长到短的，所以如果长得在前，短的在后不可行的话，那么相反的一定不可行,POJ1020-Anniversary Cake,有一块边长为BoxSize的正方形的大蛋糕，现在给出n块不同尺寸的正方形的小蛋糕的边长，问是否能把大蛋糕按恰好切割为这n块小蛋糕，要求每块小蛋糕必须为整块。 Max_n=16，Max_size=10，大蛋糕最大40*40 如何确定搜索策略,解题思路,首先确定搜索顺序 依然是从大到小搜索，因为小的灵活性较高 放置蛋糕时遵从从上到下，从左到右的原则,难点,本题的难点不在于如何

12、找到搜索策略 难点是如何记录当前的状态 最简单的方法是将整个盒子分割成1*1的小块分别记录是否被占据 但是，这必然是会超时的,按列记录,我们定义一个数组col 记录当前列 从上到下一共连续放了多少的蛋糕 例如在第24列放入了一个size=3的小蛋糕，那么inc(col2,3), inc(col3,3), inc(col4,3) 我们的搜索顺序保证了底部先填满的原则，如果悬空，则回溯,Functin dfs(t:longint):boolean Begin If (t=n+1) exit(true); P:=1;num:=0; For i:=1 to size do if (colisize-c

13、olp) num=size-colp; For i:=num downto 1 do if (ai0) Begin dec(ai); For j:=p to p+i-1 do inc(colj,i); If (dfs(t+1) exit(true); For j:=p to p+i-1 do dec(colj,i); Inc(ai); End; End.,广度优先搜索,广度优先搜索也称为宽度优先搜索，它是一种先生成的节点先扩展的策略。适合于判定是否有解和求唯一解的情况 搜索过程是：从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。 假设有两个表：Op

14、en表存放待处理节点，Closed表存放处理完节点 Open表中的节点总是按进入的先后排序，先进入Open表的节点排在前面，后进入Open表的节点排在后面。,广度优先搜索,两个状态的集合 : 未处理完的状态 : 已处理的状态 从中选择被演化状态的原则：离初态S0距离最近的状态s S0到s的距离：从S0到达s使用的动作数量 实现方法：用queue表示 每次取queue头部的状态演化 每次演化出的状态s若不属于，则s将压入queue的尾部,深搜 vs. 广搜,深搜 1-2-4-8-5-6-3-7 广搜 1-2-3-4-5-6-7-8,广搜算法,广度优先搜索算法如下：（用 QUEUE） (1) 把初

15、始节点S0放入Open表中； (2) 如果Open表为空，则问题无解，失败退出； (3) 把Open表的第一个节点取出放入Closed表，并记该节点为n； (4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出； (5) 若节点n不可扩展，则转第(2)步； (6) 扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。,POJ1077八数码问题,八数码问题是人工智能中的经典问题 POJ1077八数码问题：经典搜索问题 有一个3*3的棋盘，其中有0-8共9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态到达目标状态1 2 34

16、5 67 8 0的步数最少的解？,广度优先搜索（bfs） 优先扩展浅层节点，逐渐深入,广度优先搜索 用队列保存待扩展的节点，从队首队取出节点，扩展出的新节点放入队尾，直到找到目标节点（问题的解）,广度优先搜索的代码框架,BFS() 初始化队列 while(队列不为空且未找到目标节点) 取队首节点扩展，并将扩展出的节点放入队尾； 必要时要记住每个节点的父节点； ,判重,新扩展出的节点如果和以前扩展出的节点相同，则这个新节点就不必再考虑 如何判重？,判重,合理编码，减小存储代价 不同的编码方式所需要的存储空间会有较大差别 需要考虑的问题 状态数目巨大，如何存储？ 怎样才能较快的找到重复节点,为节点

17、编号 把每个节点都看一个排列，以此排列在全部排列中的位置作为其编号 排列总数：9!=362880 只需要一个整数(4字节)即可存下一个节点 一个boolean标志数组flag 记录当前状态是否重复 判重用的标志数组只需要362,880字节即可。 此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。,时空,时间与空间的权衡 对于状态数较小的问题，可以用最直接的方式编码以空间换时间 对于状态数太大的问题，需要利用好的编码方法以时间换空间 具体问题具体分析,用广搜解决八数码问题,输入数据： 2 3 4 1 5 x 7 6 8 输出结

18、果： ullddrurdllurdruldr 移动序列中 u 表示使空格上移 d 表示使空格下移 r 表示使空格右移 l 表示使空格左移,设一个362880位字符型标志位序列数组szFlag，标识每个状态是否已扩展 设一个队列MyQueue存放搜索过程中的可能状态，根据问题定义，状态总数362880。考虑到搜索过程中可能存在的重复状态，其大小设为400000。 为简化计算，设置与MyQueue同样大小的数组anFather存放父节点指针、数组szMoves存放从父节点到当前节点的移动步骤 设置一个结果队列，为防止溢出，设置与MyQueue同样大小,关键处理逻辑,Main程序1.将输入的原始字符

19、串变为九进制字符串;2.用BFS过程看是否可以达到目标状态;,BFS中的关键问题：1）如何进行状态扩展？2）状态中0的位置与cMove动作间的关系？3）如何计算求从nStatus经过 cMove 移动后得到的新状态（定义为函数NewStatus ）？4）如何判断扩展标记已经存在？5）对未扩展状态，如何置已扩展标记(定义为函数SetBit )？6）字符串形式的9进制数到其整型值的互相转换函数（定义为NineToTen和TenToNine）,问题,8数码问题的有解性判定 如果所有结点都扩展完还没有达到目标状态，则问题无解，失败退出 是否有更节省存储空间的做法，例如可以不用几个大数组？ 一种可能方案

20、：使用2个链表分别存队列和结果,用深度优先搜索求解8数码问题,基本思想：优先深入遍历靠前的节点,用深度优先搜索求解8数码问题,参考代码 与前述BFS为同一架构 深度受限的情况下（如最大深度为20）：可能处理时间较长，且不一定能找到解,度量问题求解的性能,完备性：当问题有解时，这个算法是否能够保证找到一个解 最优性：这个搜索策略是否能够找到最优解 时间复杂度：找到一个解需要花费多长时间 空间复杂度：在执行搜索的过程中需要多少内存,广搜与深搜的比较,广搜一般用于状态表示比较简单、求最优策略的问题 优点：是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短

21、的解。 缺点：盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大 深搜几乎可以用于任何问题 只需要保存从起始状态到当前状态路径上的节点 根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择,更快的做法,双向广度优先搜索：从两个方向以广度优先的顺序同时扩展 A*：启发式搜索搜索,双向广度优先搜索(DBFS),DBFS算法是对BFS算法的一种扩展。 BFS算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点 DBFS算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩

22、展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。 比较 DBFS算法相对于BFS算法来说，由于采用了从两个跟开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！,A*算法,针对八数码问题，提出了人工智能史上很有名的A*算法(启发式搜索算法) 广度优先算法：当目标的深度较深时，产生很多冗余节点，空间消耗很大 有限深度优先算法：在时间或空间复杂度上均没有明显的优势，但如果目标深度较深而且路径选择得当的话，可以较快地得到解答；当问题复杂时时间消耗很多 A*算法：可以消耗较少的空间解决问题，但是由

23、于每次选择均需要寻找估价函数最小的节点，因此当深度增加相应的节点数目增加时，A*算法在时间上并不占优势。然而，A*算法总可以在有限的时间内得到问题的解。,A*算法的基本思想,A*算法基本上与BFS算法相同，但是在扩展出一结点后，要根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 估价函数： f(n) = g(n) + h(n) 这里f(n)是估价函数，g(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h(n)是n到目标的最短路经的启发值。,A*算法的基本步骤,建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 取出队列头（队

24、列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 检查扩展的新结点是否与队列中的结点重复 若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃； 若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针 如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。,BFS vs. DBFS vs. A*,B

25、FS算法只能适用于到达目标结点步数较少的情况，如果步数超过15步，运行时间太长。 对于随机生成的同一个可解状态，BFS算法最慢，A*算法较快。但在15步以内，DBFS算法与A*算法相差时间不大，超过15步后，随步数增加，A*算法的优势就逐渐明显，A*算法要比DBFS算法快5倍以上，并随步数增大而增大。到25步以上，DBFS同样因运行时间过长而失去价值。 一般来说，解答的移动步数每增加1，程序运行时间就要增加5倍以上。由于八数码问题本身的特点，需要检查的节点随步数增大呈指数形式增加，即使用A*算法，也难解决移动步数更多的问题。,小结：影响搜索效率的因素,影响搜索效率的因素 搜索对象(枚举什么）

26、搜索顺序（先枚举什么，后枚举什么） BFS：广度优先 DFS：深度优先 A*：估价函数最小优先 剪枝(及早判断出不符合要求的情况）,【noip2003】传染病控制,【问题背景】 近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO（世界卫生组织）以及全球各国科研部门的努力，这种新兴传染病的传播途径和控制方法已经研究消楚，剩下的任务就是由你协助蓬莱

27、国疾控中心制定一个有效的控制办法。,【noip2003】传染病控制,研究表明，这种传染病的传播具有两种很特殊的性质；第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不得病，或者是XY之间的传播途径被切断，则X就不会得病。第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一代患者，而不会再传播给下一代。这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就

28、会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序。,【noip2003】传染病控制,【输入格式】 输入格式的第一行是两个整数n（1n300）和p。接下来p行，每一行有两个整数i和j，表示节点i和j间有边相连（意即，第i人和第j人之间有传播途径相连）。其中节点1是已经被感染的患者。 【输出格式】 只有一行，输出总共被感染的人数。,【noip2003】传染病控制,先将题中的树形结构利用DFS

29、构造出来 按层进行搜索，枚举每一层控制哪一个人 超时,【noip2003】传染病控制,只需要加上一个最优性剪枝即可 先贪心一个解 一旦已死亡人数超过当前最优解，结束,整数拆分,整数N拆分成比不大于N的有多少种拆分.如6的拆分,有11种,罗列如下6 6 5+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1,整数拆分,根据上面的规律可抽象出, f(n, m), n表示要被拆分的数,m表示要拆分成的数的范围,及f(n,m) 表示要将n,拆分成由不大于m的数的情况,f(6,4)表示上面有下划线的情况. 情况1:

30、n = 1, 或者m = 1时只有一种情况, 1+1的情况 情况2:n = 0, 或者m = 0时,没有存在拆分 情况3:n = m,找到规律f(n,m) = f(n,m-1)+f(n-m,m);,记忆化搜索,有的题目搜索的状态时可以记录的 我们可以用数组记录下已经搜索过的状态 这种方法就是记忆化搜索,滑雪,Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 1

31、6 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9,滑雪,dfs(x,y)为以x,y为起点,最长的路线 dfs(x,y)只与相邻是个点有关,滑雪,dfs( x, y):longint if (fxy0) return 0; if (x0)and(axyax-1y) dfs(x-1,y); if (fx-1yfxy) fxy=fx-1y; if (y0)and(axyaxy-1) dfs(x,y-1); if (fxy-1fxy) fxy=fxy-1; if (xax+1y) dfs(x+1,y); if (fx+1yfxy) fxy=f

32、x+1y; if (yaxy+1) dfs(x,y+1); if (fxy+1fxy) fxy=fxy+1; inc(fxy); if (fxyans) ans=fxy; return 0; ,邮票面值设计,给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+k=40) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大max ，使得1 max之间的每一个邮资值都能得到。 例如，N=3，K2，如果面值分别为1分、4分，则在l分-6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分-7分之间的每一个邮资值都能得到。可以验证当

33、N=3，K2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。,邮票面值设计,这是一道经典的搜索与动态规划结合的题目。 解题两个步骤： 设计出n张邮票的组合 对这个组合进行dp，求出最大的连续可能贴出的邮票更新答案。,邮票面值设计,关键就是如何进行搜索与动态规划的结合。 我们可以想到，由于最多只能有k种面值，这样就可以以第几种为搜索参数，dfs第i种。如果i大于k，证明已经达到k种，这样便进行dp，更新答案；反之若不够k种，便要搜索第k+1种，注意第k+1种有一个范围，min和max，很显然min=ai-1+1,max的计算要用到dp过程，max即是前i-1种能达到的

34、连续最大值+1，即dp（i-1)+1。,马的遍历问题,在的棋盘中，马只能走日字。马从位置(x,y)处出发，把 棋盘的每一格都走一次，且只走一次。找出所有路径。,const n=5;m=4; fx:array1.8,1.2of -2.2=(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1), (-2,1),(-1,2); 八个方向增量 var dep,i:byte; x,y:byte; cont:integer; 统计总数 a:array1.n,1.mof byte; 记录走法数组 procedure output; 输出,并统计总数 var x,y:byte; b

35、egin cont:=cont+1; writeln; writeln(count=,cont); for y:=1 to n do begin for x:=1 to m do write(ay,x:3); writeln; end; readln; halt; end;,procedure find(y,x,dep:byte); var i,xx,yy:integer; begin for i:=1 to 8 do begin xx:=x+fxi,1;yy:=y+fxi,2; 加上方向增量,形成新的坐标 if (xx in 1.m)and(yy in 1.n)and(ayy,xx=0) t

36、hen 判断新坐标是否出界,是否已走过? begin ayy,xx:=dep; 走向新的坐标 if (dep=n*m) then output else find(yy,xx,dep+1); 从新坐标出发,递归下一层 ayy,xx:=0 回溯,恢复未走标志 end; end; end; begin cont:=0; fillchar(a,sizeof(a),0); dep:=1; writeln(input y,x);readln(y,x); x:=1;y:=1; if (yn) or(xm) then begin writeln(x,y error!);halt;end; ay,x:=1;

37、find(y,x,2); if cont=0 then writeln(No answer!) else write(The End!); readln; end.,在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何,const n=4; var k,u,v,result:integer; a:array1.n,1.nof char; procedure printf; 输出 begin result:=result+1;方案总数加1 writeln(- ,result, -); for v:=1 to n do begin for u:=1 to n do write(au,v);

38、 writeln end; writeln; end; begin 主程序 fillchar(a,sizeof(a), ); 记录放置情况的字符数组,初始值为空格 result:=0; k:=0; k记录已放的块数,如果k=n*n/2,则说明已放满 try; 每找到一个空位置,把长条块分别横放和竖放试验 end.,procedure try; 填放长条块 var i,j,x,y:integer; full:boolean; begin full:=true; if ktrunc(n*n/2) then full:=false;测试是否已放满 if full then printf; 放满则可输

39、出 if not full then begin 未满 x:=0;y:=1; 以下先搜索未放置的第一个空位置 repeat x:=x+1; if xn then begin x:=1;y:=y+1 end until ax,y= ; 找到后,分两种情况讨论 if ax+1,y= then begin 第一种情况:横向放置长条块 k:=k+1;记录已放的长条数 ax,y:=chr(k+ord(); 放置 ax+1,y:=chr(k+ord(); try;递归找下一个空位置放 k:=k-1; ax,y:= ; 回溯,恢复原状 ax+1,y:= end; if ax,y+1= then begin 第二种情况:竖向放置长条块 k:=k+1; 记录已放的长条数 ax,y:=chr(k+ord(0); 放置 ax,y+1:=chr(k+ord(0); try; 递归找下一个空位置放 k:=k-1; ax,y:= ; 回溯,恢复原状 ax,y+1:= end; end; end;,找迷宫的最短路径,uses crt; const migong:array 1.5,1.5 o