知识卡片
图优化先确定代价与可行约束
权可表示边的时间、距离、费用等可比较代价,但应先定义优化目标。最小生成树优化连接全部顶点的总边权,最短路径优化特定源到目标的路径和,旅行商优化访问各点并回起点的回路,三者不是同一问题。
管线最小连接是生成树模型的典型近似,但实际容量、冗余、可靠性、方向和必须多次访问等约束未必包含在树或一次遍历模型里。不能因为一个应用名出现,就推断书中算法已解决其全部现实要求。
本章带权状态复用11章Graph遍历机制,正确建模还需要确认边的方向与权值前提,不能把所有路径问题都限定有向图或所有权都默认非负。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
带权图。在一个带权图中,每条边都可能附带一个值或权,这些权用一个小的数字标记在边上。虽然很多条件因素都可以作为权值,但通常它表示遍历这条边所产生的代价。带权图和其算法可以用来对很多的实际问题进行建模。示例16-1是本章所介绍的图算法的头文件。 本章内容包括: 最小生成树 树可以看做许多相关联问题的抽
参考来源
- 位置:《算法精解:C语言描述》第16章《第16章 图算法》(spine1409;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1375.html;u291-ch16-001)。
- 结论依据:291全部三算法和八应用全文实读,不将现实模型例说成完整可行性证明。
- 原始内容:带权图。在一个带权图中,每条边都可能附带一个值或权,这些权用一个小的数字标记在边上。虽然很多条件因素都可以作为权值,但通常它表示遍历这条边所产生的代价。带权图和其算法可以用来对很多的实际问题进行建模。示例16-1是本章所介绍的图算法的头文件。 本章内容包括: 最小生成树 树可以看做许多相关联问题的抽