湘潭大学算法设计与分析第五章回溯法

《湘潭大学算法设计与分析第五章回溯法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章回溯法2021/7/291计算机算法设计与分析用计算机求解问题问题空间现实求解过程实际解状态空间对象的定义机器求解过程算法与程序的设计机内解2021/7/292计算机算法设计与分析计算机求解的过程在状态空间寻找机内解可以看成是从初始状态出发搜索目标状态(解所在的状态)的过程。状态空间初始状态目标状态搜索搜索的过程可描述为：S0S1…Sn，其中S0为初态，Sn为终态。或者说ψ(S0)且φ(Sn)，这里ψ称为初始条件，φ称为终止条件。2021/7/293计算机算法设计与分析求解是状态空间的搜索求解的过程可以描述为对

2、状态空间的搜索S0S11S12…S1k………………Sn1……Sni……Snm其中S0为初始状态，不妨设Sni为终止状态S0Sni于是问题的求解就是通过搜索寻找出一条从初始状态S0到终止状态Sni的路径。2021/7/294计算机算法设计与分析几种搜索方法状态空间的搜索实际上是一种树的搜索，常用的方法有：广度优先的搜索深度优先的搜索启发式的搜索从初始状态开始，逐层地进行搜索。从初始状态开始，逐个分枝地进行搜索。从初始状态开始，每次选择最有可能达到终止状态的结点进行搜索。2021/7/295计算机算法设计与分析三种搜索的优劣之

3、处一般来说，三种搜索方法各有优劣之处：广度优先搜索的优点是一定能找到解；缺点是空间复杂性和时间复杂性都大。深度优先搜索的优点是空间复杂性和时间复杂性较小；缺点是不一定能找到解。启发式搜索是最好优先的搜索，优点是一般来说能较快地找到解，即其时间复杂性更小；缺点是需要设计一个评价函数，并且评价函数的优劣决定了启发式搜索的优劣。2021/7/296计算机算法设计与分析树搜索的一般形式SearchTree(SpaceT)//表L用来存放待考察的结点{unfinish=true;L=T.initial;//unfinish表示搜索未

4、结束，先将初始状态放入Lwhile(unfinish

5、

6、L≠Φ){a=L.first;//从L中取出第一个元素if(aisgoal)unfinish=false//若a是终态则结束elseControl-put-in(L,Sons(a));}//否则，将a的儿子们以某种控制方式放入L中2021/7/297计算机算法设计与分析三种搜索的不同之处树的三种搜索方法的不同就在于它们对表L使用了不同控制方式：L是一个队列L是一个栈L的元素按照某方式排序广度优先搜索深度优先搜索启发式搜索其中，深度优先搜索就是回溯法。2021/7/29

7、8计算机算法设计与分析回溯法的形式化描述假设能够用n元组（x1,x2,…,xn）表示一个给定的问题P的解，其中xi∈集合Si；n元组的子组（x1,x2,…,xi）（i

8、x1,x2,…,xi’）并判断其是否满足约束条件。如此反复下去，直到得到解或者证明无解为止。2021/7/299计算机算法设计与分析递归回溯法的一般形式Try(s){做挑选候选者的准备；while(未成功且还有候选者){挑选下一个候选者next；if(next可接受){记录next；if(满足成功条件){成功并输出结果}elseTry(s+1);if(不成功)删去next的记录;}}return成功与否}2021/7/2910计算机算法设计与分析迭代回溯法的一般形式先让我们回顾解空间搜索的一般形式：SearchTree(S

9、paceT)//表L用来存放待考察的结点{unfinish=true;L=T.initial;//unfinish表示搜索未结束，先将初始状态放入Lwhile(unfinish

10、

11、L≠Φ){a=L.first;//从L中取出第一个元素if(aisgoal)finish=false//若a是终态则结束elseControl-put-in(L,Sons(a));}//否则，将a的儿子们以某种控制方式放入L中回溯法中表L为栈，将初始状态压入栈中。弹出栈顶元素在通常求解问题时，解是由逐个状态构成的。因此，这里还需要判断状态是否可接

12、受，并进行纪录路径等工作。如果a可接收但未终止，则要将a的后继压入栈中。如果要抛弃状态a，当a是最后一个儿子时，还需要消除原有纪录甚至回溯一步。2021/7/2911计算机算法设计与分析如何判断最后一个儿子？若只要遍历解空间树上的结点，那么将各个结点按栈的方式控制便可实现深度为主的搜索。但是在求解问题时