北邮-通信网规划理论 第二章--电信网规划(二)

北邮、通信网规划理论

通信网规划 通信网规划理论 网规划理论制作人：孙青华

北邮、通信网规划理论

第二章

电信网规划的基础知识

北邮、通信网规划理论

第二章 电信网规划的基础知识 第一节 第二节 第三节 第四节 第五节 第六节 方法 第七节 第八节 图论基础知识 随机服务系统及其在电信中的应用 业务预测的基本方法 流量预测的基本方法 电信网规划中的评价准则 电信网规划中的财务经济评价指标及经济分析 多目标方法及其应用 智能算法及其应用3

北邮、通信网规划理论

2.1.2

网络中各端点的最短连接方法 最小生成树算法 最小生成树算法

北邮、通信网规划理论

将图中所有边按权值从小到大排列 选所剩最小的边加入边集 T是否和前面加入 的边构成回路 N

Kruskal 算法： 算法：定理 指定图中 任一点vi,如果 vj 是距 vi 最近的相 邻节点， 邻节点，则关联边 eij 必在某个最小 生成树中。 生成树中。

Y

将边加入图中N T 中是否有 n 1 条边 Y

舍去该边推论 将网路中 的节点划分为两个 不相交的集合V1和 V2,V2=V V1,则V1 和V2间权值最小的 边必定在某个最小 生成树中。 生成树中。5

T 是最小生成树

北邮、通信网规划理论

最小生成树 V1v5 9 v6 8 17 7 11 v4 16 10 v1 10√

边权矩阵V2 V3 V4 V5 V6

√ 11 12 7 v2 √ 10 9.5 v3 19.5 √ 17 Prim算法是多项式算法 Prim算法是多项式算法 Prim算法可以求最大生成树 Prim算法可以求最大生成树 网路的边权可以有多种解释，如效率 网路的边权可以有多种解释，

√ 10 √ 16

17 V1 9.5 ∞ ∞ 19.5 V2 9.5 7 ∞ 12 V3 7 8 7 V4 ∞ 9 V5 ∞ ∞ 8 19.5 12 7 9 V 10 16 11 106

北邮、通信网规划理论

2.1.3

电信网中局、 电信网中局、站间最短路的算法

狄克斯特拉算法 (Dijkstra algorithm, 1959)–计算两节点之间或一个节点到所有节点之间的最短路 计算两节点之间或一个节点到所有节点之间的最短路 –可以应用于简单有向图和混合图 可以应用于简单有向图和混合图 可以应用于简单 –一种隐阶段的动态规划方法 一种隐阶段的动态规划方法

