计算机算法设计与分析_第七章__1.pdf

《计算机算法设计与分析_第七章__1.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章分枝－限界法12014-11-12第七章分枝－限界法7.1一般方法7.2LC-检索7.315-谜问题7.4LC-检索(续)7.5分枝-限界算法7.60/1背包问题7.7货郎担问题2一般方法基本概念–问题解的n元组表示–问题状态–解状态–答案状态–活结点–E-结点–死结点3一般方法基本概念–回溯法：使用限界函数的深度优先结点生成方法称为回溯法(backtracking)–分枝-限界方法：E结点一直保持到死为止的状态生成方法称为分枝-限界方法(branch-and-bound)–限界函数：在结点的生成过程中，需要用限界函数杀死还没有全部生成儿子结点的

2、一些活结点——这些活结点无法满足限界函数的条件，不可能导致问题的答案。4一般方法分枝-限界法：–在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。–活结点表：活结点：已经被生成，但还没有被检测的结点。存储结构：队列(FirstInFirstOut,BFS)、栈(LastInFirstOut,D-Search)–分枝-限界法的两种设计策略：FIFO检索：活结点表采用队列LIFO检索：活结点表采用栈5例7.14-皇后问题的状态空间树。x1=11x1=4x1=2x1=32183450x=4x=1x=22x

3、=4x=422x=12x=12x=3x=32222x=3x=222x=223813192429354045515661x=3x=2x=231121121123x=4334434333x3=4x=34234691114162022252730323638414346485254575962644342324341314241213231215710121517212326283133373942444749535558606365限界函数：如果(x,x,…,x)是到当前E结点的路径，那么具有父－子标记x12ii+1的所有儿子结点是一些这样的结点，它们使得(x,x,…,x,x)表

4、示没有两个皇后正12ii+1在相互攻击的一种棋盘格局。FIFO分枝－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail112183450扩展结点1，得新结点2，18，34，502183450活结点2、18、34、50入队列x=1x=2x=3x=411117FIFO分枝－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail2x=1118345081312183450扩展结点2，得新结点3，8，13x1=2x1=3x1=4利用限界函数杀死结点33813活结点8、13入队列Bx=3x=422x=228FIFO分枝

5、－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail181345081329x=212183450扩展结点18，得新结点19，24，29利用限界函数杀死结点19、243813192429活结点29入队列BBBx=42x=1x=3229FIFO分枝－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail34508132935扩展结点34，得新结点35，40，45利用限界函数杀死结点40、451活结点35入队列x=3121834503813192429354045BBBx=1BB2x=2x2=4210FIFO分枝

6、－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail5081329355156扩展结点50，得新结点51，56，61利用限界函数杀死结点611活结点51、56入队列x=4218341503813192429354045515661BBBBBx2=1x2=2Bx=32FIFO分枝－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail81329355156扩展结点8，得新结点9，11利用限界函数杀死结点9、111x1=1没有新的活结点入队列2183450x=323813192429354045515661BBB

7、BBB911BBx=2x=43312FIFO分枝－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail132935515614扩展结点13，得新结点14，16利用限界函数杀死结点161x1=1活结点14入队列2183450x=423813192429354045515661BBBBBB9111416BBx=23Bx=3313FIFO分枝－限界法检索4-皇后问题活结点扩展活结点得到的状态活结点表(队列)空间树headtail293551561430扩展结点29，得新结点3