实验四 单源最短路径问题一、实验目的:1、 理解分支限界法的剪枝搜索策略;2、 掌握分支限界法的算法柜架;3、 掌握分支限界法的算法步骤;4、 通过应用范例学习动态规划算法的设计技巧与策略;二、 实验内容及要求:1、使用分支限界法解决单源最短路径问题。2、通过上机实验进行算法实现。3、保存和打印出程序的运行结果,并结合程序进行分析,上交实验报告。三、实验原理:分支限界法的基本思想:1、分支限界法与回溯法的不同:1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想:分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,