最小连通支配集问题是一个重要的组合优化问题,在设施选址、无线传感器网络、系统生物学等多个领域有着广泛的应用。支配树问题是最小连通支配集问题的一个扩展,由于他们具有重要的理论研究意义和实际应用价值,近年来受到了研究人员的广泛关注。本文将围绕最小连通支配集问题和支配树问题求解算法展开研究。组合优化问题的求解算法主要分为两类:精确求解算法和启发式求解算法。精确求解算法能够找到问题的最优解,但随着问题规模的增大,求解此类问题需要的存储空间和运算时间呈指数增长,会带来组合爆炸现象,使得在现有能力下,精确求解算法几乎无法求解。启发式求解算法可在合理的时间内找到一个最优解或近似最优解。因此,对于规模相对较大的问题且不要求一定找到最优解的情况,启发式搜索算法是一个很好的选择。本文将设计高效的启发式搜索算法求解最小连通支配集问题和支配树问题。本文的主要研究工作如下:针对最小连通支配集问题,首先,提出了一种基于顶点适应度的顶点打分机制,使搜索可有效跳出局部最优。其次,本文使用格局检测机制来减少局部搜索阶段的循环问题。此外,本文结合了顶点的打分机制和格局检测机制提出了新的顶点翻转机制来指导局部搜索的方向。最后,基于以上的机制,本文提出了基于多重启的局部搜索算法求解最小连通支配集问题。实验结果表明,本文提出的算法在求解质量和时间效率上均优于其他算法。对于类型I实例,本文的算法为所有9个实例找到了最优解。对于类型II实例,本文的算法改进了41个实例的14个最优解。对于类型III实例,本文的算法得到了所有41个实例的最优解。针对支配树问题,首先,我们提出了Dscore和Wscore两个打分函数,将其应用于初始化阶段和局部搜索阶段。其次,在初始化阶段使用带限制候选列表,通过控制参数来平衡初始解的贪婪性和随机性,在搜索阶段提出了包含删除,支配和连通三个主要阶段的迭代局部搜索算法,用于提高初始解的质量。此外,采用高多样性的突变来扰动种群,增加个体的多样性。最后提出基于遗传算法和迭代局部搜索的混合算法求解支配树问题。实验结果表明,本文的算法在求解支配树问题上有很好的性能。在dtp组的33个实例上,本文的算法比VNS算法多找到了12个最优解。在range组的18个实例上,本文的算法与ABC_DT算法都能找到最优解,但是对于平均解,本文的算法在17个实例上优于ABC_DT算法。