An exact algorithm with learning for the graph coloring problem

Given an undirected graph G=(V,E), the Graph Coloring Problem (GCP) consists in assigning a color to each vertex of the graph G in such a way that any two adjacent vertices are assigned different colors, and the number of different colors used is minimized. State-of-the-art algorithms generally deal with the explicit constraints in GCP: any two adjacent vertices should be assigned different colors, but do not specially deal with the implicit constraints between non-adjacent vertices implied by the explicit constraints. In this paper, we propose an exact algorithm with learning for GCP which exploits the implicit constraints using propositional logic. Our algorithm is compared with several exact algorithms among the best in the literature. The experimental results show that our algorithm outperforms other algorithms on many instances. Specifically, our algorithm allows to close the open DIMACS instance 4-Fullins_5.     

基于遗传算法的自动组卷系统研究与实现

自动组卷系统是在已有的题库基础上,按照考核目的,按一定算法生成一份满足一定要求的试卷管理系统。计算机如何自动选题形成一套科学合理的试卷算法是最关键的问题,本文首先比较了几种常见的自动组卷方法,然后介绍了遗传算法组卷算法,最后给出了实现方法。     

基于算法组合的人员排班方法研究

排班问题是现实生活中的常见问题.从国内某货航实际情况出发,提出了一种初步排班流程.首先采用线性规划建立班制,再依据班制用贪心算法构建班制串矩阵,以回溯方法将具体班填入班制串,进行微调后完成排班.实验表明了排班方法的合理性.     

Fuzzy logic speed controller optimization approach for induction motor drive using backtracking search algorithm

This paper presents an adaptive fuzzy logic controller (FLC) design technique for controlling an induction motor speed drive using backtracking search algorithm (BSA). This technique avoids the exhaustive traditional trial-and-error procedure for obtaining membership functions (MFs). The generated adaptive MFs are implemented in speed controller design for input and output based on the evaluation results of the fitness function formulated by the BSA. In this paper, the mean absolute error (MAE) of the rotor speed response for three phase induction motor (TIM) is used as a fitness function. An optimal BSA-based FLC (BSAF) fitness function is also employed to tune and minimize the MAE to improve the performance of the TIM in terms of changes in speed and torque. Moreover, the measurement of the real TIM parameters via three practical tests is used for simulation the TIM. Results obtained from the BSAF are compared with those obtained through gravitational search algorithm (GSA) and particle swarm optimization (PSO) to validate the developed controller. Design procedure and accuracy of the develop FLC are illustrated and investigated via simulation tests for TIM in a MATLAB/Simulink environment. Results show that the BSAF controller is better than the GSA and PSO controllers in all tested cases in terms of damping capability, and transient response under different mechanical loads and speeds.     

运动员最佳配对问题的回溯解法

回溯法是解决许多实际问题的重要而有效的方法。文章首先对一类运动员最佳配对问题进行了分析，然后提出一种基于回溯法的解决方案，并给出了算法的具体实现过程和复杂度分析，在此基础上提出一种基于多种因素的运动员配对问题的一般模型，并给出了其回溯解法。     

0/1背包问题

本文对“0／1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析．并通过各种算法的实现．研究了0／1背包问题的实质。     

模糊回溯法实现高校多级多校区分布式网络排课

高校扩招，人数增加，异地校区增多，排课复杂度增加。本文以茂名学院的排课管理的实际情况为背景，先分析了排课的约束条件和要达到的排课效果，把众多约束条件整合到由时间和空间组成的二维空间中，采用模糊回溯法实现了高校多级多校区网络系统环境下分布式排课。该排课算法具有较强的普遍适应性和适用性。     

Value ordering for quantified CSPs

We investigate the use of value ordering in backtracking search for Quantified Constraint Satisfaction problems (QCSPs). We consider two approaches for ordering heuristics. The first approach is solution-focused and is inspired by adversarial search: on existential variables we prefer values that maximise the chances of leading to a solution, while on universal variables we prefer values that minimise those chances. The second approach is verification-focused, where we prefer values that are easier to verify whether or not they lead to a solution. In particular, we give instantiations of this approach using QCSP-Solve’s pure-value rule Gent et al. (QCSP-solve: A solver for quantified constraint satisfaction problems. In Proceedings of IJCAI, pp. 138–143, 2005). We show that on dense 3-block problems, using QCSP-Solve, the solution-focused adversarial heuristics are up to 50% faster than lexicographic ordering, while on sparse loose interleaved problems, the verification-focused pure-value heuristics are up to 50% faster. Both types are up to 50% faster on dense interleaved problems, with one pure-value heuristic approaching an order of magnitude improvement. This work was supported in part by Microsoft Research through the European PhD Scholarship Programme, and by the Embark Initiative of the Irish Research Council for Science, Engineering and Technology (IRCSET).     

Eliminating recursion from combinatoric procedures

The problem of eliminating linear and binary recursion has received quite a deal of attention. Less has been given to the elimination of the more general form of recursion that arises in combinatorics. In this paper we extend earlier work and produce two pairs of equivalent schemata. The correspondences between these schemata and the classical combinatoral problems are given and two applied examples: topological sorting and the set covering problem, are discussed in detail.     

Backtracking search optimization heuristics for nonlinear Hammerstein controlled auto regressive auto regressive systems

In this work, novel application of evolutionary computational heuristics is presented for parameter identification problem of nonlinear Hammerstein controlled auto regressive auto regressive (NHCARAR) systems through global search competency of backtracking search algorithm (BSA), differential evolution (DE) and genetic algorithms (GAs). The mean squared error metric is used for the fitness function of NHCARAR system based on difference between actual and approximated design variables. Optimization of the cost function is conducted with BSA for NHCARAR model by varying degrees of freedom and noise variances. To verify and validate the worth of the presented scheme, comparative studies are carried out with its counterparts DE and GAs through statistical observations by means of weight deviation factor, root of mean squared error, and Thiel’s inequality coefficient as well as complexity measures.