本文共 2370 字，大约阅读时间需要 7 分钟。

一、前言

• 寻找问题的解的一种可靠的方法：
  • 是首先列出所有候选解，然后逐个，在检查完所有或部分候选解之后，即可找到所需要的解
  • 理论上，只要候选解数量有限，并且在检查了所有或部分候选解之后可以确定所需解。
• 这种方法是可行的。不过在实际应用中，很少使用这种方法， 因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机，也只能对实例规模相当小的问题在合理的时间内解决
• 对候选解进行系统检查的方法有多种，其中“回溯”和“分支定界法”是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大 的问题。
• 本文阐述分支定界方法，回溯法在前面几篇文章已经介绍了
  • 和回溯法一样，分支定界发也经常把解空间组织成树进行搜索。常用的树结构也是回溯法文章中提到的子集树和排列树
  • 与回溯法不同的是，回溯法使用深度优先方法搜索树，而分支定界法一般用广度优先或最小耗费方法来搜索树
• 文本介绍的案例与回溯法文章介绍的案例一样
• 相对而言，分支定界法的空间需求比回溯法要大得多，因此当内存容量有限时，回溯法常常更容易成功

二、支定界算法概述

• 分支定界是另一种系统地搜索解空间的方法

工作原理

• 开始节点即是一个活动节点又是一个E-节点，从E-节点我们试着移到一个新节点
• 它与回溯法的主要区别在于E-节点的扩充方式：
  • 每个活动节点仅有一次机会变成E-节点
  • 当一个节点变为E-节点时，从该节点移动一步即可到达的节点都是生成的新节点
  • 在生成的节点中，那些不可能导出（最优）可行解的节点被舍弃（成为“死”节点），剩余节点加入活动节点表，然后从表中选择一个节点作为下一个E-节点
  • 将选择的节点从表中删除，然后扩展。这种扩展过程一直持续到一个解找到了或活动表成为空表

两种方式选择下一个E-节点

• 方式一：先进先出（FIFO）
  • 从活动节点表中取出节点的顺序与加入节点的顺序相同
  • 活动节点表与队列相同
• 方式二：最小耗费或最大收益法
  • 每个节点都有一个对应的耗费或收益
  • 若搜索的是耗费最小的解，则活动节点表可以组织成小根堆，下一个E-节点是耗费最小的活动节点
  • 若搜索的是耗费最大的解，则活动节点表可以组织成大根堆，下一个E-节点是耗费最大的活动节点
• 当然，可能存在其他的方法

三、实际应用之迷宫老鼠

问题描述

• 在一个矩阵迷宫中，从一个起点开始逐个进行前进与后退，最终找到重点

分支定界法解决

• 假设下图是本次案例的解空间

• 本次案例使用FIFO分支定界选择下一个E-节点，步骤大致为：
  • 初始时（1,1）为E-节点且活动队列为空。然后把（1,1）置为1，以免重回这个位置
  • 然后扩展（1,1），把它的相邻节点（1,2）和（2,1）加入队列（即活动节点表）。为避免重回到这两个位置，将（1,2）和（2,1）置为1。此时迷宫如下图a)所示，而且E-节点（1,1）被舍弃
  • 然后把节点（1,2）从队列中取出，并扩展。检查它的三个相邻节点，只有（1,3）是可行的节点，因此将其加入队列，并把相应位置（1,3）置为1，此时迷宫如下图b)所示，而且E-节点（1,2）被舍弃
  • 然后把节点（2,1）从队列中取出，并扩展，此时可以把节点（3,1）加入队列，并把相应位置（3,1）置为1，节点（2,1）被舍弃，此时迷宫如下图c)所示
  • 此时队列中包含（1,3）和（3,1）两个节点。随后把节点（1,3）变为下一个E-节点，由于此节点不能到达任何新的节点，所以被舍弃。节点（3,1）成为新的E-节点，这时队列已空
  • 然后再把（3,1）变为新的E-节点，这时队列已空
  • 扩展节点（3,1），把（3,2）加入队列，把（3,1）舍弃。（3,2）变为新的E-节点，并扩展。扩展后到达节点（3,3），搜索终止

• 两点备注：
  • 使用FIFO搜索迷宫时，所找到的路径（如果存在的话）一定是从入口到出口的最短路径。而用回溯法找到的路径却不一定是最短路径
  • 有趣的是，我们已经见过用来搜索迷宫的FIFO分支定界代码，在前面一篇文章中，电路布线的最短路径程序便是如此，它利用FIFO分支定界来确定从迷宫的（1,1）到（n,n）的最短路径

四、实际应用之0/背包问题

问题概述

• 有n个物品和一个容量为c的背包。物品i的重量为Wi，价值为p。现在要从n个物品中选出一些物品装入书包中
• 现在的最佳要求是：在装包的物品总重量不超过背包的容量下，使装入的物品总价值最高
• 问题描述是：

• 约束条件是：

• Xi=1表示物品装入背包，Xi=0表示物品没有装入背包

分支定界法解决

待续

五、实际应用之旅行商问题

• 待续

六、定界函数

• 如上面几个案例所示，利用定界函数可以降低解空间树中生成的节点数目。但是设计定界函数时必须记住，我们的主要目的是用最少的时间，在内存允许的范围内去解决问题。生成最少的节点来解决问题并不是我们的根本追求。我们需要的定界函数是以减少生成节点的数量为手段，以最大限度地减少计算时间为目标的定界函数
• 一般来说，在内存利用效率方面，回溯法优于分支定界法。回溯法需要的内存是O(解空间的最长路径长度)，而分支定界需要O()的内存。对于排列空间，回溯需要Θ(n)的内存，分支定界需要O(n!)的空间。虽然最大收益（或最小耗费）分支定界在直觉上要好于回溯法，而且检查的节点也更少，但在实际应用中，在回溯法还没有超出时间的上限之前，分支定界已经超出了内存的上限

七、编码案例（货箱装载）

• 待续

八、编码案例（0/1背包问题）

• 待续

九、编码案例（最单完备子图）

• 待续

十、编码案例（旅行商问题）

• 待续

十一、编码案例（电路板排列）

• 待续

转载地址：https://dongshao.blog.csdn.net/article/details/105821911 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！