2. 复杂网络抗毁性优化算法
•
2.1 抗毁性优化算法设计目标
•
主要手段:在网络中增加足够多的备份链路和备份设
备。
•
设计目标:忽略网络带宽的因素,用最少的成本建设
一个最小连通度为 2 的网络。该网络中任意一条传输
链路中断后,任意两个节点间的最大跳数仍不超过
K 。
•
图论表示:给定的无向图 G(V , E) 以及每条边的开
销 Ce ,寻找一个最小连通度为 2 的最小开销子图;
去除子图中任意一条边后,子图中任意两个节点间的
跳数不大于 K 。
•
目前在国内这类算法主要有刘丽娟提出的优化 IE 模
型算法、 Wang 等提出的熵优化模型算法以及刘啸林
提出的基于生成树优化算法等。
第 3 页 / 共 17 页