知识卡片
三角不等式允许捷径
旅行费用满足三角不等式时,直接从u到w的成本不高于经v中转。
由此可在遍历树的行程中跳过重复访问的顶点而不增成本;若费用不满足该性质,这一步近似证明便失效。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第35章 近似算法 · 查看原书依据
Such a cost function c satisfies the triangle inequality: for all vertices u, v, w ∈ V, c(u, w) ≤ c(u, v) + c(v, w). The triangle inequality seems as though it should naturally hold, and it is automatically satisfied in several applications. For example, if the vertices of the graph are points in the plane and the cost of traveling
参考来源
- 位置:《算法导论(第4版)》第35章《近似算法》(OEBPS/chapter035.xhtml,文本字符[10000,15000))。
- 结论依据:第35章近似定义、顶点覆盖与满足三角不等式的旅行商算法;图35.1–35.2已核对。
- 原始内容:Such a cost function c satisfies the triangle inequality : for all vertices u, v, w ∈ V , c ( u, w ) ≤ c ( u, v ) + c ( v, w ). The triangle inequality seems as though it should naturally hold, and it is automatically satisfied in several applications. For example, if the vertices of the graph are points in the plane and the cost of traveling