此卡片不在当前主题的阅读序列中,可返回主题继续阅读。
知识卡片
背包退火邻域增删物品
0-1 背包的退火邻域任选物品 i,再按它是否已在包中产生新解:
- i 不在包中:把它放入,或者放入的同时随机取出另一件 j。
- i 已在包中:把它取出,并同时随机装入另一件 j。
加入会增加重量与价值,交换则按两件物品的差更新。超重候选是否保留还要由约束接受规则决定。原书公式把部分变量写成 x(x),故这里只保留文字明确的操作含义。
补充教学示例(非书中数据)。当前装 {1,2},重量 5、价值 9。选中不在包中的物品 3(重量 4、价值 6)且不取出其他件,新重量 9、新价值 15。
结构图:
flowchart TD
A[选择物品 i] --> B{ i 当前在包中? }
B -- 否 --> C[加入 i]
C --> D{同时移除物品 j?}
D -- 否 --> E[重量与价值增加 i 的贡献]
D -- 是 --> F[重量与价值按 i 减 j 更新]
B -- 是 --> G[移除 i 并加入另一物品 j]
G --> H[重量与价值按 j 减 i 更新]
E --> I[形成候选邻居]
F --> I
H --> I
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 1 . 5 . 1 基 于 模 拟 退 火 算 法 的 0 - 1 背 包 问 题 · 查看原书依据
若物品i不在背包中,则将其放入背包中,或者同时从背包中随机取出任一物品j;若物品i在背包中,则将其取出,并同时随机装入另一物品j。
参考来源
- 位置:《智能算法导论》第 118 项《11.5.1 基于模拟退火算法的0-1背包问题》(源文件:`_epub-src/EPUB/xhtml/chapter11_0013.xhtml`;式 11-5、11-6)
- 结论依据:正文按物品是否已在背包中分别说明直接加入、加入并移除另一件,或移除并加入另一件;式 11-5、11-6 按相同分支定义重量和价值变化。{1,2} 加物品 3 为依据该邻域补充的教学示例,非书中数据。
- 原始内容:若物品 i 不在背包中,则将其放入背包中,或者同时从背包中随机取出任一物品 j;若物品 i 在背包中,则将其取出,并同时随机装入另一物品 j。