Warshall-Floyd算法(1962) Warshall-Floyd算法(1962) 算法–Warshall-Floyd算法可以解决有负权值边(弧)的最短路问 Warshall-Floyd算法可以解决有负权值边( Warshall 算法可以解决有负权值边 题 –该算法是一种整体算法，一次求出所有点间的最短路 该算法是一种整体算法， 该算法是一种整体算法 –该算法不允许有负权值回路 该算法不允许有负权值回路 该算法不允许有 对于有向网络中的一个圈，定义它的权为圈上所有前向弧上 对于有向网络中的一个圈， 的权的和, 减去圈上所有反向弧上的权. 权为正的圈称为正 的权的和, 减去圈上所有反向弧上的权. 权为正的圈称为正 权

为负的圈称为负圈 权为0的圈称为零圈 负圈; 零圈. 圈; 权为负的圈称为负圈; 权为0的圈称为零圈.

线性规划法求解最短路 –将问题模型化 将问题模型化

北邮、通信网规划理论

令始点Ts=0,并用框住，所有其它 始点T =0, 框住， 节点临时标记 Tj=∞ ; 出发， 从 vs 出发，对其相邻节点 vj1 进 行临时标记， 行临时标记，有 Tj1=ds,j1 ; 在所有临时标记中找出最小者， 在所有临时标记中找出最小者，并用 框住， 框住，设其为 vr是否全部节点都永久标记 是否全部节点都永久标记 N Y

Kruskal 算法： 算法： 计算两节点之 计算两节点之 间或一个节点到 所有节点之间的 最短路

算法结束

出发， 从新的永久标记节点 vr 出发，对其相邻的临 时标记节点进行再标记，设 vj2 为其相邻节点 时标记节点进行再标记， ,则 Tj2=min{Tj2, Tr+dr,j2 }

令 dij 表示 vi 到 vj 的直接距 离(两点之间有 边),若两点之 间没有边，则 间没有边， 令 dij = ∞, 若两点之间是 有向边， 有向边，则 dji = ∞;令 dii = 表示始点， 0,s 表示始点， t 表示终点 8

北邮、通信网规划理论

例

狄克斯特拉算法 ∞ 10 ∞ 11

2 100

1 8 9 3 4∞ 12 15

5 20 2 2 30∞ t 31

s 8

15

4 ∞ 8

7

6∞ 13 15

每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同 每次迭代只有一个节点获得永久标记， 每次迭代只有一个节点获得永久标记 9 时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记， 时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记， 是一种深探法 是一种深探法

北邮、通信网规划理论

Warshall-Floyd算法 Warshall-Floyd算法 (1962)

该算法基于基本的三角运算 =1,2,…, 执行三角运算， 定理 依次对 j=1,2, ,n 执行三角运算，则 dik 间最短路的长度。 最终等于 i 到 k 间最短路的长度。

j dij i dik djk k

北邮、通信网规划理论

最短路问题的数学描述xij表示弧(i,j)是否位于s-t路上：当xij =1时，表示弧(i, 表示弧( 路上： =1时 表示弧( j)位于s-t路上，当xij =0时，表示弧(i,j)不在s-t路上. 路上， =0时 表示弧( 路上. 6min( i , j )∈ A

∑w x

5 (开始) A 开始) 4 7

B

D

6

ij ij

4 (结束 结束) F (结束) 5 C 3 E 1

s.t.

1, xij ∑ x ji = 1, ∑∈A j:( j ,i )∈A j:( i , j ) 0, xij ≥ 0.

i = s, i = t,

i ≠ s, t ,

思考： 思考： 关联矩阵是否一定是全么模矩阵？ 关联矩阵是否一定是全么模矩阵？

北邮、通信网规划理论

Bellman方程min

( i , j )∈ A

∑w x

ij ij

s.t.

1, ∑ xij + ∑ x ji = 1, j:( i , j )∈ A j:( j ,i )∈ A 0, xij ≥ 0.

i = s, i = t, i ≠ s, t ,

对偶问题为

max(ut us ) s.t. u j ui ≤ wij , (i, j ) ∈ A.

根据互补松弛条件, 当x和u分别

为原问题和对偶问题的最优解 时: xij (u j ui wij ) = 0, (i, j ) ∈ A.

北邮、通信网规划理论

Bellman方程 Bellman方程当某弧(i,j)位于最短路上时， 即变量xij>0时, 一定有 当某弧(i,j)位于最短路上时， 即变量x (i,j)位于最短路上时

u j u i = wij

相当于对节点 j 赋予的一个实数值uj (通常称为 “标号”), 在us=0时表示的正好是节点s到节点j的最短路的长度. Bellman方程(最短路方程、动态规划基本方程 )

u s = 0, u = min{u + w }. ij j i≠ j i 一般情况下直接求解最短路方程是相当困难的.

北邮、通信网规划理论

最短路树(树形图)

定理 对于只含正有向圈的连通有向网络， 从起点s 到任一顶 对于只含正有向圈的连通有向网络， 从起点s 点j都存在最短路，它们构成以起点s为根的树形图(称为最短 都存在最短路，它们构成以起点s为根的树形图( 路树(Tree of Shortest Paths)或最短路树形图(Shortest 路树( Paths )或最短路树形图 ( Path Arborescence)),最短路的长度可以由Bellman方程唯 Arborescence)),最短路的长度可以由Bellman方程唯 )) Bellman 一确定. 一确定. 6

5 A 7 4

B

D

6

4 F 5 C 3 E 1

前一部分实际上是Bellman最优化原理的直接结果； 前一部分实际上是Bellman最优化原理的直接结果； Bellman最优化原理的直接结果 后一部分中Bellman方程解的唯一性可以用反证法证明( 后一部分中Bellman方程解的唯一性可以用反证法证明(略) Bellman方程解的唯一性可以用反证法证明

北邮、通信网规划理论

最短路算法 – 例例 计算如下网络(图)中从节点A到所有其它节点的最短路. 计算如下网络( 中从节点A到所有其它节点的最短路.

1 A -1 B 1 A -1 B 1 E -1

E 5 3 1

-2 D 4 C -2 D 1 -1 3

1

2 E 5 3 1

-2 4 4 5

计算过程:u1 =0,

u2 = min{ui + wi 2 } =min{0+1}=1, i <2

u3 = min{ui + wi 3 } =min{0+(-1)}=-1, i <3u 4 = min{ui + wi 4 }i <4

=min{0+5,1+(-2),-1+3}=-1, =min{-1+1, -1+4}=0.

C

u5 = min{ui + wi 5 }i <5

北邮、通信网规划理论

一般费用网络：标号修正算法 一般费用网络： 逐次逼近法， Approximation) (逐次逼近法，Successive Approximation)Bellman - Ford算法 (Ford,1956)计算从起点到所有其它顶点的最短路: 相当于迭代法解Bellman Bellman方程 计算从起点到所有其它顶点的最短路: 相当于迭代法解Bellman方程

u1(1) = 0, (1) j ≠ 1, u j = w1 j , u (jk +1) = min{u (jk ) , min{ui( k ) + wij }}, i≠ j uj ~(3 引理 在(1)~(3)中, 临时标号 条时的最短路路长. 过的弧数不超过 k 条时的最短路路长.(k )

(1) 1 ≤ k ≤ n 2,1 ≤ j ≤ n. ( 2) (3)

是从起点 s =1到顶点 j 且所经

北邮、通信网规划理论

Floyd-Warshall算法的具体实现 算法的具体实现 算法由于要记录所有节点之间最短路的信息, 由于要记录所有节点之间最短路的信息, 所以这里我们要用一个二维数组P;

采用“正向追踪”的方式得到最短路. 可以依据二维数组P, 采用“正向追踪”的方式得到最短路.STEP0 STEP0: k=0. 对于所有节点i和j: 令 (( p ij1 ) = j,

( u ij1 ) = w ij

, ) .

w ii = 0

之间没有弧, ,若节点i和j之间没有弧, 认为 w ij = ∞( ( ( u ij k ) ≤ u ikk ) + u kjk )

STEP1 STEP1: k=k+1. 对于所有节点i和j: 若( ( p ij k + 1 ) = p ij k ) ( p ij k + 1 ) = p i(,kk )( u ij k + 1 ) = u,( k ) ij

, 令 ; .

否则令

( ) ( ( u ij k + 1 , = u ikk ) + u kjk )

STEP2:如果k=n, 结束; 否则转STEP1. STEP2 结束; 否则转STEP1 STEP

北邮、通信网规划理论

Floyd-Warshall算法的例 算法的例 算法 4 1 -3 5 4 3 6 0 4 3 ∞ 3 0 7 ∞ , = ∞ 10 0 3 6 0 5 6 1 1 = 1 1 2 2 2 2 3 3 3 3 4 4 , 4 4

-3

2 6 10 3 -7

U (1)

P (1)

北邮、通信网规划理论

Floyd-Warshall算法的例 算法的例 算法 0 4 3 ∞ 3 0 7 ∞ , = ∞ 10 0 3 5 6 2 0 1 1 = 1 1 2 3 4 2 3 4 , 2 3 4 2 1 4

U (2)

P ( 2)

U ( 3)

0 4 3 ∞ 3 0 7 ∞ , = 7 10 0 3 3 6 1 0 1 5 4 3 6 -3 4 -3 6

P ( 3)

1 1 = 2 22

2 3 4 2 3 4 , 2 3 4 2 2 4

10 3

-719

本文来源：https://www.bwwdw.com/article/trcj.html