解 packing 及 CNF-SAT 问题的拟物拟人方法

提出拟物拟人方法．论述了如何按此种方法为ＮＰ难问题设计出高效实用的快速求解算法．作为例证，所得出的关于ＣＮＦ－ＳＡＴ问题及ｐａｃｋｉｎｇ问题的算法，其先进性在国际竞赛及工业生产中得到了显示．     

关于SAT问题物理模型猜想的一个反例

针对关于ＳＡＴ问题物理模型的一个猜想，得到了该猜想成立的必要条件，然后构造出反例，说明该猜想是不成立的，同时指出，考虑到“算法吸引区”的存在，这并不降低应用该物理模型求解ＳＡＴ问题的良好的现实效果。     

提高预卜精度的一个方法

本文指出,预卜问题,往往在未来点上隐存着某种约束条件。如能将此条件定出并引进预卜方程则所得预卜值之精度必有提高。作为简明的例证,我们在[5]的基础上进一步处理了曲线长度预卜问题。所得之结果,在所示的范围内精度有明显的提高。     

用新预卜方法求空间无解析表达式曲线的长度

预卜问题非常困难，但在未来点上往往十分自然地隐存着某种严格的自然约束条件．如能将此种条件引进预卜方程必将极大地提高预卜的精度．按此途径完成了寻求空间无解析表达式曲线长度的工作．严格地证明了未来点上的约束条件的成立．实验验证说明预卜精度得到了极大的提高．     

预测Au_（13-75）团簇基态结构的启发式算法

针对具有NP难度的团簇结构预测问题,提出启发式求解算法——TP-ISDO作算法.该算法包括两阶段局部搜索、内部操作、表面操作和扰动操作.利用TP-ISDO算法预测了Aun（13≤n≤75）团簇的基态结构,其中Au团簇采用Sutton-Chen势能函数模型描述.实验结果表明,该算法能快速地得到Aun（13≤n≤75）团簇的当前已知最低能量结构.特别是对于Au58团簇,得到了两种新构型,这两种构型都是10面体结构,它们的势能值分别为-15648.5689和-15648.8754能量单位,小于当前已知的最低势能值.     

六角系统的点强全色数

对图G及正整数k,映射σ：VUE→{1,2,…,k}满足：（1）任意e1,e2∈VUE,如果e1,e2是相邻或相关联的,则有σ（e1）≠σ（e2）;（2）对u,v,w∈V（G）,uw,vw∈E（G）,uv￠E（G）有σ（u）≠σ（v）,则称σ为G的一个k-点强全染色,并且xτ^vs（G）={k｜存在G的k点强全染色},称为G的点强全色数．研究了六色系统图G的点强全色数,得到△（G）＋l≤xτ^vs;（G）≤△（G）＋2,其中△（G）,xτ^vs（G）分别表示G的最大度和点强全色数．     

基于局部搜索策略的车间作业调度问题的算法研究

为车间作业调度问题提供了一个快速、易于实现的近似算法．该算法基于局部搜索策略,采用特殊的邻域构造方法,即邻域的构造仅与关键路径上的工序相关．该算法找到了所测试的14个标准算例中12算例的最优解,而且在PⅡ233的计算机上每个算例的计算时间不超过1s。     

求解车间作业调度问题的快速禁忌搜索算法

针对车间作业调度问题的难解性，提出了一种求解该问题的快速禁忌搜索算法．该算法是按照禁忌搜索算法的一般步骤来进行设计的，在设计过程中对于算法所涉及到的初始解问题、邻域构造问题以及禁忌表长度的选取等问题给出了旨在减少算法计算时间，提高算法优度的解决方案．该算法找到了所测试的21个标准算例中18个算例的精确最优解，而且在PⅡ233的计算机上每个算例的计算时间不超过2s。     

关于相对化的P与NP问题的若干研究

研究相对化的Ｐ＝？ＮＰ问题，提出了矛盾天书、相对天书和绝对天书的概念，证明了这些天书的客观存在性，并具体地构造了一个矛盾天书和一个ＮＰ集类之外的相对天书．结论对利用现有关于相对化Ｐ＝？ＮＰ问题的成果来研究ＮＰ问题将产生有益的影响     

关于布尔线路计算模型的注记

本文给出了一种布尔线路的编码方案.证明了有关布尔线路编码中的两个定理,其中定理1表明对布尔线路这种计算模型,没有类似于图灵机的递归式定理那样的结论;定理2表明对于布尔线路计算模型,存在类似于图灵机中的Smn定理那样的结论.另外,本文还证明了一个有关布尔线路宽度的定理,此定理表明,布尔线路的宽度与计算能力无关.