知识卡片

普通读书笔记卡 · 3644.h · 生成模型:未记录

图优化先确定代价与可行约束

理解等级:中级

权可表示边的时间、距离、费用等可比较代价,但应先定义优化目标。最小生成树优化连接全部顶点的总边权,最短路径优化特定源到目标的路径和,旅行商优化访问各点并回起点的回路,三者不是同一问题。

管线最小连接是生成树模型的典型近似,但实际容量、冗余、可靠性、方向和必须多次访问等约束未必包含在树或一次遍历模型里。不能因为一个应用名出现,就推断书中算法已解决其全部现实要求。

本章带权状态复用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是本章所介绍的图算法的头文件。 本章内容包括: 最小生成树 树可以看做许多相关联问题的抽