欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树，例如总代价与总收益比值最小的生成树。当不限制分母的符号时，这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上，提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优，采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性，采用无关和相关两种策略产生测试数据，并使用Delphi7．0实现了算法的具体步骤。
英文摘要：
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 competi- tive 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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：