组合优化（Combinatorial Optimization）是一门古老而又年轻的学科,著名数学家Fermat,Euler等都为其形成和发展做出过重要贡献。二十世纪后半叶,伴随着工业科技革命和现代管理科学的发展,特别是计算机技术的突飞猛进和在各行业的广泛应用,组合优化已壮大成为计算机科学与运筹学的一个独立分支,一些数百年前数学家们偶然想到的问题和方法,已在网络通信、物流管理、交通规划等行业发挥了重要的作用,这是他们当时所不曾想到的。这从另一方面寓示了这一学科的巨大前景。组合优化问题的目标是从组合问题的可行解集中求出最优解,通常可描述为:令Ω={s₁,s₂,…,s_n}为所有状态构成的解空间,C（s_i）为状态s_i对应的目标函数值,要求寻找最优解s^*,使得对于所有的s_i∈Ω,有C（s^*）=min{C（s_i）}。典型的组合优化问题有旅行商问题、背包问题、装箱问题、最小度生成树问题、集合覆盖问题等。这些问题描述非常简单,并且有很强的工程代表性,但最优化求解很困难,其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间,以致根本不可能在现有计算机上实现,即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。组合优化问题中有一些是P类问题,人们可以分析利用其组合性质,发掘深层次的结构,进而设计出有效的算法求出问题的最优解。不幸的是,许多重要问题是NP-hard,很难精确求解。当问题规模超过一定大小之后,即使超级计算机也无能为力。这也是计算机算法和复杂度研究的长期课题,其有效求解直接影响到国民经济和国防建设的许多领域。因此,寻找求解这类问题的快速而有效的算法具有深刻的理论意义和普遍的实用价值。对于NP-hard问题,人们常常把研究的重点转向在较短时间（多项式时间）内求一个可行的次优解。事实上,关于启发式算法有大量的文献,并有着广泛的应用。启发式算法致命的弱点是对所求的解的质量没有任何保障。事实上,对任何一个启发函数,总有一些实例使其失效,也就是说,所求解偏离最优解甚远。近似算法（Approximation Algorithm）弥补了启发式算法的不足,它能够界定所求解的质量。近似算法也是一类启发式算法,但它给出了近似解与最优解之比值的上界。另一方面,由于NP-hard问题的结构难以被解析的了解,人们常常在算法中引入随机化技术,许多求解NP-hard问题的算法都可以看做是随机算法。一般的说,随机算法就是指计算过程受到随机数影响的算法,它是对传统确定性算法设计思想的突破,目前已被广泛应用在数论、计算几何、图论、并行处理和网络路由等多个领域中。本文讨论低度网络设计问题、集合覆盖问题和路径规划问题的算法与复杂度,设计它们的新求解算法。三个计算问题均以网络与通信领域的实践活动为应用背景,路经规划问题还直接用于机器人控制研究中。本文的主要研究工作和创新点:1.提出了有向无环图上最小度生成树（MDST）问题的一种精确算法。在设计通讯网络时,常常会出现这样的情况,要求构建一个连接多个客户终端的网络,而可用的软硬件设施往往对网络的拓扑结构施加额外的约束。比如,计算机网络领域中往往会碰到这样的问题:给定一定数量的客户端,它们通过某种特定的通讯协议进行互相通讯,这种协议对每一个客户端可以同时打开的连接数目具有一定的约束。用图论中的术语来描述,客户端对应于图中的顶点,网络连接对应于图中的边。这种约束条件就转化为对图中顶点的最大度的限制。这种情形可以建模成最小度生成树问题。给定一个无向图G=（V,E）,我们要求一棵生成树T,使得T中顶点的最大度最小。该问题是哈密尔顿路问题的推广,因此是NP-hard。本文给出了该问题在有向无环图上的一种精确算法,并将该算法应用到最短时间广播问题,改进了其近似比。2.提出了有向无环图上带度约束的最小生成树问题的一个近似算法。与最小度生成树问题密切相关的是最小度最小生成树（MDMST）问题。在该问题中,图的每条边都有一个非负权值,或称为费用,要求一棵最小生成树T,使得T的度在所有最小生成树中最小。该问题在网络设计、VLSI中都有广泛应用。在构建通讯网络时,往往不仅要降低每个节点的负载（节点的度）,同时也要降低网络的构建费用（边的权值）。MDMST问题自然而然的建模了这两种互斥的要求。带度约束的最小生成树（BDMST）问题是MDMST问题的预算版本。我们给定一个度的界B≥1,要求一棵最小生成树T,使得T的度不超过B。上述问题,对于无向版本,已有大量文献。对于有向版本,问题无疑复杂得多,这方面的研究成果也比较少,本文一部分工作正是致力于这类问题的有向图情况。在该问题中,度和费用的要求是互斥的,我们给出了一个将度和费用进行折中的近似算法。3.提出了集合覆盖问题的一种随机近似算法。集合覆盖问题在实践中具有重要价值,多年来作为计算机算法研究的核心问题而被广泛研究。与传统的“确定”算法不同,本文给出了带权集合覆盖问题的一种“随机”算法,并给出了算法期望意义下的近似比。由于算法的随机性,每次运行输出的覆盖集合都可能不同,因此,可以多次运行该算法得到一系列覆盖,从中选择费用最小的,该覆盖很可能接近最优解,甚至可能就是最优解。又因为该算法的时间复杂度是线性的,这为算法的多次运行奠定了基础。4.提出了规划问题的一种状态空间削减算法。作为人工智能的核心领域之一,规划在航天技术、航线安排、商业策略、医疗优化、自动控制、工程设计等众多领域有着巨大的作用。状态空间搜索是人工智能的一个基本的普遍使用的技术。状态空间一般被定义为一个有向图。图中的每条边都有一个权值,或者叫做费用,搜索是指找一条由初始状态到目标状态的路径,使得其总费用最小。传统的状态空间搜索算法的性能主要依赖于启发函数的精度。然而,最近的研究表明,即使使用近乎完美的启发函数,启发式搜索仍然具有指数的时间复杂度。因此,改进搜索算法不能完全寄希望于设计更好的启发函数,而应该另辟途径。本文提出一种状态空间削减技术,我们称之为核心扩展方法。该技术可以将原状态空间图削减成一个较小的状态空间图,同时保持了完全性和最优性。而且,核心扩展方法可以与传统的搜索算法结合使用,从而达到进一步加速搜索的目的。本文的进一步工作主要包括:1.一般有向图上的低度网络设计问题的算法研究。对于低度网络设计问题,我们主要集中研究了有向无环图上的情况,一般的有向图情况将是我们进一步研究的方向之一。2.集合覆盖问题的各种变体以及其对偶问题的随机算法研究。从“随机”的角度,对集合覆盖及其相关问题进行研究也是我们的研究方向之一。3.具有更强削减能力的状态空间削减算法研究。状态空间削减是与启发函数设计是从两个不同的角度降低搜索代价,两者相辅相成。由于启发函数的局限性,削减技术显得更为重要。