最坏情况下X2SAT问题的上界

最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的O(1.4511n)提高到O(1.4203n),其中n为X2SAT公式中变量的数目.X2SAT问题实例的大小不仅依赖于变量的数目还依赖于公式的长度,时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算法X2SAT-L,并从公式长度的角度证明了X2SAT问题在O(1.3643l)时间上界内可解.     

最坏情况下X3SAT最大海明距离问题最小上界

X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.7107n)缩小到O(1.6760n),其中n为公式中变量的数目。     

基于分支回溯的NAE-3SAT问题求解算法

NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.     

多文字可满足SAT问题的相变点上界

可满足(SAT)问题是指：是否存在一组布尔变元赋值,使得随机合取范式(CNF)公式中每个子句至少有1个文字为真。多文字可满足SAT问题是指：是否存在一组布尔变元赋值,使得随机CNF公式中每个子句至少有2个文字为真。此问题仍然是一个NP难问题。定义约束密度α为CNF公式子句数与变元数之比,对该问题的相变点上界α^*进行了研究。如果α>α^*,则多文字可满足SAT问题高概率不可满足。通过一阶矩一个简单的推断,可以证明α^*=-ln 2/ln(1-(k+1)/2^k),当k=3时,α^*=1。利用Kirousis等人的局部最大值技术,提升了多文字可满足3-SAT问题的相变点上界α^*=0.7193。最后,选择了大量数据进行实验验证,结果表明,理论结果与实验结果相吻合。     

最坏情况下#3-SAT问题最小上界

最坏情况下#SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.#SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究#SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2\\+m),其中m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam-Logemann-Loveland (DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393\\+m).     

基于寻找可满足2SAT子问题的SAT算法*

可满足问题（SAT）是一个NP-Hard问题。提出了一种求解SAT的新算法（FFSAT）。该算法将SAT问题转换为寻找一个可满足的2-SAT子问题。SAT问题虽然是NP完全问题,但是当所有子句长度不大于2时,SAT问题可以在线性时间求解。使用2-SAT算法-BinSat求解2-SAT子问题,当它不满足时,根据赋值选择新的2-SAT子问题。实验结果表明,采用本算法的结果优于UnitWalk。     

基于子句权重学习的求解SAT问题的遗传算法

该文提出了一种求解SAT问题的改进遗传算法（SAT—WAGA）．SAT-WAGA算法有多个改进性特点：将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散．该文最后描述了实现包括SAT—WAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议．实验结果表明：与一般遗传算法相比,SAT—WAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善．     

基于加强概率控制策略的SAT局部搜索算法

局部搜索算法是目前求解SAT问题比较有效的方法,而Sattime算法是在SAT国际大赛中获得大奖的一种典型局部搜索算法。在Sattime算法的求解过程中,记录变元翻转事件流数据库,通过数据分析与模式挖掘,发现Sattime算法的局部搜索行为中会出现相邻搜索步选择同一个变元的现象,即所谓的回环现象,从而降低了求解效率。为解决此问题,提出两种概率控制策略：加强子句选择策略和加强变元选择策略,并将这两种策略应用到Sattime算法中,形成新的局部搜索算法Sattime-P。实验结果表明,与Sattime算法相比,改进后的Sattime-P算法求解效率有显著的提升。该方法也对其他局部搜索算法的改进具有参考价值。     

基于演化算法的SAT问题求解

SAT问题即布尔可满足性问题是逻辑学的一个基本问题,也是计算机科学和人工智能研究的核心问题。寻找求解SAT问题的快速算法不仅在理论研究上而且在许多应用领域都具有极其重要的意义。本文讨论了基于演化算法的SAT问题求解方法。     

组织进化算法求解SAT问题

基于组织的概念设计了一种新的进化算法——求解SAT问题的组织进化算法(Organizational Evolutionary Algorithm for SAT problem,0EASAT)．OEASAT将SAT问题分解成若干子问题,然后用每个子问题形成一个组织,并根据SAT问题的特点设计了三种组织进化算子——自学习算子、吞并算子和分裂算子以引导组织的进化．根据组织的适应度,将所有组织分成两个种群——最优种群和非最优种群,然后用进化的方式来控制各算子,以协调各组织间的相互作用．OEASAT通过先解决子问题,再协调相冲突变量的方式来求解SAT问题．由于子问题的规模较小,相对于原问题来说较容易解决,这样就达到了降低问题复杂度的目的．实验用标准SATLIB库中变量个数从20-250的3700个不同规模的标准SAT问题对OEASAT的性能作了全面的测试,并与著名的WalkSAT和RFEA2的结果作了比较．结果表明,OEASAT具有更高的成功率和更高的运算效率．对于具有250个变量、1065个子句的SAT问题,OEASAT仅用了1．524s,表现出了优越的性能．     

