最小树的一般算法

本文根据设计并行算法的基本原则,给出了最小树的两个对偶定理.在此基础上,建立了两种对偶的同步并行算法的雏型.这两种算法恰恰在对偶的意义下,概括了以往的最小树算法.     

具有限制的最小 k一个边不交支撑树问题

本文推广了刘振宏等具有次限制最小树算法,给出了求具有限制的最小 k 个边不交支撑树算法.该算法已在 IBM-PC 机上用 Fortran 语言实现,其时间复杂性为max{O(k~2|E|~2|V|~2),O(k~3|V|~4|E|)}.     

λ_5-geometry中的Steiner树问题(Ⅰ)

本文首先提出了 λ5-geometry中的 Steiner最小树问题 .讨论了 λ5-ge-ometry中的 Steiner最小树的若干性质 ,并给出了给定点数为 3或 4时 Steiner最小树的基本结构 .     

最小树图的Hamilton性及全部最小树的生成

对给定的连通图G,树图T(G)的Hamilton性,首先由Cummins所证明。稍后,Kamae给出另一构造证明,并用于树的生成。本文将研究一个赋权图G所有最小树的一些性质。主要结果如下:(1)对任意赋权图G,证明了最小树图T_(min)(G)的Hamilton性;(2)根据构造性证明,给出生成全部最小树的算法。     

最小树问题的全部解

<正> 以某些实际问题(如管道设计、通讯网建设等)为背景,图论中的最小树问题引起人们的广泛兴趣.自从 Kruskal 提出三种基本的构造法以后,各种算法实现途径相继出现,使这一问题得到完满的解决.然而,实际问题往往不能满足于求出一个最小树,而希望兼顾其它目标,在若干最小树中进行再选择.这就要求我们讨论最小树问题的全部解.在已有文献中,求全部支撑树已有较成熟的算法,尤其是文献[4]提供的算法可以将全部支撑树按权的大小依次列出.从理论上说,可以认为这些结果已经包含了求全部最小树问题.作为另一种途径,本文将着重讨论最小树问题全部解的性质,并由此建立求全部解的广探法(求全部支撑树的 Mayeda-Seshu 算法的推广).     

切触有理插值函数的新算法

切触有理插值函数的算法大都是基于连分式进行的,其算法的可行性大都是有条件的,且有理函数次数较高,计算量较大.文章利用拉格朗日插值的性质和分段组合的方法,给出了一种新的切触有理插值算法,并给出误差估计且将其推广到向量值切触有理插值情形.较之其他算法,具有有理函数次数较低、计算量较小、算法无条件性、无极点、满足高阶导数插值条件等优点.     

正多边形顶点集上的斯坦纳最小树

众所周知,覆盖一给定点集A的最小树T是所谓的斯坦纳最小树,简记为SMT.T中的顶点集记为V(T),V(?)A,而S=V-T中的点即为斯坦纳点。SMT的构作及其基本性质可见文献[1]及[2]。1977年Garey和其他人证明了离散的斯坦纳问题是属NP-complete类,从而很少有希望找到SMT的有效算法了。故斯坦纳问题研究中的另一方     

λ5—geometry中的Steiner树问题（Ⅰ）

本文处先提出了λ5－geometry中的Steiner最小树问题，讨论了λ5－geometry中的Steiner最小树的若干性质，并给出了给定点数为3或4时Steiner最小树的基本结构。     

λ5-geometry中的Steiner树问题( )

首先研究了λ5-geometry中4个点的Steiner最小树的某些特性,然后证明了对于λ5-geometry中的给定点集P,必有P的一个Steiner最小树,其Stein-er点在P的前2n/3代格点中.     

多点收缩混沌优化方法及全局收敛性证明

针对目前混沌优化算法在选取局部搜索空间时的盲目性,提出一种具有自适应调节局部搜索空间能力的多点收缩混沌优化方法.该方法在当前搜索空间搜索时保留多个较好搜索点,之后利用这些点来确定之后的局部搜索空间,以达到对不同的函数和当前搜索空间内已进行搜索次数的自适应效果.给出了该算法以概率1收敛的证明.仿真结果表明该算法有效的提高了混沌优化算法的性能,改善了混沌算法的实用性.     

最小树的层次算法及全部最小树动态结构

最小树问题在国民经济中有着广泛的应用。本文提出不同于著名的kruskal算法[1]及其他算法的层次算法,并推导出揭示最小树不变量的枝杈确定性以及边可作为最小树树枝的充要条件,最后得出全部最小树的动态结构。由于实际选用最小树时还经常需要兼顾其它具体     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

最小双权树

本文根据一个实例建立了在双权无向网络中求最小双权树的多目标网络模型，提出了最小双权树和临界最小树子图的概念，并给出了这个模型的一个有效算法．     

一种基于竞争策略的稀疏多元多项式插值算法

提出了一个有限域上的基于竞争策略的稀疏多元多项式插值算法,改进了Javadi和Monagan在2010年提出的概率性插值算法.对n个变元,t个非零项的多元多项式f进行插值,Javadi/Monagan算法要求给定f的全次数上界d,为确定变元x_j在第i个单项式中的次数,需要从O到d做d+1次根测试,每个变元测试次数为O(td).改进算法设计了两个子算法并采用竞争策略用尽可能少的插值点准确计算变元x_j在多项式f中的次数集,使得测试次数降为O(td'),其中d'为变元x_j在f中出现的次数集的基数,因而减小了测试次数及根冲突的概率.在Maple环境下实现了改进算法,Zippel算法和Javadi/Monagan算法,给出了测试用例对3种算法的插值点个数及其CPU运行时间进行了比较.     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

关于有向图上的最小树形图——具等双回路特性的情况

如果我们要在某些城镇之间建立联系这些城镇的线路(例如电线等),假设线路的交叉点只能在代表这些城镇的点上,如何能使设立的线路总长度最短呢?这类问题在图论上叫无向图上的最小树问题。又如渠道设计中,有一个水源,要把水引到若干个点上,要求渠道的分叉点必须是在给定的点上,希望设计的渠道路线总长度最短。它和最小树问题的区别在于两点之问水流是有方向的,称谓有向图上的最小树形图问题。这些问题在理论上和实际应用中均有一定的意义。最小树形图和一类有向截集有对偶性的联系。寻求最小树的方法要点是,对每一点,在以其为顶点的所有边中选一条最短的,然后把由此产生的部分图中的每个连通片中收缩成一点,对新图重复上述步骤。求最小树形图时,对每一点取指向这个顶点的一条长度最短的弧。收缩时,不是收缩一个连通片,而只能收缩每个连通片中的一条回路。因此前者的收敛速度要比后者快。本文对于具有从无向图到有向图过渡性质的一类有向图提供了一个算法,寻求其最小树形图时,可以收缩一个连通片。     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

近似邻近点算法收敛性的一个注记

近似邻近点算法在最优化理论与方法研究中具有重要作用.在不同误差准则下,近似邻近点算法具有不同的收敛性.利用极大单调算子等工具给出了一个具体的例子,解释了在一些误差准则下近似邻近点算法的收敛性.     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题,证明了该问题是ＮＰ－完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法,对最小点成本最短路问题,给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。