(精品)第五章2 图的搜索算法.ppt

《(精品)第五章2 图的搜索算法.ppt》由会员分享，可在线阅读，更多相关《(精品)第五章2 图的搜索算法.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章图的搜索算法图的搜索算法5 55 5 分支限界法分支限界法 5 55 51 1 分枝搜索算法分枝搜索算法 5 55 52 2 分枝分枝-限界搜索算法限界搜索算法 5 55 53 3 算法框架算法框架5 56 6 图的搜索算法小结图的搜索算法小结 5 55 51 1 分枝搜索算法分枝搜索算法 1 1基本思想基本思想 分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓“分支分支”是采用广度优先的策略，依次生成是采用广度优先的策略，依次生成E-结点所有分支，也就结点所有分支，也就是所有的儿子结点。和回溯法一样，在生成的节点中，抛弃

2、那些不是所有的儿子结点。和回溯法一样，在生成的节点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点，其余节点满足约束条件（或者说不可能导出最优可行解）的结点，其余节点加入活节点表。然后从表中选择一个节点作为下一个加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择节点。选择下一个下一个E-节点的方式不同导致几种不同的分支搜索方式：节点的方式不同导致几种不同的分支搜索方式：1FIFO搜索 2LIFO搜索 3优先队列式搜索 上一页 下一页 返回首页 5.5.2 5.5.3 5.6552分枝分枝-限界搜索算限界搜索算法法 【例【例2】有两艘船，有两艘船，n n 个货箱。第一艘船

