知识卡片

结构图卡 · 3765

背包退火邻域增删物品

理解等级:中级

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 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 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。