一个NP─完全问题的求解复杂性剖析

本文提出一个构造的ＮＰ完全问题ＲＨＣ并证明其ＮＰ完全性。在此基础上，通过分析通用图灵机带头移动的次数，讨论了通用图灵机上任一求解ＲＨＣ的算法的复杂性。分析结果揭示了在简单计算模型（定义见正文）上寻找一个对满足ＲＨＣ的任意输入，而不是对某些特殊实例都能正确求解的算法的困难性。根据本文的讨论，我们认为，给出本文分析的严格论证或许只是时间问题。

关于约束底盘装载问题的一种启发式方法

已研究多年的底盘装载问题属于ＮＰ完备问题，关于它的解决方法多为启发式方法．本文讨论了约束底盘装载问题，并提出了一种基于计算机的启发式方法．实例表明，该方法能较好地解决约束底盘装载问题．

一类分批排序问题的复杂性分析及近似算法

探讨了分批排序问题,分析了极小化加权总完工时间问题1｜B,rj∈｛0,r｝｜!!jCj的复杂性,证明了此问题的NP-完备性,并对一类特定问题进行了研究,给出了解决问题的近似算法,证明了其可行性,进而对算法的性能进行了分析,结果表明算法有效地降低了计算复杂度。

带核集分划问题的一个线性(1/7)-近似算法

设有整数集Ｓ＝｛ｒ１，ｒ２；ｐ１，ｐ２，…，ｐｎ｝，这里ｒｉ≥０，ｐｊ＞０（ｉ＝１，２；ｊ＝１，２，…，ｎ），寻找一个Ｓ的最优分划Ｐ＝（Ｓ＊１，Ｓ＊２）使得：（１）ｒｉ属于不同子集，（２）Ｓ＊１与Ｓ＊２中元素总和较大者尽可能地小．这是一个ＮＰ－完备问题，本文给出一个线性时间近似算法，它的近似界为８７．

用神经网络求解划分问题

划分问题是一类常见的 NP完备的优化问题 ,本文利用推广的 Hopfield神经网络模型解决了划分问题 ,并取得了较好的效果 ,为这个问题的解决提供了一条新的途径。同时 ,也为解决其它优化问题提供了有益的启示。

板料优化中基于满排方案的启发式搜索算法

提出了一种适用于板料排样优化的基于满排方案的启发式搜索算法 ,它克服了现有众多排样算法执行效率低、对板料多规格缺乏支持的缺陷 。