深度优先搜索与回溯算法.ppt

深度优先搜索与回溯算法
回溯是计算机解题中常用的算法,很多问题无法根据某种
确定的计算法则来求解,可以利用搜索与回溯的技术求解。回溯
是搜索算法中的一种控制策略。它的基本思想是:为了求得问题
的解,先选择某一种可能情况向前探索,在探索过程中,一旦发
现原来的选择是错误的,就退回一步重新选择,继续向前探索,
如此反复进行,直至得到解或证明无解。
如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步
步向前试探前进如果碰到死胡同,说明前进方向已无路可走,
这时,首先看其它方向是否还有路可走,如果有路可走,则沿该
方向再向前试探;如果已无路可走,则返回一步,再看其它方向
是否还有路可走;如果有路可走,则沿该方向再向前试探。按此
原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口
处无解为止。
回溯法算法框架
Procedure dfs(s)∥访间状态s
Begin
if边界 then begin
判断是否为目标状态;exit;
en
fori:=状态变换规则数
begin
si=S+规则
保存局面
dfs (si)
还原局面
end
End
【例1】设有n个整数的集合
1,2,n},从中取出任意r个数
(r<n),试列出所有的可能的情况
例如[1,2,3},r=2。那么有3种可能,
(1,2),(1,3),(2,3)
【例2】任何一个大于1的自然数n,总可以拆分成若干个小于n
的自然数之和
当n=7共14种拆分方法:
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
【例3】素数环:从1到n(<=20)这n个数摆成一个
环,要求相邻的两个数的和是一个素数。
【算法分析】
非常明显,这是一道回溯的题目。从1开始,每个空位有20
种可能,只要填进去的数合法:与前面的数不相同;与左边
相邻的数的和是一个素数。第20个数还要判断和第1个数的
和是否素数
【例4】八皇后问题:要在国际象棋棋盘中放八个皇
后,使任意两个皇后都不能互相吃。(提示:皇后
能吃同一行、同一列、同一对角线的任意棋子。)
2345678
2345678
【例5】马的遍历
中国象棋半张棋盘如图4(a)所示。马自左下
角往右上角跳。今规定只许往右跳,不许往左跳。比
如图4(a)中所示为一种跳行路线,并将所经路线打
印出来。打印格式为:0,0->2,1->3,3->1,4->3,5
>2,7->4,8
()2
012345678
(a)
例6】数的划分NoP2001)
问题描述】
将整数n分成k份,且每份不能为空,任意两种分法不能相同
(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5;1,5,1;5,1,1:
问有多少种不同的分法。
【输入格式】
nk(6<n≤200,2≤k≤6)
【输出格式】
个整数,即不同的分法。
输入样例】
【输出样例】
4
4种分法为:1,1,5;1,2,4;1,3,3;2,2,3说明部分不必输出}
【例7】跳马问题。在5*5格的棋盘上,有一只
中国象棋的马,从(1,1)点出发,按日字跳
马,它可以朝8个方向跳,但不允许出界或跳
到已跳过的格子上,要求在跳遍整个棋盘
输出前5个方案及总方案数。
输出格式示例:
116211025
2011241522
1721969
12742314
3181385