New Worst-Case Upper Bounds for SAT

In 1980 Monien and Speckenmeyer proved that satisfiability of a propositional formula consisting of K clauses (of arbitrary length) can be checked in time of the order 2 ^{K / 3}. Recently Kullmann and Luckhardt proved the worst-case upper bound 2 ^{L / 9}, where L is the length of the input formula. The algorithms leading to these bounds are based on the splitting method, which goes back to the Davis–Putnam procedure. Transformation rules (pure literal elimination, unit propagation, etc.) constitute a substantial part of this method. In this paper we present a new transformation rule and two algorithms using this rule. We prove that these algorithms have the worst-case upper bounds 2^{0. 30897 K} and 2^{0. 10299 L} , respectively.     

O(m~2)时间求解SAT问题的随机算法

传统的求解 SAT问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 SAT问题的随机算法 Sat Test1和 Sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 SAT问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 Sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 SAT实例有较好的求解能力 .     

应用计算机探索小Sidon数的上界*

应用计算机探索数论和组合数学中著名的难题——Sidon序列问题,给出一种新的计算方法,获得七个Sidon数的新上界：F(15)≤157,F(16)≤189,F(17)≤220,F(18)≤251,F(19)≤294,F(20)≤337,F(21)≤392。     

A priori determination of bounds for the optimal value of variables in integer linear programming problems

The paper outlines a simple technique for determining a narrower interval containing the coordinates of the optimal solution to integer linear programming problems. Computational experiments show that the lengths of the given ranges of variables decreases by 30–90% on average. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 86–93, March–April 2006.     

基于网络演算的簇树WSN性能上界分析

为保证WSN的服务质量(QoS),需精确求解其性能上界。对进入WSN节点的数据流进行漏桶管制,节点为数据流提供基于速率-延迟模型的服务保障,在已有簇状拓扑WSN性能模型研究基础上,利用确定性网络演算理论推导簇树WSN节点的有效带宽、缓冲区队列长度上界和数据流端到端延迟上界。     

LP-oriented upper bounds for the weighted stability number of a graph

Upper bounds for the weighted stability number of a graph are considered that are based on the approximation of its stable set polytope by linear inequalities for odd cycles and p-wheels in the graph. Algorithms are developed for finding upper bounds on the basis of solution of LP problems with a finite number of inequalities produced by the shortest path algorithm for a special graph. The results of test experiments are given for graphs with several hundred or thousand vertices. This work was partially financially supported by the CRDF Cooperative Grants Program under grant UKM2-2812-KV-06. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 157–170, January–February 2009.     

Improving spectral bounds for clustering problems by Lagrangian relaxation

Clustering is one of the most important issues in data mining, image segmentation, VLSI design, parallel computing and many other areas. We consider the general problem of partitioning n points into k clusters by maximizing the affinity measure of the points into the clusters. This objective function, referred to as Ratio Association, generalizes the classical (Minimum) Sum‐of‐Squares clustering problem, where the affinity is measured as closeness in the Euclidean space. This generalized version has emerged in the context of the approximation of chemical conformations for molecules, and in explaining transportation phenomena in dynamical systems, especially in dynamical astronomy. In particular, we refer to the dynamical systems application in the paper. Although successful heuristics have been developed to approximately solve the problem, the conventional spectral bounds proposed in the literature are not tight enough for “large” instances to assert the quality of those heuristics or to allow solving the problem exactly. In this paper, we investigate how to tighten the spectral bounds by using Lagrangian relaxation and Subgradient optimization methods.     

一般克隆选择算法的概率性收敛研究*

为了丰富克隆选择算法的理论研究并将遗传算法与克隆选择算法的收敛属性进行比较,采用与研究遗传算法类似的方法研究一般克隆选择算法概率性收敛属性,得到了克隆选择算法以一个预先定义的概率δ找到全局最优解的进化代数上界,该上界是独立于优化问题的。另外,在概率性收敛的情况下,得出了克隆选择算法与遗传算法的进化代数上界的比较结果以及相关结论。     

New upper bounds for excited vibration systems with applications of the differential calculus of norms

In an earlier paper, the author introduced new upper bounds for free linear and nonlinear vibration systems; to compute the best upper bounds, the differential calculus of norms was applied. In the present paper, this work is continued for the corresponding excited systems. Some new techniques and ideas are involved. The results in the applications cannot be obtained by the methods used so far.