回溯法 ppt课件.ppt

第五章回溯法
2018/7/29
计算机算法设计与分析
1
用计算机求解问题
问题空间
现实求解过程
实际解
状态空间
对象的定义
机器求解过程
算法与程序的设计
机内解
2018/7/29
计算机算法设计与分析
2
计算机求解的过程
在状态空间寻找机内解可以看成是从初始状态出发搜索目标状态(解所在的状态)的过程。
状态空间
初始状态
目标状态
搜索
搜索的过程可描述为:S0S1…Sn,其中S0为初态,Sn为终态。或者说ψ(S0)且φ(Sn),这里ψ称为初始条件,φ称为终止条件。
2018/7/29
计算机算法设计与分析
3
求解是状态空间的搜索
求解的过程可以描述为对状态空间的搜索
S0
S11
S12
…
S1k
……
……
……
Sn1
……
Sni
……
Snm
其中S0为初始状态,不妨设Sni为
终止状态
S0
Sni
于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。
2018/7/29
计算机算法设计与分析
4
几种搜索方法
状态空间的搜索实际上是一种树的搜索,常用的方法有:
广度优先的搜索
深度优先的搜索
启发式的搜索
从初始状态开始,逐层地进行搜索。
从初始状态开始,逐个分枝地进行搜索。
从初始状态开始,每次选择最有可能达到终止状态的结点进行搜索。
2018/7/29
计算机算法设计与分析
5
三种搜索的优劣之处
一般来说,三种搜索方法各有优劣之处:
广度优先搜索的优点是一定能找到解;缺点是空间复杂性和时间复杂性都大。
深度优先搜索的优点是空间复杂性和时间复杂性较小;缺点是不一定能找到解。
启发式搜索是最好优先的搜索,优点是一般来说能较快地找到解,即其时间复杂性更小;缺点是需要设计一个评价函数,并且评价函数的优劣决定了启发式搜索的优劣。
2018/7/29
计算机算法设计与分析
6
树搜索的一般形式
SearchTree(Space T)//表L用来存放待考察的结点
{unfinish = true; L = ;
// unfinish表示搜索未结束,先将初始状态放入L
while (unfinish || L≠Φ) {
a = ; //从L中取出第一个元素
if (a is goal) unfinish = false //若a是终态则结束
else Control-put-in(L, Sons(a));
} //否则,将a的儿子们以某种控制方式放入L中
2018/7/29
计算机算法设计与分析
7
三种搜索的不同之处
树的三种搜索方法的不同就在于它们对表L使用了不同控制方式:
L是一个队列
L是一个栈
L的元素按照某方式排序
广度优先搜索
深度优先搜索
启发式搜索
其中,深度优先搜索就是回溯法。
2018/7/29
计算机算法设计与分析
8
回溯法的形式化描述
假设能够用n元组(x1,x2,…,xn)表示一个给定的问题P的解,其中xi∈集合Si;n元组的子组( x1,x2,…,xi )(i<n),如果它满足一定的约束条件,则称为部分解。
如果它已经是满足约束条件的部分解,则添加xi+1∈Si+1形成新的子组( x1,x2,…,xi ,xi+1 )并检查它是否满足约束条件,若满足则继续添加xi+2∈Si+2,并以此类推。如果所有的xi+1∈Si+1都不满足约束条件,那么去掉xi+1,回溯到xi的位置,并去掉当前的xi,另选一个xi’∈Si,组成新的子组( x1,x2,…,xi’)并判断其是否满足约束条件。
如此反复下去,直到得到解或者证明无解为止。
2018/7/29
计算机算法设计与分析
9
递归回溯法的一般形式
Try(s){
做挑选候选者的准备;
while (未成功且还有候选者) {
挑选下一个候选者next;
if (next可接受) {
记录next;
if (满足成功条件) {成功并输出结果}
else Try(s+1);
if (不成功) 删去next的记录; }}
return 成功与否}
2018/7/29
计算机算法设计与分析
10