算法分析与设计课件 第5章.ppt

学习要点 理解回溯法的深度优先有哪些信誉好的足球投注网站策略。 掌握用回溯法解题的算法框架 （1）递归回溯最优子结构性质 （2）迭代回溯贪心选择性质 （3）子集树算法框架 （4）排列树算法框架 通过应用范例学习回溯法的设计策略。 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）最大团问题； 迷宫的求解。 问题描述：老鼠走迷宫是心理学中的一个经典试验。问题是这样的，设有一只无盖大箱，箱中设置一些隔壁，形成一些曲曲弯弯的通道，做为迷宫。箱子设有一个入口和出口。实验时，在出口处放一些奶酪之类的可以吸引老鼠的食物，然后将一只老鼠放到入口处，这样，老鼠受到美味的吸引，向出口处走。心理学家就观察老鼠如何由入口到达出口。 这个实验可以用来考察老鼠记忆力的强弱。如果它记忆力很好，那么，在迷宫中对以前尝试过的失败路径就不会再去尝试。 我们的任务是，编写一个计算机程序，模拟老鼠走迷宫。该程序假定老鼠具有稳定记忆力（记为A级假设智能），能记住以前走过的失败路径，而不会重蹈覆辙。如果计算机模拟的走迷宫路径与老鼠的实际走迷宫路径基本吻合，则说明老鼠具有计算机程序的假设智能。当然，如果不吻合，可以改变计算机程序的假设智能，直到其与老鼠的实际轨迹吻合。我们这里只考虑编写模拟A级假设智能的程序。 求解思想：根据我们对老鼠的智能的假设（A级假设智能），老鼠走迷宫的方式为：试探---回溯 尝试---纠错 即每到达一个位置，就试探当前方向是否可行，若可行，则到达下个位置，继续按类似的方法试探；若不可行，有两种情况： ① 当存在下个未尝试的方向时，转下一个方向并按类似方式试探； ② 当不存在下个未尝试的方向时，回退一步，转下个方向并按类似方式试探，若此位置已无下个未尝试的方向，则按类似的方式回退，直到找到未尝试的方向，或退到开始处，而且开始处的各种方向都已尝试过，此时，表示当前解的生成失败。 如此一直进行，直到找到出口，或者所有可能都尝试过。 表示迷宫的数据结构： 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1；其中：0表示通路，1表示不通，当从某点向下试探时，中间点有8个方向可以试探，而四个角点有3个方向，其它边缘点有5个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为8，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 如图表示的迷宫是一个6×8的迷宫。入口坐标为 （1，1），出口坐标为（m，n）。 迷宫的定义如下： #define m 6 /* 迷宫的实际行 */ #define n 8 /* 迷宫的实际列 */ int maze [m+2][n+2] ; 2．试探方向： 在上述表示迷宫的情况下，每个点有8个方向去试探，如当前点的坐标(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素有两个域组成，x：横坐标增量，y：纵坐标增量。move数组如图所示。 Move数组定义如下： typedef struct { int x，y } item ; item move[8] ; 这样对move的设计会很方便地求出从某点 (x，y) 按某一方向v(0≤v≤7) 到达的新点（i，j）的坐标：i=x+move[v].x；j=y+move[v].y； 3．栈的设计： 当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。 栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图迷宫，走的路线为：(1,1)1?(2,2)1?(3,3)0?(3,4)0?(3,5)0?(3,6)0（下脚标表示方向），当从点(3,6)沿方向0到达点(3,7)之后，无路可走，则应回溯，即退回到点(3,6)，对应的操作是出栈