受限交换邻域搜索：最小连接支配集问题的高效求解策略

本文主要探讨了"基于交换限制的邻域搜索"在解决"最小连通支配集问题"（Minimum Connected Dominating Set Problem, MCDSP）中的应用。最小连通支配集问题是近年来随着移动Ad-hoc网络和传感器网格技术发展而变得日益重要的研究课题，它涉及在一个无线网络中找到一个集合，该集合内的每个节点都与至少一个其他节点相连，并且整个集合能够覆盖所有节点，以确保通信的有效性和安全性。 作者Xinyun Wu和Zhipeng Lü来自华中科技大学计算机科学与技术学院的智能计算与优化实验室，他们的研究聚焦于针对MCDSP设计一种新颖的受限交换基邻域搜索（Restricted Swap-Based Neighborhood, RSN）方法。这种方法是通过将这种特定的邻域结构嵌入到禁忌搜索（Tabu Search, TS）框架中，以增强搜索空间的多样性。禁忌搜索是一种常用的优化算法，它通过避免重复访问已经探索过的状态来防止陷入局部最优解。 文章的关键创新在于引入了一个扰动机制，这有助于增加算法在搜索过程中的灵活性，从而提高解决方案的质量。通过对四组广泛使用的文献中基准实例进行测试，结果显示，提出的RSN-TS算法在求解质量（即找到的最小连通支配集的大小）和计算效率方面都表现出显著的优势。特别是，该算法成功地改进了41个测试案例中的最佳已知结果，这表明其在解决实际问题时具有很高的实用价值和竞争力。 这项研究不仅为最小连通支配集问题提供了新的求解策略，而且展示了在复杂网络环境中优化搜索策略的重要性。通过结合限制交换操作和禁忌搜索，研究者们得以实现更高效的搜索过程，这对于无线网络管理和资源分配等领域具有潜在的实际应用前景。