分支限界法——对解空间的一种策略搜索(广度优先搜索)
发布网友
发布时间：2023-03-28 18:12
共1个回答
热心网友
时间：2023-11-19 23:27
将顶点编号为0, 1, ..., n-1.
每个结点包含如下信息：
u——该节点所对应的顶点
path[n]——从源点开始的路径上的顶点编号
k——当前搜索深度下，路径上的顶点个数
d——从源点到本节点所对应顶点的路径长度
b——经本节点到目标顶点最短路径的长度下界
bound——一个可行解的取值，当做剪枝的标准
假定源顶点为s，目标顶点为t。
假定n个商品重量分别为w0, w1, ..., wn-1，价值分别为p0, p1, ..., pn-1，背包载重量为M。怎样选择商品组合，使得价值最高？
每个结点都包含如下信息：
S1——当前选择装入背包的商品集合
S2——当前不选择装入背包的商品集合
S3——当前尚待选择的商品集合
k——搜索深度
b——上界
bound——一个可行解的取值，当做剪枝的标准
每个结点包含如下信息：
m——已分配作业的操作员编号集合
S——未分配作业的操作员编号集合
x——操作的分配方案向量x，分量xi表示分配给第i位操作员的作业编号。
k——搜索深度（表示分配的第k号作业）
t——所需时间的下界
bound——一个可行解的取值，当做剪枝的标准
考虑如图所示的4个操作员的作业最优分配方案
每个结点包含如下信息：
c——归约过后的费用矩阵
k——费用矩阵的阶数
w——下界
ad——顶点邻接表
bound——一个可行解的取值，当做剪枝的标准
