共查询到20条相似文献,搜索用时 109 毫秒
1.
2.
3.
4.
本文首次提出了中国邮递员问题的推广问题-水灾地区邮递员问题,并对解的存在性给出了一系列的充分条件、必要条件及充要条件,得到了求解该问题的一个多项式算法。 相似文献
5.
本文首次提出了赋权有向图上中国邮递员问题的一个推广-战争地区邮递员问题,并对解的存在性给出了若干充分条件和必要条件,得到了求解该问题的一个多项式算法。 相似文献
6.
对于一类非单调线性互补问题提出了一个新算法:高阶Dikin型仿射尺度算法,算法的每步迭代.基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向,再适当选取步长,得到了算法的多项式复杂性。 相似文献
7.
8.
9.
点带约束成本的最短路问题 总被引:6,自引:0,他引:6
本文提出了点带约束成本的最短路问题,证明了该问题是NP-完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为O(mn^2)的算法,对最小点成本最短路问题,给出了一个时间复杂性为O(n^2)的算法。 相似文献
10.
一类线性规划逆问题及解法 总被引:4,自引:0,他引:4
本文讨论了逆LP问题的更一般的情况,这里称它为广义逆LP问题,即在知道了一部分变量和价值系数的条件下,求余下的未知的变量和价值系数,将它们合起来组成给定的LP问题的最优解。显然若知道全部价值系数就成为LP问题;若知道全部变量就成为逆LP问题,它是在根据研制应用软件时提出的。文中给出了解广义逆LP问题的算法,并成功地用于“宏观经济调控系统”等应用软件的研制中,对要解决的实际问题,给出了强多项式算法。 相似文献
11.
IIntroductlonWrseProblem ofCombinatorial Optunatlon has ttrartedmore砒iemion ofresearchersrecentlx It Is irst nroPosed br D·Burton and Ph·L·h尬 in[11,拙er that J.Zhang,Z.Ma,M.Catnd oth删h印儿done some r田earo work on them陀r%pr加咖s Of shortest path,mat山lug,*].---*1fill sp皿D*旷r%,*砒m皿m伽n山阻111tim c毗,*%r01讥扯所肥出饲811加妙-5].讪出把papers l皿vs conhe their modd onthe suppooltlonth时 sh耐est p毗h,mimmum spanningtree,matd止ng and so on are一、n.h "aner [61,D.Burton… 相似文献
12.
求解运输问题的一种新算法 总被引:7,自引:2,他引:5
本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijk-stra算法扩展到可能出现负边权的运输问题。与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时)。 相似文献
13.
The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n^3). 相似文献
14.
本文通过研究匹配问题的实例空间,匈牙利算法和解空间三者之间的关系,指出S实例空间的数目与问题复杂度之间的关系既不是充分也不是必要的,而如何对问题的解空间进行合理的分解才能是问题的关键。 相似文献
15.
16.
迄今为止,组合拍卖竞胜标问题并不存在一个多项式时间复杂度的算法,其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。它是一个NP难问题,也是组合拍卖机制设计中的难题之一。而有穷损害优先方法是纯粹递归论中的一个十分重要的现代方法,特别对NP难问题求解算法的设计,对研究依复杂度决定的偏序结构的构造是一个很基本的有用工具。因此,本文提出根据组合拍卖的内在特性,将各不同的拍卖商品按照拍卖机制的要求,并结合其自身的协同价值等因素,设定一个优先序,然后采用有穷损害优先法有效有序地解决。 相似文献
17.
1.引言 设A(c)=(aij(c))是n阶实矩阵,其元素aij(c)(i,j=1,…,n)是参变量c=(C1,…,cn)T的实解析函数,λ1(c),…,λn(C)是矩阵A(c)的特征值,λ1,…,λn是给定的实数,代数特征值反问题[4]就是研究如何求解实的c,使A(c)的特征值为给定的λ1,…,λn. 假设给定的n个数λ1,…,λn互异,且问题的解存在(解不存在时可考虑某种形式的最小二乘解),过去的研究一般是直接研究或将问题转化为如下等价的非线性方程组 det(A(c卜人I)一0, i= 1,…,… 相似文献
18.
Andrzej Mróz 《代数通讯》2013,41(6):2005-2036
Let Λ be the four subspace algebra. We show that for any Λ-module M there exists an algorithm (up to the problem of finding roots of the so-called characteristic polynomial of M) with relatively low polynomial complexity of determining multiplicities of all direct summands of M. Moreover, we give a fully algorithmic criterion for deciding if two Λ-modules M and N are isomorphic. 相似文献
19.
Given a network with several weights per node and several lengths per edge, we address the problem of locating a facility on the network such that the convex combinations of the center and median objective functions are minimized. Since we consider several weights and several lengths, various objective functions should be minimized, and hence we have to solve a multicriteria cent-dian location problem. A polynomial algorithm to characterize the efficient location point set on the network is developed. Furthermore, this model can generalize other problems such as the multicriteria center problem and the multicriteria median problem. Computing time results on random planar networks considering different combinations of weights and lengths are reported, which strengthen the polynomial complexity of the procedure. 相似文献