基因组Translocation排序问题的改进多项式算法

该文给出基因组 Translocation排序问题的一个改进多项式算法 .原算法所用存储空间为 O(n) ,时间复杂度为 O(n3) .文中改进算法仍采用 O(n)存储空间 ,时间复杂度为 O(n2 logn) .具体地 ,将计算 Translocation距离的时间复杂度由 O(n3)改进为 O(n2 ) ,将计算 Translocation序列的时间复杂度由 O(n3)改进为 O(n2 logn) .

一类线性规划问题的强多项式算法

对一类线性规划问题提出了一个强多项式算法．此算法可进行双向搜索．可行解集、目标函数的两个目标值以及相应的最优解，全部可行基与最优基可以一步求得，无需迭代．算法的复杂性为Ｏ（ｎ３＋ｎ２＋ｎ）。

关于ESAC网活性和有界性的一个多项式算法

寻找实际可行的多项式算法一直是Petri网应用的重要方面.给出了关于扩展强化非对称选择网(extended strong asymmetric choice nets,简称ESAC网)结构活和结构有界的一个判定算法.该算法可简单、有效地测试结构活结构有界的ESAC网的初始标识是否是活标识.ESAC网覆盖了自由选择网,因此,该算法应用范围较为广泛.

求基可行解一种概率意义下的多项式算法

本文对求线性规划问题的基可行解，给出一种改型算法，证明它对m个约束、n个变量的问题，当n≥2m时，为使求得一个基可行解的概率大于0．98，对m>24，所需迭代次数不超过（m＋3），而对m≥76，迭代次数已不超过（m＋1）．

基于五次多项式算法的机器人轨迹规划研究

为进一步保障机器人速度与加速度变化曲线的稳定性与光滑度,需优化轨迹规划算法。因此,文章以五次多项式算法为基础进行了机器人轨迹规划研究,通过五次函数拟合插值机器人各关节速度与加速度,并基于Matlab轨迹仿真与机器人试验验证,得出结论,五次多项式算法进行轨迹规划时,拟合曲线光滑度较高,可确保速度与加速度不发生突变状况,保障了机器人运动的平稳性;能保证机器人根据预定轨迹平稳过渡速度与加速度,提升了机器人运动精确性;可减少机构碰撞与干涉,延长机器人使用寿命。

用线性分式规划的多项式算法改进线性规划的Karmarkar方法

本文给出了解线性规划问题的一个改进的Karmarkar算法。它是把线性公式规划的多项式算法应用于线性规划问题而得到的一个两阶段下降算法,该算法的优点是:不必假设目标函教的极小值为零,不涉及势函数,迭代次数为o(nq),α参数可取I为最佳值。我们还提出了一种分离基解变量加速求解的方法。

一个整数瓶颈问题的两个多项式算法

