NP完备问题相关论文
已研究多年的底盘装载问题属于NP完备问题,索的解决方法多为启发式方法。本文讨论了约束 盘装载问题,并提出一种基计算机的启发式方法......
提出了一种适用于板料排样优化的基于满排方案的启发式搜索算法,它克服了现有众多排样算法执行效率低、对板料多规格缺乏支持的缺......
设有整数集S={r1,r2;p1,p2,…,pn},这里ri≥0,pj>0(i=1,2;j=1,2,…,n),寻找一个S的最优分划P=(S*1,S*2)使得:(1)ri属于不同子集,(2)S*1与S*2中元素总和较大者尽可能地小.这是一个NP-完备问题,本文给出一个线性时间近......
本文提出一个构造的NP完全问题RHC并证明其NP完全性。在此基础上,通过分析通用图灵机带头移动的次数,讨论了通用图灵机上任一求解RHC的算法的复......