3、的载重量是个货箱。第一艘船的载重量是c1c1，第二艘第二艘船的载重量是船的载重量是c2c2，wi wi 是货箱是货箱i i 的重量的重量,且且 w 1+w2+wnc1+c2c1+c2。我们希望确定是否有一种可将所有我们希望确定是否有一种可将所有n n 个货箱全部装船的方法。若有个货箱全部装船的方法。若有的话，找出该方法的话，找出该方法 FIFO限界搜索算法限界搜索算法优先队列式分支限界法优先队列式分支限界法上一页 下一页 返回首页 5.5.1 5.5.3 5.6MaxLoadingMaxLoading(c1);(c1);if(s-if(s-bestw bestw=c2);=c2);print(

4、print(“The first ship loadingThe first ship loading”,bestw bestw，“chosechose：”););for(i=1;i=n;i+)for(i=1;i=n;i+)if(if(bestxbestxi=1i=1)print(i print(i，“，”););print(print(“换换行符行符 The second ship loadingThe second ship loading”,s-,s-bestwbestw,“chosechose”););for(i=1;i=n;i+)for(i=1;i 30+50=80 bestwbes

5、tw，也入队；也入队；3 3）结点结点B B变为变为E-E-结点扩充结点扩充D D入队，入队，bestwbestw=40=40；结点结点E E的装载上界为的装载上界为60 60 bestwbestw，也入队；也入队；4 4）结点结点C C变为变为E-E-结点扩充结点扩充F F入队，入队，bestwbestw仍为仍为4040；结点结点G G的装载上界为的装载上界为50 50 bestwbestw，也入队；也入队；5 5）结点结点D D变为变为E-E-结点，叶结点结点，叶结点H H超过容量，超过容量，叶结点叶结点I I的装载为的装载为4040，bestwbestw仍为仍为4040；6 6）结点结点

6、E E变为变为E-E-结点，叶结点结点，叶结点J J装载量为装载量为6060，bestwbestw为为6060；叶结点叶结点K K被剪掉；被剪掉；7 7）结点结点F F变为变为E-E-结点，叶结点结点，叶结点L L超过容量，超过容量，bestwbestw为为6060；叶结点叶结点M M被剪掉；被剪掉；8 8）结点结点G G变为变为E-E-结点，叶结点结点，叶结点N N、O O都被剪掉；都被剪掉；此时队列空算法结束。此时队列空算法结束。LC-LC-搜索的过程如下：搜索的过程如下：1 1）初始队列中只有结点初始队列中只有结点A A；2 2）结点结点A A变为变为E-E-结点扩充结点扩充B B入堆，

7、入堆，bestwbestw=10=10；结点结点C C的装载上界为的装载上界为30+50=80 30+50=80 bestwbestw，也入堆；堆中也入堆；堆中B B上界为上界为9090在优先队列首。在优先队列首。3 3）结点结点B B变为变为E-E-结点扩充结点扩充D D入堆，入堆，bestwbestw=40=40；结点结点E E的装载上界为的装载上界为60 60 bestwbestw，也入堆；此时堆中也入堆；此时堆中D D上界为上界为9090为优先队列首。为优先队列首。4 4）结点结点D D变为变为E-E-结点，叶结点结点，叶结点H H超过容量，叶结点超过容量，叶结点I I的装载为的装载为

8、4040入堆，入堆，bestw bestw仍为仍为4040；此时堆中；此时堆中C C上界为上界为8080为优先队列首。为优先队列首。5 5）结点结点C C变为变为E-E-结点扩充结点扩充F F入堆，入堆，bestwbestw仍为仍为4040；结点结点G G的装载上界为的装载上界为50 50 bestwbestw，也入堆；此时堆中也入堆；此时堆中E E上界为上界为6060为优先队列首。为优先队列首。6 6）结点结点E E变为变为E-E-结点，叶结点结点，叶结点J J装载量为装载量为6060入堆，入堆，bestwbestw变为变为6060；叶结点叶结点K K上界为上界为1010bestwbestw

9、被剪掉；此时堆中被剪掉；此时堆中J J上界为上界为6060为优先队列首。为优先队列首。7 7）结点结点J J变为变为E-E-结点，扩展的层次为结点，扩展的层次为4 4算法结束。算法结束。虽然此时堆并不空，但可以确定已找到了最优解。虽然此时堆并不空，但可以确定已找到了最优解。上一页 下一页 返回首页 5.5.1 5.5.3 5.6FIFO限限界界算算法法搜搜索索解解空空间间的的过过程程是是按按图图5-26子子集集树树中中字字母母序序进进行的，而行的，而优优先先队队列限界搜索解空列限界搜索解空间间的的过过程是：程是：A-B-D-C-E-J看看了了上上面面的的例例子子大大家家会会发发现现，优优先先队

10、队列列法法扩扩展展结结点点的的过过程程，一开始一开始实际实际是在是在进进行行类类似似“深度深度优优先先”的搜索。的搜索。553算法框架算法框架 上上一一小小节节的的例例子子是是求求最最大大值值的的最最优优化化问问题题，下下面面我我们们以以求求找找最小成本的最优化问题，给出最小成本的最优化问题，给出FIFO分支搜索算法框架。分支搜索算法框架。假假定定问问题题解解空空间间树树为为T，T至至少少包包含含一一个个解解结结点点（即即答答案案结结点点）。u为为当当前前的的最最优优解解，初初值值为为一一个个较较大大的的数数;E表表示示当当前前扩扩展展的的活活结结点点，x为为E的的儿儿子子，s(x)为为结结点

11、点x下下界界函函数数，当当其其值值比比u大大时时，不不可可能能为为最最优优解解，不不继继续续搜搜索索此此分分支支，该该结结点点不不入入队队；当当其其值值比比u小小时时，可可能能达达到到最最优优解解，继继续续搜搜索索此此分分支支，该该结结点点入入队队；cost（X）为当前叶结点所在分支的解。为当前叶结点所在分支的解。算法框架如下：算法框架如下：上一页上一页 下一页下一页 返回首页返回首页 5.5.15.5.1 5.5.25.5.2 5.65.62 2）：）：上一页 下一页 返回首页 5.5.1 5.5.2 5.6search（T）/为找出最小成本答案结点检索为找出最小成本答案结点检索T。leaf

12、=0;初始化队；初始化队；ADDQ（T）；）；/根结点入队根结点入队 parent（E）=0；/记录扩展路径，当前结点的父结点记录扩展路径，当前结点的父结点while（队不空）队不空）DELETEQ(E)/队首结点出队为新的队首结点出队为新的E结点；结点；for（E的每个儿子的每个儿子X）if(s（X）u)/当是可能的最优解时入队当是可能的最优解时入队ADDQ（X）；）；parent（X）=E;if(X是解结点是解结点)/x为叶结点为叶结点U=min（cost（X），），u）;leaf=x;/方案的叶结点存储在方案的叶结点存储在leaf中中3 3）：）：上一页 下一页 返回首页 5.5.1 5

13、.5.2 5.6print（”leastcost=，u）；）；while（leaf0）/输出最优解方案输出最优解方案print（leaf）；）；leaf=parent（leaf）；）；找找最最小小成成本本的的LC分分支支-限限界界算算法法框框架架与与F FIFO分分支支-限限界界算算法法框框架架结结构构大大致致相相同同，只只是是扩扩展展结结点点的的顺顺序序不不同同，因因而而存存储储活活结结点点的的数数据据结结构构不不同同。F FIFO分分支支-限限界界算算法法用用队队存存储储活活结结点点，LC分分支支-限限界界算算法法用用堆堆存存储储活活结结点点，以以保保证证比比较较优优良良的的结结点点先先被

14、被扩扩展展。且且对对于于LC分分支支-限限界界算算法法，一一当当扩扩展展到到叶叶结结点点就就已已经经找到最优解，可以停止搜索。找到最优解，可以停止搜索。56图的搜索算法小结图的搜索算法小结1 1深度优先搜索与广度优先搜索算法有何区别深度优先搜索与广度优先搜索算法有何区别 通常深度优先搜索法不全部保留结点，扩展完的结点从数据存通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，空间树的深度，因此它占用空间较少。所以，当搜

15、索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。解方法。广度优先搜索算法，一般需存储产生的所有结点，占用的存储广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。栈和出栈的操作，所以运行速度比深度优先搜索要快些。上一页 下一

16、页 返回首页 5.52.2.2 2回溯与分支限界法回溯与分支限界法 回溯法以深度优先的方式搜索解空间树回溯法以深度优先的方式搜索解空间树T T，而分支限界法则而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树以广度优先或以最小耗费优先的方式搜索解空间树T T。由于它由于它们们在在问题问题的解空的解空间树间树T上搜索的方法不同，适合解决的上搜索的方法不同，适合解决的问题问题也也就不同。一般情况下，回溯法的求解目就不同。一般情况下，回溯法的求解目标标是找出是找出T中中满满足足约约束束条件的所有解的方案，而分支限界法的求解目条件的所有解的方案，而分支限界法的求解目标则标则是找出是找出满满足足

17、约约束条件的一个解，或是在束条件的一个解，或是在满满足足约约束条件的解中找出使用束条件的解中找出使用某一目某一目标标函数函数值值达到极大或极小的解，即在某种意达到极大或极小的解，即在某种意义义下的最下的最优优解。解。相对而言，分支限界算法的解空间比回溯法大得多，相对而言，分支限界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。因此当内存容量有限时，回溯法成功的可能性更大。下表列出了回溯法和分支限界法的一些区下表列出了回溯法和分支限界法的一些区别别：上一页 下一页 返回首页 5.53 3.上一页 下一页 返回首页 5.54 4.在在处处理理最最优优问问题题时时，采采用用

18、穷穷举举法法、回回溯溯法法或或分分支支限限界界法法都都可可以以通通过过利利用用当当前前最最优优解解和和上上界界函函数数加加速速。仅仅就就对对限限界界剪剪支支的的效效率率而而言言，优优先先队队列列的的分分支支限限界界法法显显然然要要更更充充分分一一些些。在在穷穷举举法法中中通通过过上上界界函函数数与与当当前前情情况况下下函函数数值值的的比比较较可可以以直直接接略略过过不不合合要要求求的的情情况况而而省省去去了了更更进进一一步步的的枚枚举举和和判判断断；回回溯溯法法则则因因为为层层次次的的划划分分，可可以以在在上上界界函函数数值值小小于于当当前前最最优优解解时时，剪剪去去以以该该结结点点为为根根的

19、的子子树树，也也就就是是节节省省了了搜搜索索范范围围；分分支支限限界界法法在在这这方方面面除除了了可可以以做做到到回回溯溯法法能能做做到到的的之之外外，同同时时若若采采用用优优先先队队列列的的分分支支限限界界法法，用用上上界界函函数数作作为为活活结结点点的的优优先先级级，一一旦旦有有叶叶结结点点成成为为当当前前扩扩展展结结点点，就就意意味味着着该该叶叶结结点点所所对对应应的的解解即即为为最最优优解解，可可以以立立即即终终止止其其余余的的过过程程。在在前前面面的的例例题题中中曾曾说说明明，优优先先队队列列的的分分支支限限界界法法更更象象是是有有选选择择、有目的地有目的地进进行深度行深度优优先搜索

20、，先搜索，时间时间效率、空效率、空间间效率都是比效率都是比较较高的。高的。上一页 下一页 返回首页 5.55 5.3动态规动态规划与搜索算法划与搜索算法撇撇开开时时空空效效率率的的因因素素不不谈谈，在在解解决决最最优优化化问问题题的的算算法法中中，搜搜索索可可以以说说是是“万万能能”的的。所所以以动动态态规规划划可可以以解解决决的的问问题题，搜搜索索也也一一定定可可以以解解决决。动动态态规规划划要要求求阶阶段段决决策策具具有有无无后后向向性性，而而搜搜索索算算法法没没有此限止。有此限止。动动态态规规划划是是自自底底向向上上的的递递推推求求解解，而而无无论论深深度度优优先先搜搜索索或或广广度度优

21、优先先搜搜索索都都是是自自顶顶向向下下求求解解。利利用用动动态态规规划划法法进进行行算算法法设设计计时时，设设计计者者在在进进行行算算法法设设计计前前已已经经用用大大脑脑自自己己构构造造好好了了问问题题的的解解空空间间，因因此此可可以以自自底底向向上上的的递递推推求求解解；而而搜搜索索算算法法是是在在搜搜索索过过程程中中根根据据一一定定规规则则自自动动构构造造，并并搜搜索索解解空空间间树树的的。由由于于在在很很多多情情况况下下，问问题题的的解解空空间间太太复复杂杂用用大大脑脑构构造造有有一一定定困困难难，仍仍然然需需要要采采用用搜搜索索算算法。法。上一页 下一页 返回首页 5.5 另外动态规划

22、在递推求解过程中，需要另外动态规划在递推求解过程中，需要用数组存储有关信息，用数组存储有关信息，而数组的下标只能是整数，所以要求问题中相关的数据必须为而数组的下标只能是整数，所以要求问题中相关的数据必须为整数（如整数（如4.5.3节节【例【例2】“资源分配问题资源分配问题”中的资金就必须为中的资金就必须为整整数），对于这类信息非整数或不便于转换为整数的问题，同样数），对于这类信息非整数或不便于转换为整数的问题，同样需要采用搜索算法需要采用搜索算法。一般说来，动态规划算法在时间效率上的优势是搜索无法比一般说来，动态规划算法在时间效率上的优势是搜索无法比拟的，但动态规划总要遍历所有的状态，而搜索可

23、以排除一些拟的，但动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。如何协的状态，因此在空间开销上往往比动态规划要低很多。如何协调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的调好动态规划的高效率与高消费之间的矛盾呢？有一种折衷的办法就是记忆化搜索算法办法就是记忆化搜索算法 记忆化限界搜索算法在求解时，还是按着自顶向下的顺序，记忆化限界搜索算法在求解时，还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这但是每求

24、解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。记忆化限界态规划两方面的优点，因而还是很有实用价值的。记忆化限界搜索。它以搜索算法为核心，只不过使用搜索。它以搜索算法为核心，只不过使用“记录求过的状态记录求过的状态”的办法，来避免重复搜索，这样，记忆化搜索的每一步，也可的办法，来避免重复搜索，这样，记忆化搜索的每一步，也可以对应到动态规划算法中去。记忆化搜索有优化方便、调试容以对应到动态规划算法中去。记忆化搜索有优化方便、调试容易、思维直观的优点，但是效率上比循环的动态规划差一个常易、思维直观的优点，但是效率上比循环的动态规划差一个常数，但是时间和空间复杂度是同一数量级的（尽管空间上也差数，但是时间和空间复杂度是同一数量级的（尽管空间上也差一个常数，那就是堆栈空间）。当一个常数，那就是堆栈空间）。当n比较小的时候，我们可以忽比较小的时候，我们可以忽略这个常数，从而记忆化搜索可以和动态规划达到完全相同的略这个常数，从而记忆化搜索可以和动态规划达到完全相同的效果。效果。