最小比率生成树的竞争决策算法

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (28): 47-51.

最小比率生成树的竞争决策算法

熊小华1，宁爱兵2

1.上海第二工业大学计算机与信息学院，上海 201209
2.上海理工大学管理学院，上海 200093

出版日期:2012-10-01 发布日期:2012-09-29

Competitive decision algorithm for minimum ratio spanning tree

XIONG Xiaohua1, NING Aibing2

1.College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, China
2.School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China

Online:2012-10-01 Published:2012-09-29

摘要/Abstract

摘要： 最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树，例如总代价与总收益比值最小的生成树。当不限制分母的符号时，这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上，提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优，采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性，采用无关和相关两种策略产生测试数据，并使用Delphi 7.0实现了算法的具体步骤。

关键词: 竞争决策算法, 生成树, 最小比率生成树, 降阶

Abstract: Minimum ratio spanning tree（MRST for short） is the problem of finding a minimum spanning tree when the objective function is the ratio of two linear cost functions（e.g., a ratio of cost to weight）. MRST problem is NP-hard when the denominator is unrestricted in sign. Based on the mathematical properties of MRST, a competitive decision algorithm for MRST is presented. The edge-exchange is used to prevent the problem from becoming trapped in a local optimum. The algorithm is coded in Delphi 7.0, by which series of typical instances are tested. These instances are generated using two strategies, one is irrelevant strategy, and the other one is related strategy.

Key words: competitive decision algorithm, spanning tree, minimum ratio spanning tree, reduction

熊小华1，宁爱兵2. 最小比率生成树的竞争决策算法[J]. 计算机工程与应用, 2012, 48(28): 47-51.

XIONG Xiaohua1, NING Aibing2. Competitive decision algorithm for minimum ratio spanning tree[J]. Computer Engineering and Applications, 2012, 48(28): 47-51.

[1]	苟海雯，宁爱兵，胡沁，张惠珍. 带惩罚的无容量设施选址问题的降阶回溯算法[J]. 计算机工程与应用, 2020, 56(24): 43-49.
[2]	龙浩，张书奎，张力. 群智感知网络中基于社会关系的社区发现算法[J]. 计算机工程与应用, 2020, 56(15): 179-184.
[3]	邓宇，谌贵辉，李忠兵，张军豪，亢宇欣，夏旭洪. 基于颜色与边缘融合的非局部立体匹配算法[J]. 计算机工程与应用, 2020, 56(10): 199-204.
[4]	宋森森1，贾振红1，杨杰2，Nikola KASABOV3. 结合Ostu阈值法的最小生成树图像分割算法[J]. 计算机工程与应用, 2019, 55(9): 178-183.
[5]	何永梅，宁爱兵，彭大江，尚春剑，张惠珍. 软容量限制设施选址问题的竞争决策算法[J]. 计算机工程与应用, 2019, 55(3): 50-54.
[6]	曹戴，陈丽芳. 基于杰卡德度量的智能拼图改进算法[J]. 计算机工程与应用, 2018, 54(2): 188-192.
[7]	刘志民，宁爱兵，黄飞，何咏梅，张惠珍. 加权分治与皇冠技术求解最大加权独立集[J]. 计算机工程与应用, 2017, 53(9): 26-30.
[8]	陈卉，胡立坤，黄钰雯. 采用高斯混合模型及树结构的立体匹配算法[J]. 计算机工程与应用, 2017, 53(20): 195-200.
[9]	郑淼1，郑成增2. 粒子寻优和最小生成树聚类下的WSN能量优化[J]. 计算机工程与应用, 2017, 53(15): 106-110.
[10]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[11]	邵　　超，万春红，李洁颖. 用于多流形分类的核等距映射算法[J]. 计算机工程与应用, 2016, 52(4): 121-128.
[12]	支志兵，宁爱兵，陈吉珍，王永斐，杨晓芳. 最大团问题的加权分治算法[J]. 计算机工程与应用, 2016, 52(2): 50-53.
[13]	鱼先锋. 半直觉模糊图与应用[J]. 计算机工程与应用, 2016, 52(18): 88-91.
[14]	徐康丽1，杨志霞1，蒋耀林2. 基于Krylov-Schur重启技术的Arnoldi模型降阶方法[J]. 计算机工程与应用, 2016, 52(12): 251-255.
[15]	陈吉珍，宁爱兵，支志兵，胡琳琳，张惠珍. 图论中最大独立集问题的精确算法[J]. 计算机工程与应用, 2016, 52(1): 20-22.