流量约束最小生成树问题的分枝定界算法1
需积分: 0 197 浏览量
2022-08-03
20:21:09
上传
评论
收藏 782KB PDF 举报
第 22卷 第 3期
2005年 6月
黑 龙 江 大 学 自 然 科 学 学 报
JOURNAL OF NATURAL SCIENCE OF HE ILONGJ IANG UN IVERSITY
Vol122 No13
June, 2005
流量约束最小生成树问题的分枝定界算法
杨亚碧
1
, 黄亚玲
2
(
1. 贵州民族学院 物理与电子信息科学系 ,贵州 贵阳 550025; 2. 北京航空航天大学 计算机学院 ,北京 100083
)
摘 要 : 研究流量约束最小生成树问题
(
CMST
)
,它是通讯和网络优化设计中最为基础和重要
的问题之一. 给出一种分枝定界算法 ,详细阐述了算法的原理、搜索过程 ,数值结果表明 ,该算法是
有效的 ,并且有较好的计算性能.
关键词 :最小生成树 ; 流量约束 ; 分枝定界
中图分类号 : TU313 文献标识码 : A 文章编号 : 1001 - 7011
(
2005
)
03 - 0353 - 06
收稿日期 : 2004 - 11 - 25
基金项目 : 国家自然科学基金资助项目
(
60473010
)
作者简介 : 杨亚碧
(
1962 -
)
,女
(
苗族
)
,讲师 ,主要研究方向 :计算物理与高性能计算 , E - mail: zttgzcn@yahoo. com. cn
黄亚玲
(
1967 -
)
,女 ,高级工程师 ,硕士
1 问题与假定
流量约束最小生成树问题是指在一定的流量约束条件下 ,找到所有由已知节点集组成的展开树中成本
最低的问题. 考虑一个由节点集 V = { 0, 1, …, n}和弧集 A 组成的连通图 G =
(
V, A, b, c
)
. V 中每个节点 i有
一个单位节点质量 b
i
=1和 b
0
= 0. 节点质量可理解为流量需求 ,而一个弧质量 c
ij
表示使用 A 中弧
(
i, j
)
的成
本. 节点 0具有其特殊性 ,被称为中心节点并将成为树根. 一个根子树
(
或组件
)
定义为通过弧
(
0, i
) (
该弧可
被视为中心弧
)
连接到中心的最大子树. 为了满足流量约束 ,每个弧上的流量不得超过已知的流量约束 K. 借
助这些定义 , CMST问题便等同于寻找一个连通节点集 V 的最低成本树 ,其中所有弧满足流量约束.
假设当 i = 1, …, n时 b
i
=1;当 i = 0时 b
i
= 0, 那么 CMST问题可以由一个混合整数线性规划公式来描
述 ,如文献 [1 ]所示. 如果解中包括 arc
(
i, j
)
,定义 x
ij
= 1;否则 x
ij
= 0. 当 i = 0, …, n,且 j = 1, …, n时 ,设 y
ij
表
示弧 arc
(
i, j
)
上的流量 , 下面的公式给出了一个以中心节点 0为根的受流量限制的最低成本树 :
M inimize
∑
n
i =0
∑
n
j =1
c
ij
x
ij
(
1
)
s. t.
∑
n
i =0
x
ij
= 1 i = 1, …, n j = 1, …, n
(
2
)
∑
n
i =0
y
ij
-
∑
n
i =1
y
ji
= 1 j = 1, …, n
(
3
)
x
ij
≤y
ij
≤
(
k - b
i
)
·x
ij
i = 1, …, n j = 1, …, n
(
4
)
x
ij
∈{ 0, 1} y
ij
≥0 i = 1, …, n j = 1, …, n
(
5
)
CMST在计算机网络、通信网络、交通运输网络、航空航天等领域还有着广泛的应用.
由文献 [2 ]知 ,当 2 < k < n /2时 ,流量约束最小生成树是 N P - hard问题.
关于 CMST问题 ,已有很多启发式算法 ,目前已取得的成果包括构造方法
[3 - 4 ]
、储蓄算法
[5 - 7 ]
、二重方
法
[5 ]
、分解还原算法
[8 ]
、定误差边界方法
[ 9 ]
、本地交换方法
[5 ] [10 ]
、二次方法
[7 ] [11 ]
和 节点交换方法
[12 ]
等.
本文提出一种解决受流量约束的最小生成树问题的确定性算法. 显然 ,枚举随节点数的增加而计算量指
数增长 ,对于大规模问题是无法应用的 ,而启发式算法更具有可行性. 但是 ,开发精确的算法仍然是非常重要
的 ,因为精确算法能够证明解的最优性 ,而启发式算法却做不到. 对于中、小规模的问题 ,精确算法依然是切
王者丶君临天下
- 粉丝: 17
- 资源: 265
最新资源
- 各国之间制度距离1996-2020
- 884091349023892Lightroom_219576.apk
- 1998-2022年上市公司超额现金持有水平-目标现金持有水平偏离度参考顶刊含Stata代码
- 广东省2023年我国科技型中小企业数据
- WANGSHANGYINHANG-4.2.9.031406-android
- docker&docker-compose离线安装包(centos)
- 混淆矩阵（Confusion Matrix）是机器学习领域中一种常用的可视化工具4.txt
- 滑动窗口是一种流量控制技术，用于在数据传输过程中进行拥塞控制和流量调节4.txt
- Nacos如何支持服务发现和注册-基于词频统计的分析.txt
- 基于BP神经网络的PID控制算法-MATLAB实现
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0