赋有提前或延误惩罚的单机排序问题的动态规划算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明［１］：赋有延误惩罚的单机排序问题是强ＮＰ－完全问题，没有多项式时间算法。笔者曾证明［２］：如果附加条件ｐｉ≥ｐＪｐｉ／ｗｉ＞ｐｊ／ｗｊ对于所有的ｉ≠ｊ（ｉ，ｊ＝１，２，…，ｎ）成立，则该问题有伪多项式时间算法。现在研究如何用动态规划方法求解这类排序问题。     

四元素空间中广义正则函数的一类变态P－H问题

四元素空间中广义正则函数的一类变态Ｐ－Ｈ问题李生训黄沙（河北轻化工学院石家庄市０５００１８）（河北师范大学石家庄市０５００１６）１问题的提法设Ｂ４为四元素空间，基底为１，ｉ，ｊ，ｋ（其中ｉ２＝ｊ２＝ｋ２＝－１，ｉｊ＝ｋ＝－ｊｉ）．对于四元数ｕ∈其中ｕ...     

插值曲线的构造和光滑问题

通过对Ｂ－Ｂ曲线和Ｌａｇｒａｎｇｅ曲线相互关系的研究，给出端点信息为ｄｉｄｔｉＧ（ｊ）（ｊ＝０，１，ｉ＝１，２，…，ｒ＜［ｄ／２］），而内点信息为Ｐｉ＝Ｇ（ｔｉ）（０＜ｔｉ＜ｔｉ＋１＜１，ｉ＝０，１，…，ｄ－２ｒ＋２）的ｄ次多项式曲线Ｈ（ｔ）的一种构造方法，从而解决了“既插值给定的内点信息，又在连接点处ｒ一阶光滑”的关键性问题     

由位置码性质所确定的集合的Hausdorff维数

设Ｆ为一Ｍｏｒａｎ集，Ω＾ｗ＝П↑∞↓ｉ＝１｛１，２，…，ｎ｝，φ为Ω＾ｗ→Ｆ的一个相关的自然满射；Γｉ，…，Γｋ两两不交且∪↑ｋ↓ｉ＝１Γｉ＝｛１，２，…，ｎ｝。令Ｈ（Γｉ，…，Γｋ）＝φ（Ｈ（Γｉ，…，Ｆｋ）），此处Ｈ（Γｉ，…，Γｋ）＝｛σ∈Ω＾ｗ：ｌｉｍ↓ｌ→∞Ｃａｒｄ｛１≤ｉ≤ｌ：σ（ｉ）∈Γｊ｝／ｌ＝Σ↓ｉ∈Гｊｃｉ，１≤ｊ≤ｋ｝。这里ｃｉ≥０且Σ↑ｎ↓ｉ＝１ｃｉ＝１。得到了下列结论：     

关于差分方程un＋r=Σ（n＋r,i=1）aiun＋r—i—bn的显示解

给出了差分方程｛ｕｎ＋ｒ＝Σ（ｎ＋ｒ，ｉ＝ｉａｉｕｎ＋ｒ－ｉ＋ｂｎ ｕｉ＝ｃｉ ｉ＝０，１，…，ｒ－１的一个显示解，ｕｎ＝ｄｎ＋Σ（ｎ，ｉ＝ｄｎｉｋ＋ｋ＋２…＋ｉｋｉ（Σ（ｉ，ｊ＝１ｋｊ）！Π（ｉ，ｊ＝１）ａｉｋｊ／Π（ｉ，ｊ＝１）ｋｊ！．     

三类Km—E（G）型的色唯一性

本文讨论了形如（∪＾ｒ，ｉ＝１Ｐｎｉ）∪（∪ｓｊ＝１Ｃｍｊ）∪（∪ｔｋ＝１Ｐｑｋ）；∪ｔｉ＝１Ｔｎｉ（ｌ＾（ｉ）１，ｌ（ｉ）２，ｌ＾（ｉ）３和比（∪ｒｉ＝１Ｐｎｉ）∪（∪ｔｊ＝１Ｔｍｊ（ｌ＾ｊ）１，ｌ＾（ｊ）２，ｌ＾（ｊ）３））三类并图在不可约束条件下的补图的色的唯一性，通过比较图的伴随多项式的前四项系数，证明了这些结果。     

正值幂函数乘积的极小和问题

研究下述非线性规划ｍｉｎ↓ｘ∈ＸΣ↑ｓ↓ｊ＝１П↑ｋ↓ｉ＝１ｆｉ＾ｐｊ＾ｊ（ｘ）这里ｆｉｊ：Ｘ→Ｒ＾＋，ｐｉｊ≥０，Σ↑ｋ↓ｊ＝１ｐｉｊ＝１，ｉ＝１，２，…，ｋ，ｊ＝１，２，…，ｓ．Ｘ是Ｒ＾ｎ中非空紧集。借助加权平均值不等式将问题转化为含参数函数之和的极小化问题。证明了最优参数只需取一些特定的值。特别当ｆｉｊ是线性齐次函数，Ｘ为凸多面体时，其最优解必定可以在Ｘ的顶点达到。同时给出了可行点为最优解的     

乘积矩阵的奇异值估计

本文给ｍ个矩阵乘积的奇异值估计：ｍ∑ｊ＝１ｉ（ｊ）＝（ｍ－１）ｎ＋ｉ＾ｍａｘ（ｍ）Ⅱ（ｊ＝１）σ＾（ｊ）ｉ（ｊ）≤σｉ≤（ｍ）∑（ｊ＝１）＝ｉ＋ｍ－１ｍｉｎ＾（ｍ）Ⅱ（ｊ＝１）σ＾（ｊ）,ｉ（ｊ）,１≤ｉ≤ｎ同时给出了（ｋ）∑（ｉ＝１）σｉ,＾（ｋ）Ⅱ（ｉ＝１）σｉ的一个下界。     

二阶微分方程的Mather集和拟周期解

考虑了二阶非线性微分方程ｘ↑．．＋ｘ＾２ｎ＋１＋∑↑ｌ↓ｊ＝０ｘ＾ｊｐｊ（ｔ）＝０，ｘ∈Ｒ＾１，其中ｐｉ（ｔ）是周期为１的函数，１≤ｉ≤ｌ≤２ｎ。证明了：如ｐｊ∈Ｃ＾２（Ｓ＾１），方程有Ｍａｔｈｅｒ集存在；对方程的一些特殊情形，证明了相应的Ｍａｔｈｅｒ集确是不变闭曲线，从而得到解的有界性。     

关于Negoita—Ralescu表现定理的改进与扩充一文的注记

研究了Ｌ模糊幂集Ｌ（Ｕ）分别与四种Ｌ晕集集合Ｌ（Ｕ）（ｉ＝１，２，３，４）之间的一一一对应关系，给出了ｉ＝３，４，情况的新的证明，改进了已有的证明。     

求解K-闭包问题的DNA算法

给出了解决K-闭包问题的DNA算法，进一步表明了用DNA计算来解决NP-完全问题是非常有前景的。     

子集和问题的扩展研究

基于文献所提出的子集和改进求解算法,我们提出了一些针对具体实际问题的改进方法。基本的思想是将子集和问题进行转化。实验和分析都显示我们方法的有效性。     

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

一个求解SAT问题的随机算法

本文中引入了一个求解满足性问题的随机算法。在该算法中,利用CNF公式转换为其对偶式——DNF公式,通过对满足DNF公式的真值赋值数Y作出估计。根据Y与2n比较结果,对CNF公式的可满足性进行估计并对其满足性进行判断。     

分组遗传算法用于图的着色

图的着色算法是一种典型的NP 完全问题 在系统地讨论了图的正常顶点着色、边着色以及全着色的有关理论的基础上 ,提出了基于分组遗传算法和启发式搜索的图的正常 k 点着色 ,正常k 边着色以及正常k 全着色的新型混合算法 ,提出了评价算法性能的标准 实验仿真结果表明 ,新型混合算法可以获得问题高质量的解 ,即对图进行着色所使用的颜色数接近图的色数     

大型BP神经网络学习算法

神经网络训练是一个ＮＰ完全问题，提出一种集成学习算法，理论分析与计算机模拟结果表明这种学习算法具有学习结果准确，学习速度快等特点，尤其适用于大型ＢＰ神经网络。     

遗传算法用于NP完全问题的求解

讨论了如何利用遗传算法求解布尔表达式的可满足性问题,并给出该结果对求解其他NP完全问题时的应用.     

DNA计算原理与发展

DNA计算是一种摸拟生物分子DNA的结构并借助分子生物技术进行计算的新方法,为NP完全问题的解决提供了一种全新的途径,具有广阔的应用前景。本文首先介绍了DNA计算的基本思想;然后综述了DNA算例及其模型;指出了DNA计算的应用及目前存在的问题;最后对DNA计算的发展前景进行展望。     

求解接点网络问题的DNA算法

利用DNA的二级结构——发卡构形，给出了求解接点网络问题的DNA算法．首先用DNA分子编码接点网络问题，然后利用DNA分子的自组装和形成二级结构的能力来求解问题．算法具有自动化实现计算的特点，计算所需的实验操作比Lipton提出的算法少，同时计算所需的DNA量也比Lipton提出的算法少．