最大覆盖问题研究

最大覆盖问题是运筹学中一个经典组合优化问题。通常是现实生活中邮政服务站点,加油站点,银行选址等问题的数学抽象。最大覆盖问题一般被描述为有被服务点若干,选取若干服务点对被服务点进行服务的最小代价。最大覆盖问题已经被证明是一类NP问题,也就是不能在多项式时间内求得最优值的问题。目前国内外学者对于此问题的研究多是使用遗传,蚁群,退火模拟等启发式搜索求的近似值的方法来进行讨论。本文主要分析了最大覆盖问题的穷举解法,剪枝搜索解法和启发式搜索解法。对这三种解法进行了测试,比较算法的优劣和适用范围。通过提出对于待选边进行性价比的计算,设计出启发式函数来搜索近似最优值,最后的测试将近似最优值保持在平均2的差异值范围内。