论文部分内容阅读
最小加权顶点覆盖(MWVC)问题是图论中一个著名的组合优化问题，它有着广泛的实际应用，例如网络流、电路设计、运输和电信等。MWVC问题中的每一个顶点都有一个正权值，它的目标是在一个无向图中求得一个总权值最小的顶点覆盖。一个顶点覆盖是一个图的顶点集的子集，这个子集包含图中每条边的至少一个顶点。因为MWVC问题是NP难的，所以许多求解该问题的方法都是基于启发式方法，尤其是局部搜索。本文关注于大规模MWVC问题的高效求解，设计了三个高效的局部搜索算法——FastWVC，DynWVC1和DynWVC2。 本文提出的FastWVC算法主要包含三个创新的算法策略。第一个是ConstructWVC过程，目标是在短时间内生成一个有质量的初始顶点覆盖。第二个是一个新的交换步，它用来重建顶点覆盖。最后一个是高效选择添加顶点，它能加速算法。我们在102个实例上进行的实验证实了算法的有效性。结果显示FastWVC在大多数实例上的解质量和计算时间都比它之前的其他算法表现得更好。作为本文的另一个部分，我们提出两个动态策略来调节FastWVC算法在搜索过程中的行为。第一个动态策略是动态选择顶点评分函数，我们用该策略提高了FastWVC的性能，并由此产生了DynWVC1算法。第二个动态策略是动态选择移除顶点数量，使用该策略继续改进DynWVC1后，我们得到了DynWVC2算法。本文提出的算法都在100多个来自不同领域的大图（规模高达千万顶点）上进行了测试，实验表明了这些算法的高效性以及策略的有效性。另外，本文还在一个重要的实际问题即动态地图标记问题上测试了算法，实验说明本文的算法在该问题上取得了比之前的算法更好的效果。