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

• 作者: 宁爱兵 熊小华
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 竞争决策算法 生成树 最小比率生成树 降阶
• 年，卷（期）: 2012,（28）
• 所属期刊栏目: 研究、探讨
• 页码范围: 47-51
• 分类号: TP301.6
• 字数: 4424字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2012.28.010

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宁爱兵	上海理工大学管理学院	59	341	11.0	15.0
2	熊小华	上海第二工业大学计算机与信息学院	23	132	7.0	10.0