科研之友
微信
新浪微博
Facebook
分享链接
摘要
最大最小分散度问题可简单描述为：在给定的集合中选择包含固定元素个数的子集，使得该子集中的元素在给定距离度量下的最小距离最大；该问题在生产生活中有广泛的应用。近些年来，该问题的一种考虑容量下限和成本上限的变体开始引起学者们的关注，并已被证明为NP-Complete问题。基于考虑容量和成本的最大最小分散度选址问题进行研究，首先提出该问题的数学性质并证明，利用这些性质可以减小问题规模或缩减搜索空间，以加快问题的求解速度，然后设计了上下界子算法及降阶子算法；基于这些子算法提出一种可大幅缩减搜索空间并能得到最优解的降阶回溯算法。通过分析和求解一个示例来阐述该算法的原理和执行过程，并通过随机算例测试、算法对比分析和案例分析进一步验证了该算法的可行性和有效性。结果表明该算法可有效通过大幅缩减搜索空间加快问题的求解速度。
- 单位