讨论下列数学模型Ⅰ:求x=(x_1,x_2,…,x_n)适合条件{■a_(ij)x_j≥b_i (i=1,2,…,m) x_j≥0且整数(j=1,2,…,n)使f(x)■{c_jx_j}达到最小值,其中m＜n,a_(ij),b_i及c_j均为正整数。对该模型,建立了两个多项式算法,其复杂度均为O(n^2),并列举了一个数值例子．

定性因果与多项式算法的模型诊断方法

在基于模型的诊断方面，Ｒｅｉｔｅｒ最初提出了使用第一原理的诊断方法，但它应用于复杂物理系统时遇到很多困难。后来，Ｍｉｋｉｔｏ等人提出了使用定性因果与覆盖集的模型诊断方法，此方法有很大改进，但覆盖集的计算复杂费时。提出一种使用定性因果与多项式算法的模型诊断方法，此方法可以明显地减少诊断的计算量，并且对这种新算法的正确性给予了证明。

关于关系模式主属性判定的一种多项式算法

该文深入分析了主属性在关系模式中的结构特征,提出了化简独立复合环、独立简单环、化简双部属性函数依赖图等概念。在此基础上,给出了一个关系模式主属性判定的多项式算法。

工作流模型验证及分解的多项式算法分析

基于工作流的Petri网结构化建模方法,证明了工作流网的T不变量和P不变量的存在性、可覆盖性,给出了一个工作流模型完整性的充要条件,进一步得到了基于T不变量的多项式分解算法,与以往非多项式分解算法相比,克服了遍历的不足,降低了算法复杂度,给出的实例验证了算法的有效性.

带固定工件的单机排序问题1|FB,r_j,pmtn|Σ_jU_j的多项式算法(英文)

研究具有若干固定工件和自由工件,其中固定工件必须在指定时间窗内加工,而自由工件具有不同交工的时间,并且其加工可以中断的单机排序问题,其目标是极小化工件的误工数.该问题可以表示为1|FB,r_j,pmtn|∑_jU_j.首先讨论了问题的几个重要性质,以此为基础建立了求解该问题的动态规划算法,其时间复杂度为O(n^4+mlog m),其中m和n分别是固定工件数和自由工件数.

求关系模式所有最小基数候选关键字的一种多项式算法

本文深入分析了最小基数候选关键字在关系模式中的结构特征,提出了化简独立复合环、独立简单环、化简双部属性函数依赖图等概念。在此基础上 。

双权树形图的多项式算法

本文根据一个实例建立了在赋双权的有向图中求带参数的双权树形图的网络模型,通过求解一系列的问题P2(l),我们得到了求解该问题的多项式算法。

法向消元和线性规划强多项式算法

为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法.

单台机器E-T随机排序问题的多项式算法

本文研究排序问题中的E-T问题,工件在单台机器上加工,n个工件的加工时间都为整数p,相同的工期d为离散分布,满足∑mi=1P(d=ξi)=1,其中ξi为整数,目标是使E(∑(Ej+Tj))的期望值最小。应用贪婪算法和二分法思想,我们提出解决该问题的一个最优算法,并得出该算法的复杂性为O(nmlogp)。

运输问题的多项式算法──最小调整法

给出了运输问题的一种方法—最小调整法．和通常方法比较，这种方法具有直观、简单、计算量少、在计算机上容易实现及易于推广等优点。井区是多项式算法．

整数瓶颈问题的两个多项式算法

研究了一个特殊的整数瓶颈问题并给出了两个求最优解的多项式算法程序。通过对算例的分析可知该算法运行效率高。

多项式族稳定性判定问题的多项式算法

利用除零原则，多项式族稳定性的判定问题（系数仿射依赖于参数的情形）可以化为单参数秩２简单二次规划问题。本文用二次规划的理论、Ｋｕｈｎ－Ｔｕｃｋｅｒ条件，提出了此问题的一个多项式时间算法。可以看到许多重要的结果，如棱边定理和强Ｋｈａｒｉｔｏｎｏｖ定理仅是此算法的一个特例。作为简单应用，介绍了区间多项式族ｓｃｈｕｒ问题的一个具体算例。

K_（1，r）－free图的次限制树多项式算法

设Ｇ＝（Ｖ，Ｅ）为一连通图，ｄ＞０整数．Ｇ中存在生成树Ｔ，使得Δ（Ｔ）小于ｄ吗？这一问题已被证明是ＮＰ－完全的，故不太可能有多项式解法．本文证明了当Ｇ是Ｋ１，ｒ－ｆｒｅ时，则有Ｏ（ｎ２）的算法求出Ｇ的生成树Ｔ，使Δ（Ｔ）≤ｒ。

一个求半序集的最优碰撞数扩张的多项式算法

设Ｐ＝（Ｘ，≤）是一个半序集，Ｈａｂｌｂ等人与Ａ，Ｓｃｈａｆｆｅｒ同时证明了求Ｐ关于碰撞数的最优扩张的问题是Ｐ－问题；本文给出了一个求具有最小碰撞数的半序集的线性扩张的多项式算法。