| 最小比率生成树的竞争决策算法 |
| |
| 引用本文： | 熊小华,宁爱兵.最小比率生成树的竞争决策算法[J].计算机工程与应用,2012,48(28):47-51. |
| |
| 作者姓名： | 熊小华 宁爱兵 |
| |
| 作者单位： | 1.上海第二工业大学 计算机与信息学院，上海 201209
2.上海理工大学 管理学院，上海 200093 |
| |
| 基金项目： | 国家自然科学基金(No.70871081);上海市重点学科建设资助项目(No.S30504) |
| |
| 摘 要： | 最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树，例如总代价与总收益比值最小的生成树。当不限制分母的符号时，这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上，提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优，采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性，采用无关和相关两种策略产生测试数据，并使用Delphi 7.0实现了算法的具体步骤。
|
| 关 键 词： | 竞争决策算法 生成树 最小比率生成树 降阶 |
Competitive decision algorithm for minimum ratio spanning tree |
| |
| XIONG Xiaohua
,
NING Aibing.Competitive decision algorithm for minimum ratio spanning tree[J].Computer Engineering and Applications,2012,48(28):47-51. |
| |
| Authors: | XIONG Xiaohua NING Aibing |
| |
| Affiliation: | 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 |
| |
| 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. |
| |
| Keywords: | competitive decision algorithm spanning tree minimum ratio spanning tree reduction |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
