知识卡片
零干扰不证明频谱数最少
适应度 f(S) 统计相互干扰的顶点落在同一频谱组的冲突数:干扰对 (u,v) 若同组则 δ_uv=1,否则为 0,f 是这些 δ 的总和。f(S)=0 只说明给定 K 个频谱组时分配可行。它不能证明 K 是最少频谱数,因为流程在零冲突时输出当前 K,没有排除更小 K 的可行着色。要声称最少,仍须检查更小 K 或给出下界证明。参见 [[相邻顶点必须异色]] 与 [[跨颜色组移动构造禁忌邻域]]。
示例(补充教学示例,非书中数据):三点一线,只 1–2、2–3 干扰,K=2。方案 A:组1={1,2}、组2={3},同组干扰对 1–2,f=1。方案 B:组1={1,3}、组2={2},1 与 3 无边,f=0,可行。K=1 时三点同组,f=2,不可行。于是 K=2 是本图最小可行数;换一个更密的图,f=0 仍可能发生在大于最小色数的 K 上。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 1 4 . 3 . 2 算 法 实 现 具 体 步 骤 · 查看原书依据
当两个相互干扰的顶点u,v都属于顶点集合Vl时,δuv=1,否则δuv=0。
参考来源
- 位置:《智能算法导论》第 138 项《1 4 . 3 . 2 算 法 实 现 具 体 步 骤》(源文件:`_epub-src/EPUB/xhtml/chapter14_0007.xhtml`;式 δuv 与步骤10)
- 结论依据:原文把同组的干扰顶点计为冲突并以总冲突为适应度;步骤4/10 在零冲突时输出当前 K。整个流程固定 K 再搜,未给出排除更小 K 的检验。三点冲突计数是补充教学示例,非书中数据。
- 原始内容:当两个相互干扰的顶点 u , v 都属于顶点集合 V l 时, δ u v =1,否则 δ u v =0。 f ( S )表示初始解 S 中存在的干扰总和。