设计 郑宗汉郑晓明 第7章+回溯.ppt

《设计 郑宗汉郑晓明 第7章+回溯.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章回溯法7.1回溯法的思想方法回溯法是一种通过有组织地检查和处理问题实例的解空间,并对解空间进行归约的方法。对于解空间很大的一类问题,这种方法特别有效。实际生活中有很多问题没有有效算法,如TSP。求解这类问题可采用:回溯法(分支限界)、近似算法、随机算法。7.1.1问题的解空间和状态空间树1.解空间问题的解向量:X=(x1,x2,…,xn),xi的所有可能取值的组合称为问题的解空间。例如,n=3时,0/1背包问题的解空间为:{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}输入规模为n时,有2n种可能

2、的解。n=3时,货郎问题的解空间为:{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}输入规模为n时,有n!种可能解。2.状态空间树问题的解空间可以用树的形式表示,这种树称为状态空间树。n=4时,货郎问题的状态空间树如下:货郎问题的状态空间树为排列树:n!个叶结点,n!种可能的解遍历排列树需(n!)的计算时间。n=4时,0/1背包问题的状态空间树如下:0/1背包问题的状态空间树为子集树:2n个叶结点,2n种可能的解遍历子集树需(2n)的计算时间。7.1.2状态空间树的动态搜索1.可行解和最优解可行解:满足约束条件的解。{解空间的一个

3、子集}最优解:使目标函数取极值(极大或极小)的可行解。{1个或少数几个}例如,0/1背包问题有2n种可能解,其中一些是可行解,只有1个或几个是最优解。再如,货郎问题有nn种可能解,其中n!种可行解,只有1个或几个是最优解。有些问题只要可行解,不需最优解。如八皇后问题、图着色问题。2.状态空间树的动态搜索穷举法对整个状态空间树中的所有可能解进行搜索,但只有满足约束条件的解才是可行解,只有满足目标函数的解才是最优解。这就有可能使需要搜索的空间大为压缩。从根结点出发沿子结点向下搜索。若它和子结点的边所记的分量xi满足约束条件和目标函数的界,则把xi加入到部分解中,并继续向下搜索;若它和子结

4、点的边所记的分量xi不满足约束条件和目标函数的界,则结束对以子结点为根的整棵子树的搜索,选择另一子结点进行搜索。搜索过程中的结点分为三类:l_结点(活结点):所搜索到的结点不是叶结点,且满足约束条件和目标函数的界,其儿子结点还未全部搜索完毕;e_结点(扩展结点):正在搜索其儿子结点的结点,它也是一个l_结点.d_结点(死结点):不满足约束条件或目标函数的结点;其儿子结点已搜索完毕的结点;叶结点。以d_结点为根的子树可在搜索过程中删除。例7.1有4个顶点的货郎问题（有向赋权图）,其费用矩阵如图所示,求从顶点1出发最后回到顶点1的最短路线。7.1.3回溯法的一般性描述问题的解向量:X=(

5、x0,x1,…,xn-1)xi的取值范围为Si,Si=(ai,0,ai,1,…,ai,mi)故解空间为笛卡尔积A=S0S1…Sn-1状态空间树可看成为一棵高度为n的树:第0层:

6、S0

7、=m0个分支结点,构成m0棵子树,每棵子树有

8、S1

9、=m1个分支结点;第1层:m0m1个分支结点,m0m1棵子树;第n-1层:m0m1…mn-1个叶结点回溯法的一般步骤:初始化,令解向量X为空;从根结点出发,在第0层选择S0的第一个元素a0,0作为解向量X的第一个元素,即置x0=a0,0;若X=(x0)是部分解,则该结点是l_结点,也是e_结点,选择S1的第一个元素a1,0作为X的第二个元

10、素,即置x1=a1,0;(4)若X=(x0,x1)是部分解,则该结点是l_结点,也是e_结点,置x2=a2,0;若X=(x0,x1)不是部分解,则该结点是d_结点,舍弃以该结点为根的子树,取S1的下一元素a1,1作为X的第二个元素,即x1=a1,1。以此类推。一般地,若已检测到X=(x0,x1,…,xi)是问题的部分解,在把xi+1=ai+1,0扩展到X时,有以下三种情况:若X=(x0,x1,…,xi+1)是最终解,则把它作为有效解保存。若只需一个解,则结束,否则继续搜索其它有效解;若X=(x0,x1,…,xi+1)是部分解,则令xi+2=ai+2,0,继续搜索其下层子树;(3)若X

11、=(x0,x1,…,xi+1)既不是最终解,也不是部分解,则有下述两种情况:a.若xi+1=ai+1,k不是Si+1的最后元素,则令xi+1=ai+1,k+1,继续搜索其兄弟子树;b.若xi+1=ai+1,k是Si+1的最后元素,则回溯到X=(x0,x1,…,xi)的情况。若此时xi=ai,k不是Si的最后元素,则令xi=ai,k+1,搜索上一层兄弟子树;若此时xi=ai,k是Si的最后元素,则继续回溯到X=(x0,x1,…,xi-1)。用m[i]表示集合