15-搜索算法---回溯.ppt

搜索算法---回溯
搜索的本质通用的解题法
一、两种题型:
。对于这一类试题,我们尽量用数学
方法求解。
,或即使有一定的数学模型,但采用数学方法解决有一定困难。对于这一类试题,我们只好用模拟或搜索求解。搜索的策略选择此时特别重要
二、搜索的本质:
搜索的本质就是逐步试探,在试探过程中找到问题的答案
三、搜索问题考察的范围


例1:数字排列问题(全排列)
P1358
《高级本》p3
全排列的另类实现方法(思考)
[算法描述],2……N依次赋给a[1]至a[n],输出第一种排列;,分四步完成:(1) i的初值为1,在a[1]至a[n]中搜索找出相应的i,使i是a[k]>a[k-1]的k中最大的,即i=max{k|a[k]>a[k-1],k=2,3…n};(2) 在a[x]至a[n]中搜索找出相应的j,使j是a[k]>a[i-1]的k中最大的,即j=max{k|a[k]>a[i-1],k=i,i+1…n};(3) 交换a[i-1]与a[j]形成新的序列;(4) 对新的序列从 a[i+1]……a[n]进行逆序处理,输出相应序列.=1时结束
从问题的某种可能情况出发,搜索所有能到达的可能情况,然后以其中一种可能的情况为新的出发点,继续向下探索,当所有可能情况都探索过且都无法到达目标的时候,再回退到上一个出发点,继续探索另一个可能情况,这种不断回头寻找目标的方法称为“回溯法”。
一、回溯的概念
回溯算法是一种有条不紊的搜索问题答案的方法,是一种能避免不必要搜索的穷举式的搜索算法,其基本思想就是穷举搜索。常用于查找问题的解集或符合某些限制条件的最佳解集。
一、回溯的概念
二、回溯的一般描述(竞赛指导p263)
program 程序名;
const maxdepth=xxx;
type statetype=****; {状态类型定义}
var stack:array[1..maxdepth] of statetype; {存当前路径}
total:integer; {路径数}
procedure make(k:integer); {递归搜索以stack[k]为初始接点的所有路径}
var i:integer; {子节点个数}
begin
if stack[k-1]是目标状态 then
begin
total:=total+1;
输出当前路径stack[1]..stack[k-1];
exit; {回溯(如果只需要一条路径,则exit改为halt即可)}}
end;
for i:=算符最小值 to 算符最大值 do
begin
算符i作用于生成stack[k-1]产生子状态stack[k];
if stack[k]满足约束条件 then make(k+1);{若不满足,则通过for循环换一个算符扩展;递归返回该处时,系统自动恢复调用前的栈指针和算符;在通过for 循环换一个算符扩展。注:若在扩展stack[k].state时使用过全局变量,则应插入若干条语句,恢复这些全局变量在递归前的值}
end;
end;
begin
total:=0;
初始化处理;
make(1);{从初始状态出发}
打印路径数total;
end;
二、回溯的一般描述
三、回溯的一般步骤
首先需要为问题定义一个解空间(solution space),这个空间必须至少包含问题的一个解;
然后我们需要组织解空间,以便它能被容易地搜索。典型的组织方法是图或树。
最后对这个空间即可按深度优先的方法从开始节点进行搜索。
例2 皇后问题(p1249)
[问题描述]
在n×n的国际象棋盘上,放置n个皇后,使任何一个皇后都不能吃掉另一个,要使任何一个皇后都不能吃掉另一个,需满足的条件是:同一行、同一列、同一对角线上只能有一个皇后。求放置方法.
如:n=4时,有以下2种放置方法.
*
*
*
*
*
*
*
*
题目来源:《高级本》p5