-
题名机械手抓取排序问题(MSP)的最小权匹配算法
- 1
-
-
作者
陈刚
徐青川
-
机构
西安交通大学管理学院
-
出处
《西安科技大学学报》
CAS
北大核心
2005年第4期495-498,共4页
-
基金
国家自然科学基金项目(B类-70028102)
-
文摘
介绍了中药电子调配中心机械手抓取排序问题(MSP),并分析描述了其运行过程;在分析中药电子调配中心机械手抓取药材运动过程的基础上,建立了MSP的网络模型,并给出了求解MSP的“最小权匹配算法”;对“最小权匹配算法”的证明及实例研究表明,最小权匹配算法具有性能比为3/2的优良性质,应用该算法求解MSP可较好地提高计算效率。
-
关键词
中药电子调配中心
机械手抓取排序问题(msp)
旅行商问题(TSP)
近似算法
-
Keywords
preparing center of Chinese herbs
manipulator-snatching scheduling problem (msp)
traveling salesman problem(TSP)
approximately arithmetic
-
分类号
TN911
[电子电信—通信与信息系统]
-
-
题名机械手抓取排序问题(MSP)研究
- 2
-
-
作者
徐青川
张何之
-
机构
西安交通大学管理学院
-
出处
《西安工程科技学院学报》
2003年第4期326-329,共4页
-
基金
国家自然科学基金资助项目(B类-70028102)
-
文摘
介绍了机械手抓取排序问题(MSP)并描述了其运行过程,建立了MSP的网络模型并给出了求解方法“η72算法”.通过对“η72算法”的讨论、证明及实例研究表明,应用该算法求解MSP可较好地提高计算效率,并具有性能比为2的优良性质.
-
关键词
中药电子调配中心
机械手抓取排序问题
msp
旅行商问题
TSP
近似算法
网络模型
中医药现代化
-
Keywords
preparing center of Chinese herbs
manipulator-snatching scheduling problem (msp)
traveling salesman problem (TSP)
approximately arithmetic
-
分类号
R2-03
[医药卫生—中医学]
TP241
[自动化与计算机技术—检测技术与自动化装置]
-
-
题名SAT问题可多项式归结到MSP问题
被引量:4
- 3
-
-
作者
樊硕
姜新文
-
机构
国防科技大学计算机学院
-
出处
《计算机科学》
CSCD
北大核心
2012年第11期179-182,共4页
-
基金
国防科技大学校预研基金资助
-
文摘
针对文献[1]中提出的MSP问题(定义见正文),从SAT问题出发,给出SAT问题到MSP问题的多项式归结,进而给出MSP问题NP完全性质的另一种证明。
-
关键词
msp问题
SAT问题
多项式归结
NP完全性
-
Keywords
msp problem
SAT problem
Polynomially reduction
NP-completeness
-
分类号
TP301.5
[自动化与计算机技术—计算机系统结构]
-
-
题名MSP问题NP完全性研究
被引量:4
- 4
-
-
作者
吴添君
姜新文
-
机构
国防科技大学计算机学院
-
出处
《计算机科学》
CSCD
北大核心
2015年第7期12-14,27,共4页
-
基金
国家自然科学基金(61272010)资助
-
文摘
针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
-
关键词
msp问题
NP完全
问题归结
相变
-
Keywords
msp problem
NP-complete
problem reduction
Phase transition
-
分类号
TP301.5
[自动化与计算机技术—计算机系统结构]
-
-
题名特殊形式和结构的MSP问题NP完全性研究
- 5
-
-
作者
马兰
刘新
朱哲
-
机构
湘潭大学计算机学院网络空间安全学院
-
出处
《计算技术与自动化》
2021年第3期78-83,共6页
-
基金
国家自然科学基金资助项目(61272010)。
-
文摘
针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化。以简化证明为导引,提出一种特殊形式和结构的MSP问题。而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义。因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明。类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究。
-
关键词
msp问题
多项式归结
NP完全性
-
Keywords
msp problem
polynomially reduction
NP-comlete problem
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名Z-H算法正确性证明第四次改写
被引量:5
- 6
-
-
作者
姜新文
王琪
姜子恒
-
机构
国防科技大学计算机学院
-
出处
《计算技术与自动化》
2010年第3期35-48,共14页
-
文摘
提出多级图简单路径求解问题,我们称之为MSP问题。给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性。最后通过将HC问题(哈密顿图判定问题)多项式归结成MSP问题,证明MSP问题的NP完全性质。本文极大地简化文献[6,7]中αβ引理的证明,特别是对证明过程中的各种情形进行分割,将一个巨大的证明分成系列引理。
-
关键词
算法
msp问题
HC问题
NP问题
NP完全问题
-
Keywords
algorithm
msp problem
HC problem
NP problem
NP–complete prolem
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名基于GA的分布式任务调度算法的研究
被引量:4
- 7
-
-
作者
金可音
蒋伟进
-
机构
株洲工学院计算机系
-
出处
《计算机工程与应用》
CSCD
北大核心
2003年第13期106-108,共3页
-
基金
湖南杰出青年基金资助项目(编号:02JJYD012)
-
文摘
任务调度问题是一个强NP难题,算法研究是它的一个重要研究方向,智能Agent技术研究和应用开发在AI领域和分布环境下更具研究价值。分析了实时智能监控系统作业调度问题的特点,提出了结合GA和MAS技术的新的调度策略及算法。应用表明,该算法具有很好的可扩展性、适应性和稳定性。
-
关键词
遗传算法
智能多代理系统
调度策略
多处理器调度问题(msp)
-
Keywords
genetic algorithm(GA),intelligent multi agent system(IMAS),task scheduling policy,Multiprocessor Scheduling problem(msp)
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名哈密顿图判定问题的多项式时间算法
被引量:3
- 8
-
-
作者
姜新文
-
机构
湘潭大学计算机学院·网络空间安全学院
国防科技大学计算机学院
智能计算和信息处理教育部重点实验室
-
出处
《计算机科学》
CSCD
北大核心
2020年第7期8-20,共13页
-
基金
国家自然科学基金(61272010)。
-
文摘
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完全问题
多项式时间算法
-
Keywords
msp problem
HC problem
NP-comlete problem
Polynomial time algorithm
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名需求连续的无向网络上最小距离和问题算法
- 9
-
-
作者
马鸣明
王成恩
张士廉
-
机构
中国科学院沈阳自动化研究所
-
出处
《机械设计与制造》
2001年第6期34-37,共4页
-
基金
国家自然科学基金重点项目(79931000)资助
-
文摘
设施位置优化决策是运筹学中的重要领域和供应链战略规划的一个很重要的部分。企业在建立分散的服务系统时,会面对如何选择服务设施建立位置才能使设施与客户距离的平均值最小的问题。这里将运筹学与图论相结合,提出的有连续需求无向网络上的 MSP(MiniSum problem最小距离和问题)算法,并开发了一个基于此算法的计算机程序。此算法能够解决任意平面图上的最小加权距离总和问题,并且以离散方法代替导数方法来寻找图上距所有需求的加权距离总和最小点的位置。这里对所提出的算法进行了数值例子验证,证明本算法由于避免T NP问题,所以能够在较短的时间里求出可行解。
-
关键词
位置决策
最小加权距离总和问题
1-median问题
供应链管理
-
Keywords
Facility location
Weighted minisum problem (msp)
1 - median problem
-
分类号
F270
[经济管理—企业管理]
O22
[理学—运筹学与控制论]
-
-
题名ZH算法的性质及一种新视角分析
- 10
-
-
作者
李鹏坤
姜新文
盖方宇
-
机构
国防科学技术大学计算机学院
-
出处
《计算技术与自动化》
2017年第2期104-108,共5页
-
基金
国家自然科学基金项目(61272010)
-
文摘
文献[1]提出的MSP问题是一个NP完全问题。为了求解MSP问题,文献[1]给出了ZH算法。本文以ZH算法为研究对象,剖析ZH算法主要过程,从新的角度解读其作用,给出并证明ZH算法的两条重要性质——顶点边集守恒性质和顶点边集存在性质。对算法过程和作用的新视角分析为MSP问题的研究提供重要参考,ZH算法的重要性质也为算法的正确性证明提供帮助。
-
关键词
msp问题
ZH算法
算法分析
算法性质
-
Keywords
msp problem
Z H algorithm
aigorithm analysis
algorithm properties
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-