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

摘要：

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

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

所属期刊栏目：48

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金70871081;上海市重点学科建设资助项目S30504

在线出版日期：2013-01-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：47-51