�
(1) 可取状态 根据题意,并不是所有状态都是可取的.通过穷举法列出来,可 取状态是: 人在此岸 人在彼岸 (1, 1, 1, 1) (0, 0, 0, 0 ) (1, 1, 1, 0 ) (0, 0, 0, 1 ) (1, 1, 0, 1 ) (0, 0, 1, 0 ) (1, 0, 1, 1 ) (0, 1, 0, 0 ) (1, 0, 1, 0 ) (0, 1, 0, 1 ) 总共有十种可取状态.
=d(1)+c 13放入 A 中,即
A = {P1 , P5 , P3 }, B = {P2 , P4 , P6 , p 7 , P8 }
( 3)
minB {d (i ) + cij } = min {d (1) + c1 j , d (3) + c3 j , d (5) + c5 j } i∈ A , j∈
实例二 交通费用问题
设有一城市间的飞机飞行网络, 由第 Pj 个城 市到第 Pj 个城市所需要费用为 Cij ,令 Cij =∞表示 第 Pj 个城市与第 Pj 个城市不直接通航,Cij 的值 如表 6-1 所示.设所有城市中只有 P1,然后多 P1 然后从 p1 出发到各地,求 p1 到 p8 的最少费用.
表 6-1 2 3 4 5 6 7 8 1 28 2 ∞ 1 ∞ ∞ ∞ 2 ∞ 9 8 ∞ ∞ ∞ ∞ ∞ 24 ∞ 27 ∞ ∞ 8 7 3 4 5 6 7
26 ∞ ∞
8 ∞
7
(1)画网络图 该问题属于图论中的最短路问题.画出网络图 6-3.
显然,从 p1 走到 p8 有若于种走法,每种线路的花费不同,一种简单 的想法是,从某一城市 Pj 出发时,皆选花费最小的城市作为下一站.这种 办未能当然可以使当前一站的花费最小,但未必使整个线路花费最小.举 一个简单的例子,如图 6-4,边上的值为相邻点之间的花费.显然,若按 上面的想法,使每一步都花费最小,则从 A 点到 C 点的最短路线为 A— B —C,其总花费为 4.而从 A 直接走到 C 的花费仅为 3.因此,在考虑这 类问题时,每次寻打下一站时不是去考虑局部花费,而应以考虑总体花费 最少为原则. 先把顶点集分成两个集合,集合 A 包含所有的出发点(包括始发点 P1 ) ,集合 B 包括其它点.显然,初始时:
