分支限界

mac2025-02-11  14

分支限界及其应用

组合优化问题 组合优化问题的相关概念、 目标函数(极大化或极小化) 约束条件(解满足的条件) 可行解:搜素空间满足约束条件的解 最优解:使得目标函数达到极大(或极小)的可行解 代价函数 计算位置:搜索树的节点 值:极大化问题是以该点为根的子树所有可行解的值的上界 性质:对极大化问题父节点代价不小于子节点的代价(极小化问题相反) 界 含义:当前得到可行解的目标函数的最大值 初值:极大化问题初值为0(极小化问题为最大值) 更新:得到更好的可行解时 F的值>=B

分支限界

停止分支回溯父节点的依据: 1.不满足约束条件 2.对于极大化问题,代价函数值小于当前界(对于极小化问题是大于界) 界的更新: 对极大化问题,如果一个新的可行解的优化函数值大于(极小化问题为小于)当前的界,则把界更新为该可行解。 有4种物品,重量和价值已知,背包的重量限制为10. 求得是每个物品应该拿多少

对节点<x1,x2,x3…xk>,估计以该节点为根得子树中可行解得上界按vi/wi,从小到大排序,i=1,2,3,…n代价函数=已经装价值+▲ ▲:还可继续装入最大价值得上界 ▲ =背包剩余容量*vk+1/wk+1(可装) ▲=0(不可装)

*

最新回复(0)