检索结果-南通市图书馆

应用数学学报 1996年第1期19卷 33-38页

作者：张青富肖高奚陈开周西安电子科技大学数学系

本文给出了一种新的线性规划多项式时间算法．在此算法中，每步可沿一族方向中的一个进行线性搜索，同时，还使用了开关策略，从而大大减少了求逆矩阵的次数，最后，证明了算法经Ｏ（ｎＬ）次选代结束．

关键词：线性规划 Karmarkar算法多项式时间算法

关系模式最小基数候选关键字多项式时间求解算法

在线全文

学校读者我要写书评

暂无评论

计算机研究与发展 1995年第2期32卷 27-33页

作者：郝忠孝刘国华东北重型机械学院

文献［１］、［２］、［３］均明确指出，求一个关系模式的最小基数候选关键字问题是一个ＮＰ完全问题。作者在深入分析主属性在ＦＤ集、最小基数候选关键字关系模式和候选关键字集合中的结构特性的基础上，提出了同类属性集，同类主属... 详细信息

文献［１］、［２］、［３］均明确指出，求一个关系模式的最小基数候选关键字问题是一个ＮＰ完全问题。作者在深入分析主属性在ＦＤ集、最小基数候选关键字关系模式和候选关键字集合中的结构特性的基础上，提出了同类属性集，同类主属性组集族，自由、半自由同类属性集等概念。在此基础上，给出了一个求关系模式最小基数候选关键字的Ｏ（ｎ２ｐ）级算法。

关键词：候选关键字关系模式数据库多项式时间算法

基于局部self-concordant障碍函数的全牛顿步多项式时间算法(英文)

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2008年第1期12卷 1-15页

作者：金正静白延琴韩伯顺上海大学数学系上海200444

由Nesterov和Nemirovski^([4])创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concor... 详细信息

由Nesterov和Nemirovski^([4])创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.

关键词：运筹学线性规划障碍函数 self-concordant函数内点算法多项式时间算法

在线全文

学校读者我要写书评

暂无评论

约束正定式几何规划的一种多项式时间算法

工程数学学报 2002年第2期19卷 75-80,102页

作者：景书杰毕小山张可村焦作工学院基础部河南454159 西安交通大学理学院西安710049

利用了几何规划的特点 ,借助于对偶及矩阵分析的理论为约束正定式几何规划构造了一种内点算法 ,并证明了算法具有多项式时间收敛性 ,从而推广了张可村等 (1995 )文的结果。

关键词：约束几何规划多项式时间算法对偶理论凸规划

带有延迟时间下界的k-(n_1,1,…,1)-排序问题的拟多项式时间算法

在线全文

学校读者我要写书评

暂无评论

复旦学报（自然科学版） 2005年第2期44卷 224-230页

作者：殷志文沈靓复旦大学管理科学系上海200433

研究Wikum提到的关于带有延迟时间下界的k (n1,1,…,1) 链形结构排序问题的拟多项式时间算法,其中n1=2的情况己得到解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出此原来的算法更加有效的拟多项式时间算法.

关键词：多项式时间算法延迟时间排序问题下界链形结构加细

在线全文

学校读者我要写书评

暂无评论

哈密顿图判定问题的多项式时间算法

计算机科学 2020年第7期47卷 8-20页

作者：姜新文湘潭大学计算机学院·网络空间安全学院湖南湘潭411105 国防科技大学计算机学院长沙410073 智能计算和信息处理教育部重点实验室湖南湘潭411105

NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的... 详细信息

NP=?P(即NP是否等于P)的问题是计算机科学和数学中的重要问题。美国克雷数学研究院将其列为新千年七大困难问题之首,2005年Science将其列为25个困难问题之19。Science最近列出的125个亟待解决的重要问题中,第19个问题实质上就是NP=?P的问题。如果NP=P,对于很多困扰科学研究的困难计算问题,理论上就存在多项式时间算法来迅速求解它们。而现代密码学建立在NP≠P的假设之上。人们希望存在难解问题,希望基于难解问题构造加密算法,希望能够利用难解问题的求解复杂性对抗分析和攻击。如果NP=P,所有在NP≠P假定之上开展的计算研究都至少需要重新审视其意义。NP完全问题的求解复杂性决定NP=P是否成立。针对一个被称为MSP问题的新问题,文中提出了一个关于MSP问题的多项式时间算法,并给出了该算法的证明和时间复杂性分析。由于已经发表了十多个经典的NP完全问题到MSP问题的归结以及MSP问题到SAT问题的归结,因此MSP问题存在多项式时间算法这样一个研究结果对于研究NP=P有重要和积极的意义。

关键词： MSP问题 HC问题 NP完全问题多项式时间算法

在线全文

学校读者我要写书评

暂无评论

NP完全问题多项式时间算法研究

应用数学 2001年第S1期14卷 107-112页

作者：石海林马鞍山矿山研究院信息中心安徽243004

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )... 详细信息

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .

关键词： NP完全问题 LP技术多项式时间算法哈密尔顿回路 TSP问题群

在线全文

学校读者我要写书评

暂无评论

两个代理的单机排序问题的多项式时间算法

山西大学学报(自然科学版) 2012年第3期35卷 448-451页

作者：冯琪孙晓梅马冉尚卫萍郑州大学数学系中原工程学院理学院河南工程学院数学科学系河南理工大学数学与信息科学学院

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二... 详细信息

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.

关键词：排序多代理多项式时间算法