分支与限界：货物装载问题VIP免费

第1页共16页分支与限界：货物装载问题课程名称：**************院系：************************学生姓名：******学号：************专业班级：*****************************指导教师：*******2013年12月27日第2页共16页分支与限界：货物装载问题摘要：在现实生活中，我们会经常遇见货物装载问题，如何解决货物装载问题，获取利润的最大化，花费最少的而得到更多的东西，是人们一直都要考虑的问题。在广泛的解决问题中，人们一般采用分支限界算法解决这样的问题。分支限界法是由分支策略和限界策略两部分组成的。分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。分支策略体现在对问题空间是按广度优先的策略进行搜索，限界策略是为了加速搜索速度而采用启发信息剪枝的策略。在分支限界法，经常采用的是分支搜索法，分支搜索法是一种在问题空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略，依次搜索E-结点的所有的分支，也就是所有的相邻结点。和回溯法一样，在生成的节点中，抛弃那些不满足的约束条件的的结点，其余结点加入活结点表。在分支搜索的算法中，人们经常会采用FIFO搜索和优先队列式搜索。例题中采用的是轮船装载的问题，这是一个非常经典的分支限界算法的例题，通过这个例子的学习，将会理解并掌握分支限界货物装载的问题。关键词：分支限界法货物装载FIFO分支限界优先队列分支限界第3页共16页目录第一章绪论.............................................41.1分支-界限算法的基本思想............................41.2常见的两种分支界限算法.............................4第二章货物装载问题.....................................52.1问题描述..........................................52.2问题分析.........................................5第三章优先队列式分支限界法解决货物装载问题..............63.1算法设计..........................................63.2数据结构设计......................................73.2.1程序流程图....................................73.2.2数据结构描述.................................73.2.3重要算法.....................................83.3测试结果与分析....................................9第四章基于队列式(FIFO)分支限界法解决货物装载问题.......104.1算法设计.........................................104.2数据结构设计.....................................104.2.1程序流程图...................................114.2.2数据结构描述和算法..........................114.3测试结果与分析...................................13第五章结论.............................................14参考文献................................................15第4页共16页第一章绪论1.1分支-界限算法的基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。1.2常见的两种分支...