搜索与回溯算法.doc

搜索与回溯算法 回溯算法? ? 2 一、回溯法的思想? ? 2 二、实现要点? ? 2 三、应用举例? ? 2 【例1】马的遍历? ? 2 【例2】选书? ? 5 四、回溯典型例子? ? 7 【例1】八皇后问题? ? 7 【例2】骑士遍历问题? ? 12 五、递归中体现回溯? ? 15 【例1】走迷宫问题? ? 15 搜索算法? ? 19 一、深度优先搜索? ? 19 二、广度优先搜索? ? 29 回溯算法 一、回溯法的思想 在求解一些问题（如走迷宫、地图着色等问题）时，题目的要求可能是求出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状态所构成的，每一步骤又有若干种可能的决策方案；由于没有固定、明确的数学解析方法，往往要采用搜索的做法，即从某一个初始状态出发，不断地向前（即下一个状态）搜索，以期最终达到目标状态，从而得到原问题的一个解或所有的解。在搜索的过程中，由于问题本身及所采取的搜索方法的特点（如在缺乏全局及足够的前瞻信息的情况下进行搜索等），会导致走到某一状态就走不下去的情况，这时，就必须回头（即回到上一步，而不是回到最初的状态），再尝试其他的可能性，换一个方向或方法再试试。这样，不断地向前探索、回溯，再向前、再回溯，直至最终得出问题的解，或者一路回溯到出发点（出现这种情况即表示原问题无解）。注意，这种搜索过程并不是尝试搜索问题解空间中所有的可能状态和路径，而是采用深度优先的方式，沿着一条路径，尽可能深入地向前探索。 二、实现要点 由于回溯法是一种搜索方法，而且是一种深度优先式的搜索算法，在搜索过程中，前进和回退交织进行，因而，必须有适当的手段和机制来已经走过的状态，以便在发生回溯时能够回退到上一步，再选择与上一步不同的方向继续探索下去。要满足回溯过程中对状态进行记录的要求，最好的数据结构便是堆栈了，它与回溯时只回退到上一步非常吻合。（在具体实现时，栈又可以采用数组、链表等结构来实现。）此外，还要有适当的数据结构来表示整个问题的可能解空间，以及在每一步（每一状态）时可能的选择。 在理解和把握回溯法时，首先要能够手工地理解和模拟在搜索过程中，实际的前进和后退的过程，真正以人工的方式想通实际发生的前进-回退过程。然后，在编制程序时，就象递归算法一样，从较为宏观而自然的层面上，来表达出这种不断进-退的过程，即可构造出有效的回溯算法。 在回溯算法中，把握好何时发生回溯（即发生回溯的条件）是非常关键的，应注意有效而正确地表达回溯条件。还要注意，原问题的状态空间、每一步可能的行动方案、记录已走过的所有步骤的数据结构等，都是非常关键的。 此外，从本质上看，回溯算法符合递归算法，问题的解决可以转化为子问题，其子问题的解法与原问题相同，只是数据增大或减少；因此，在实现回溯算法时，又常常可以考虑采用递归算法来实现，这时，算法中所涉及的堆栈等数据结构就由系统来维护了。 三、应用举例 回溯法可以用来解决一系列问题，如自然数的排列、n皇后问题、迷宫问题、数的拆分、0/1背包问题、旅行商问题、货船装货问题、图形覆盖正方形等。 【例1】马的遍历 中国象棋半张棋盘如图1（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图中所示为一种跳行路线，并将所经路线打印出来。 打印格式为：0,0->2,1->3,3->1,4->3,5->2,7->4,8? 14 （14表示第十四种路线，场宽为5） 【算法分析】 如图马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为： 1: （i,j）→（i+2,j+1）；? (i<3,j<8) 2: （i,j）→（i+1,j+2）；? (i<4,j<7) 3: （i,j）→（i-1,j+2）；? (i>0,j<7) 4: （i,j）→（i-2,j+1）；? (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点； S3:打印路径。 【算法设计】 procedure try(i:integer);? ? {搜索} var j:integer; begin for j:=1 to 4 do? {试遍4 个方向} if 新坐标满足条件 then begin 记录新坐标; if 到达目的地 then? print {统计方案，输出结果} else try(i+1);? ? {试探下一步} 退回到上一个坐标，即回溯; end; end; 【参考程序】 program exam1; {递归+回溯} const x:array[1..4,1..2] of integer=((2,1),(1,2),(-1,2),(-2,1)); {四种移动