Competitive decision algorithm for minimum ratio spanning tree

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (28): 47-51.

Previous Articles Next Articles

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

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

熊小华1，宁爱兵2

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

Abstract

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

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

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

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

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

[1]	DAI Qi, LI Min, LIU Yang, LI Lihong. Fast Attribute Reduction Algorithm Based on Fuzzy Hierarchical Quotient Space [J]. Computer Engineering and Applications, 2021, 57(4): 55-60.
[2]	GAO Tianyu, WANG Qingrong, YANG Lei. Data Mining Model Based on Attribute Dependability Enhancement of Rough Set [J]. Computer Engineering and Applications, 2021, 57(3): 87-93.
[3]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[4]	LIU Guizhi. Incremental Attribute Reduction of Incomplete Hybrid Data Based on Dimension Change [J]. Computer Engineering and Applications, 2021, 57(12): 161-169.
[5]	LI Mengmeng, SHAO Liangzhi, CUI Wenchao, SUN Shuifa. Joint Bilateral Filtering Method for Ultrasound Image by Fisher-Tippett Distribution Fitting [J]. Computer Engineering and Applications, 2020, 56(9): 221-227.
[6]	WANG Yiwu, YANG Yuwang. Research and Application of Spatial Projection in [K]-means Algorithm [J]. Computer Engineering and Applications, 2020, 56(7): 200-204.
[7]	HAN Song, HAN Qiuhong. Review of Semi-Supervised Learning Research [J]. Computer Engineering and Applications, 2020, 56(6): 19-27.
[8]	WEI Shichao, LI Xin, ZHANG Yichi, ZHOU Xiaofeng, LI Shuai. Dimension Reduction and Visualization of Mixed-Type Data Based on E-t-SNE [J]. Computer Engineering and Applications, 2020, 56(6): 66-72.
[9]	ZHANG Bo, JIA Huayu, MA Jun. Estimation of Air Condition for Unmanned Aerial Vehicle Based on RS-GA Neural Network [J]. Computer Engineering and Applications, 2020, 56(4): 209-213.
[10]	QIU Jianrong, LUO Han. Improved Local Linear Embedding Algorithm and Its Application [J]. Computer Engineering and Applications, 2020, 56(3): 176-179.
[11]	GOU Haiwen, NING Aibing, HU Qin, ZHANG Huizhen. Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties [J]. Computer Engineering and Applications, 2020, 56(24): 43-49.
[12]	MOU En, ZHANG Xianyong, YAO Yuesong, DENG Qie. Class-Specific Attribute Reduct and Its Heuristic Algorithm of Neighborhood Approximation Condition-Entropy [J]. Computer Engineering and Applications, 2020, 56(24): 175-180.
[13]	ZHAN Peng, CHEN Lin, CAO Luhui, XU Haoran, LI Xueqing. Time Series Anomaly Detection Based on Kernel Turning Points Clipped Representation [J]. Computer Engineering and Applications, 2020, 56(23): 130-138.
[14]	SONG Jie, ZHU Yong, XU Bing. Batch Subtraction Update Variance Reduction Gradient Descent Algorithm BSUG [J]. Computer Engineering and Applications, 2020, 56(22): 117-123.
[15]	XIE Xinrui, LEI Xiuren, ZHAO Yan. Application of Mutual Information and Improved PCA Dimensionality Reduction Algorithm in Stock Price Forecasting [J]. Computer Engineering and Applications, 2020, 56(21): 139-144.

Competitive decision algorithm for minimum ratio spanning tree

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics