求解可满足性问题的两个启发式策略

提出了两个用于求解可满足性（SAT）问题的启发式策略,数值实验表明,基于该策略的模拟退火算法的性能优于局部搜索算法,因此这两个策略是可行和有效的。     

求解可满足性问题的两个启发式策略

提出了两个用于求解可满足性(SAT)问题的启发式策略.数值实验表明,基于该策略的模拟退火算法的性能优于局部搜索算法,因此这两个策略是可行和有效的.     

关于1阶域论命题的可满足性

考察了语言Ｔ＝（＋，·０，１）上１阶域论命题的有限可满足性及无限可满足性，得到一些初步结论。对于整环及除环的情况也有类似或较弱的结论，结合Ｊ，Ａｘ的结果，可得到域论及整环理论中全称语句类的可判定性。     

一种求解多处理机调度问题的新算法

多处理机调度问题是“算法设计与分析”中的基本问题之一,它是一个NP问题.本文介绍了模拟退火技术,给出了求解多处理机调度问题的有效算法.该算法通用性强,效率高,其基本原理可广泛应用于求解大规模的组合优化问题.     

一种求解难SAT问题的改进DP算法

DP算法是求解SAT问题的最有效完全算法之一，论文分析和讨论了DP算法中的各种分枝文字策略，并基于对不满足解数估计的方法，提出了一个有效的分枝文字策略，实验结果表明，提出的改进DP算法对难SAT实例有较好的平均性能。     

基于DNA链置换的可满足性问题的计算模型

可满足性问题是经典的NP完全问题之一。本文建立了一个基于DNA链置换的可满足性问题的计算模型,可满足性问题的约束条件被映射成计算模型上的荧光个数,将可满足性问题中变量的两种取值(0和1)分别设计成不同的DNA链,通过DNA链置换反应,最后观察反应后的计算模型上荧光个数找出可满足性问题的可行解。该模型具有操作简单,结果便于观察和检测的优点。     

中介逻辑命题演算系统的可满足性的判定复杂度

[1]证明了中介逻辑的命题演算系统MP(见[2])中的每一合式公式可以分解为以形如p,p,～p,～p(p为原子命题)为基子句的析取范式,本文的主要结果为:判定以形如p,p,～p,～p为文字的子句集的可满足性问题是NP完全的。     

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

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

程序正确性证明中逻辑公式的可满足性

采用Herbrand定理及归结原理证明在程序证明中遇到的逻辑公式是可满足的。并给出了相应的算法;同时讨论了已知循环程序中循环不变式的求解方法。     

基于一阶理论的个性化定制需求可满足性研究

产品个性化定制在服装等产品生产中广泛使用,但是个性化定制需求的多样性等特点导致在判断生产商是否具备加工能力时存在困难。文中采用基于一阶逻辑描述生产线加工能力以及个性化定制产品需求的方式,基于该模型提出判断生产线能否满足个性化定制需求的方法,将个性化定制需求表示为逻辑公式,生产线的生产要素表示为一阶理论,通过检查需求公式是否是该理论的语义属性判断需求在某个生产线的可满足性。该方法可以在用户明确需求之后,根据生产商资源判断个性化定制需求的可满足性。     

基于改进的遗传算法求解3-SAT问题

针对求解3-SAT问题,提出了一种改进的混合遗传算法。该算法是基于局部搜索算法策略与SGA算法的基础上将三路划分快速排序算法与其相结合的一种改进。首先通过适应度函数对基准的调节,运用改进的三路划分快速排序,重新生成新的种群,这在算法延迟收敛的可能性及可满足范式无解的可能性方面能起到很好的抑制作用;其次通过实验证明,与同类算法比较,该算法加快了寻找最优解的速度。最后,验证了算法的有效性与可行性。     

无线传感器网络定位方法综述

介绍了国内外研究机构在无线传感器网络定位方法方面开展的研究工作,并对这些研究工作进行了归纳和总结.定位的基本方法分为距离式定位和非距离式定位.距离式定位是通过测量距离或角度进行位置估计,测量数据的精度对定位精度有很大影响.非距离式定位是通过节点间的hop数或估计距离计算节点的坐标,这种方法不需要测量距离或角度,利用估计距离代替真实距离,算法简单但精度不高.无线传感器网络中定位方法的应用需要针对不同的应用场合,综合考虑节点的规模、成本及系统对定位精度等要求来进行设计和选择.     

时变网络最大流问题的过剩流量收缩算法

时变最大流问题是最大流问题的一个推广．设图G=（y,A）是一个有向图且有唯一的发点s和收点P．图G中的每条弧（i,j）∈A都带有两个参数：弧上流的传送时间b（i,j,u）和弧的容量f（i.j.u）,它们都是时间u的函数．时变最大流问题就是找出从s到P满足容量约束的最大流,并要求此最大流的传送时间不能超过一个预先给定的时间限制T.假设：除发点外,流在其他任何顶点都不能等待;b（i.j.u）是正整数;l（i.j.u）是任意的非负整数．提出了该问题的一个过剩流量收缩算法,并讨论了这个算法的复杂度．最后,给出了一个数值算例。     

低秩张量补全算法综述

随着现代信息技术的快速发展,待分析的数据大都具有很复杂的结构。在获取高维多线性数据的过程中,部分元素可能丢失,低秩张量补全就是根据数据集的低秩性质来恢复出所有丢失元素。低秩张量补全是压缩感知理论的高阶推广,在数学上可以描述为核范数最小化问题。对求解低秩张量补全的核范数最小化模型的现有算法进行了综述。介绍了张量的基础知识和低秩张量补全模型,给出了低秩张量补全的几种主流算法,如:简单低秩张量补全、高精度低秩张量补全以及核心张量核范数的张量补全等,指出了现有低秩张量补全算法中值得研究与改进的方向。     

矩阵表示的子空间学习算法综述

线性子空间学习是较为流形的一种特征提取方法,而向量表示的子空间学习方法则是目前众多线性子空间学习方法之一.近年来人们针对这一方法的缺点和不足,提出了若干矩阵表示的子空间学习方法,这些方法都是向量表示的子空间学习方法的拓展.首先介绍了几种经典的向量表示子空间学习方法,进而对几种有代表性的矩阵表示子空间学习方法进行了综述并比较详尽地给出了这些算法的推导过程,同时对算法的有效性等问题进行了分析比较,提出了一些新的理论观点和见解.     

图的最大亏格综述(英文)

综述了近30年来关于图的最大亏格,以及它与其他不变量之间关系的重要研究进展,包括最大亏格与图的连通性、图的直径、图的染色数和图的z-因子之间的关系,最大亏格嵌入数,以及最大亏格与嵌入图等方面.     

列车控制问题的计算分析及自适应算法

在对原有算法分析的基础之上指出其导致计算不能执行下去的原因并给出参数的下界,提出一种自适应的算法,并得到满意的实验结果.     

求解旅行商问题的几种算法的比较研究

旅行商问题具有重要的理论和实际研究价值,在工程实践中应用广泛.采用遗传算法、蚁群算法和模拟退火算法对旅行商问题进行求解,并选取中国旅行商问题进行仿真,比较了3种算法的优劣,得出了它们各自不同的适用范围:蚁群算法适用于缓慢地较精确的求解场合;模拟退火算法适用于快速精确的求解;遗传算法适用于快速求解,但结果准备度要求不高的情况.     

随机车辆路径问题综述

描述了随机车辆路径问题的历史、发展进程和特征,结合该问题的分类,介绍了该问题国内外的研究现状,指出了目前算法的搜索效率低并依赖于初始解的局限性,给出了对求解算法的进一步研究以及把研究成果应用于实际问题中的研究方向和建议。     

随机车辆路径问题综述

描述了随机车辆路径问题的历史、发展进程和特征，结合该问题的分类，介绍了该问题国内外的研究现状，指出了目前算法的搜索效率低并依赖于初始解的局限性，给出了对求解算法的进一步研究以及把研究成果应用于实际问题中的研究方向和建议。