文章目录
模型介绍与六大分类
-
- 模型介绍与六大分类
- 图与网络的基本概念
- 邻接矩阵
- 关联矩阵
- 弧表表示法
- 邻接表表示法
- 案例一
- 总结
我们将讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。
例 1 最短路问题（SPP－shortest path problem） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的 公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运 行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。
例 2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两 个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？
例 3 指派问题（assignment problem） 一家公司经理准备安排 N 名员工去完成 N 项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大&#
