瓶颈Steiner树问题的降阶分支限界算法

瓶颈Steiner树问题是经典的组合优化问题,是一个NP难题,在生物网络、交通运输网络、电路设计以及计算机网络布局等领域内有着广泛的应用.本文首先研究瓶颈Steiner树的数学性质,这些数学性质不仅可以判断某些点和边一定在某个最优瓶颈Steiner树中,还可以判断某些点和边一定不在某个最优瓶颈Steiner树中,从而达到降低问题规模和求解难度的目的.然后在瓶颈最小生成树是多项式可解的基础上,提出能快速求解瓶颈Steiner树的降阶分支限界算法.另外文中还通过对多个示例进行分析和求解来阐述算法的原理和过程.

最大团问题的加权分治算法

分支降阶是目前广泛用于求解组合优化领域中难题的技术之一,该技术的核心思想是将原问题分支成若干个子问题,并递归求解这些子问题。加权分治技术是算法设计和时间复杂度分析中的一种新技术。设计一个基于分支降阶的递归算法求解最大团问题。运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O（1.380~n p（n））,其中p（n）表示问题规模数n的多项式函数。运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂度由原来的O（1.380~n p（n））降为O（1.325~n p（n））。研究结果表明运用加权分治技术能够得到较为精确的时间复杂度。

删除顶点生成二分图问题的精确算法

分支降阶是目前广泛用于设计精确算法求解NP-Hard问题的技术之一,该技术主要通过快速降阶、分支及递归求解原问题及其子问题.为了降低分支降阶算法的时间复杂度,一方面可以增加降阶规则、改变算法的设计思想;另一方面可以运用更精确的时间复杂度分析方法分析算法.本文针对删除最少顶点生成二分图问题,首先运用常规枚举方法得到一个时间复杂度为O(3n)的算法;然后通过增加降阶规则、改善算法设计和运用加权分治技术分析算法等方法,最终得到一个时间复杂度为O(1.8157n)的精确算法.本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的.

3度图的最小顶点覆盖问题的多项式时间算法

最小顶点覆盖问题是图论和组合数学中经典的NP-Hard问题之一,在实际问题中有着广泛的应用.本文首先给出最小顶点覆盖问题的若干性质,然后根据这些性质设计了3度图最小顶点覆盖问题的一个多项式时间算法,并通过2个实例对算法进行了说明.

Perfect Code问题的加权分治算法

加权分治技术是算法设计和分析中的一种新技术,该技术通过对处理对象设置不同的权值来更加精确的描述分支子问题规模的大小,其目的是得到最坏情况下时间复杂度更好的精确算法.Perfect Code问题是一典型的NP难题,基于分支降阶技术为其设计一个快速递归算法;同时使用加权分治技术对算法加以分析,得到一个时间复杂度为O(1.3248np(n))的精确算法,其中p(n)为问题中结点个数n的多项式函数,对比分析表明该时间复杂度低于采用传统方法得到的时间复杂度.

图论中最大独立集问题的精确算法

独立集问题是图论和组合数学中常见的NP-hard问题,在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一,主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为O（1.285-n）的精确算法,该算法在理论上得到了一般图的最大独立集的最优解。

最小顶点覆盖问题的加权分治算法

最小顶点覆盖问题是组合优化中经典NP—Hard问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设置一组相应的权值，以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题，并通过加权分治技术分析得出该算法的时间复杂度为O（1．255n），优于常规分析下的时间复杂度O（1．325n）。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。

容斥原理在汉密尔顿问题中的应用

容斥原理是组合数学中的经典的计数方法,该原理的基本思想是:先不排除重叠的情况,把包含于某种性质的所有对象的数目先计算出来,然后再把重复计算的数目排斥出去.针对汉密尔顿问题,[15]利用邻接矩阵给出了判断一个图是否为汉密尔顿图的充要条件.本文将结合容斥原理给出汉密尔顿路径存在性的一个判别条件,并给出汉密尔顿路径的计算公式.