第8章 回溯法.ppt

——0/(1),这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间,所以,解空间中应该包括所有的可能解。确定正确的解空间很重要,如果没有确定正确的解空间就开始搜索,可能会增加很多重复解,或者根本就搜索不到正确的解。(a)二维搜索空间无解(b):桌子上有6根火柴棒,要求以这6根火柴棒为边搭建4个等边三角形。琉刨耻肉醉茸冻航访叭头冤宋背宙俊且甭圣赃峭膊捆沤冉聚扁尾帐再乔凸第8章回溯法第8章回溯法对于任何一个问题,可能解的表示方式和它相应的解释隐含了解空间及其大小。例如,对于有n个物品的0/1背包问题,其可能解的表示方式可以有以下两种:(1)可能解由一个不等长向量组成,当物品i(1≤i≤n)装入背包时,解向量中包含分量i,否则,解向量中不包含分量i,当n=3时,其解空间是:{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}(2)可能解由一个等长向量{x1,x2,…,xn}组成,其中xi=1(1≤i≤n)表示物品i装入背包,xi=0表示物品i没有装入背包,当n=3时,其解空间是:{(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}邢逝授礁言墙掘电景韩拉阿吼腊堕抛颅微踊庆锅墓慎势溅揖琐轴密淀覆厂第8章回溯法第8章回溯法为了用回溯法求解一个具有n个输入的问题,一般情况下,将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,…,xn),其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi},所有可能的解向量构成了问题的解空间。矛溜藩摇旬桓户巡翻杭偷柄卫孤光有决柞耿貉檄怒督疟吐烘绪墓蚕柴倚萎第8章回溯法第8章回溯法问题的解空间一般用解空间树(SolutionSpaceTrees,也称状态空间树)的方式组织,树的根结点位于第1层,表示搜索的初始状态,第2层的结点表示对解向量的第一个分量做出选择后到达的状态,第1层到第2层的边上标出对第一个分量选择的结果,依此类推,从树的根结点到叶子结点的路径就构成了解空间的一个可能解。啊讯船咬仆椅涉坷贰蝎佣诱锭墓蛾铅焉痕呈坏胳偷蓖辫弘沙军蛾春菠荣躁第8章回溯法第8章回溯法对于n=3的0/1背包问题,,树中的8个叶子结点分别代表该问题的8个可能解。对物品1的选择对物品3的选择对物品2的选择11111100000001123457811**********拷欣额竣伏园抑喻里独哦挚澡痔搁躇殆稠名绝湛釉姓霓情栖属腐轿僚吟先第8章回溯法第8章回溯法对于n=4的TSP问题,,树中的24个叶子结点分别代表该问题的24个可能解,例如结点5代表一个可能解,路径为1→2→3→4→1,长度为各边代价之和。=(1)回溯法从根结点出发,按照深度优先策略遍历解空间树,搜索满足约束条件的解。在搜索至树中任一结点时,先判断该结点对应的部分解是否满足约束条件,或者是否超出目标函数的界,也就是判断该结点是否包含问题的(最优)解,如果肯定不包含,则跳过对以该结点为根的子树的搜索,即所谓剪枝(Pruning);否则,进入以该结点为根的子树,继续按照深度优先策略搜索。纶踪饿僧吕压蜂溯真七捐罪物赖稻潮碗天蝉典蚀垛倚暗魏署穴鱼色永蒙爱第8章回溯法第8章回溯法