Conditional Preference Networks with User's Genuine Decisions

User's choices involve habitual behavior and genuine decision. Habitual behavior is often expressed using preferences. In a multiattribute case, the Conditional Preference Network (CP-net) is a graphical model to represent user's conditional ceteris paribus (all else being equal) preference statements. Indeed, the CP-net induces a strict partial order over the outcomes. By contrast, we argue that genuine decisions are environmentally influenced and introduce the notion of “comfort” to represent this type of choices. In this article, we propose an extension of the CP-net model that we call the CP-net with Comfort (CPC-net) to represent a user's comfort with preferences. Given that preference and comfort might be two conflicting objectives, we define the Pareto optimality of outcomes when achieving outcome optimization with respect to a given CPC-net. Then, we propose a backtrack search algorithm to find the Pareto optimal outcomes. On the other hand, two outcomes can stand in one of six possible relations with respect to a CPC-net. The exact relation can be obtained by performing dominance testing in the corresponding CP-net and comparing the numeric comforts.     

静态SAT问题并行处理器的设计研究

针对SAT问题的复杂性及求解速度缓慢的问题，采用可重构器件FPGA设计，实现了静态回溯搜索算法SAT问题并行处理器，提出了研制动态SAT并行处理器的设想。     

Backtrack: An O(1) expected time algorithm for the graph coloring problem

Fix a number K, of colors. We consider the usual backtrack algorithm for the decision problem of K-colorability of a graph G. We show that the algorithm operates in average time that is O(1), as the number of vertices of G approaches infinity. For instance, a backtrack search tree for 3-coloring a graph has an average of about 197 nodes, averaged over all graphs of all sizes.     

基于迭代回溯的数据库查询优化算法

查询优化器是数据库系统最重要的组件之一。该文提出了一类新的查询优化算法,并对其性能进行了评估、讨论。它是基于分层回溯的一种查询优化算法,其优点主要在于对于一些复杂的应用环境,它在枚举算法的高复杂性和算法产生方案的质量之间取一个权衡点,以产生“次优”的优化结果来换取算法的执行效率,大大节省了运行环境的资源。该算法可以应用于当今一些新型数据库,如对象数据库和XML数据库等。     

重叠端口通道的四、五层布线算法

本文提出了一个重叠端口通道的四、五层布线算法,算法的目标是占用尽可能少的通道布线行数,为此算法中采用了扩展布线的概念,将部分线网分配到器件区域中进行布线,在通道内部布线时,引入了重叠端口通道的垂直约束矩阵的概念,并用它来避发式算法的线网布线顺序,算法在任何情况下都能保证布线的成功,从运行实例上来看,算法速度很快,而且结果都是近似最优的（或者是最优,或者是比最优解多一个布线行）。     

Reasoning about networks of temporal relations and its applications to problem solving

An interval algebra (IA) has been proposed as a model for representing and reasoning about qualitative temporal relations between time intervals. Unfortunately, reasoning tasks with IA that involve deciding the satisfiability of the temporal constraints, or providing all the satisfying instances of the temporal constraints, areNP-complete. That is, solving these problems are computationally exponential in the worst case. However, several directions in improving their computational performance are still possible. This paper presents a new backtracking algorithm for finding a solution called consistent scenario. This algorithm has anO(n ³) best-case complexity, compared toO(n ⁴) of previous known backtrack algorithms, wheren denotes the number of intervals. By computational experiments, we tested the performance of different backtrack algorithms on a set of randomly generated networks with the results favoring our proposal. In this paper, we also present a new path consistency algorithm, which has been used for finding approximate solutions towards the minimal labeling networks. The worst-case complexity of the proposed algorithm is stillO(n ³); however, we are able to improve its performance by eliminating the unnecessary duplicate computation as presented in Allen's original algorithm, and by employing a most-constrained first principle, which ensures a faster convergence. The performance of the proposed scheme is evaluated through a large set of experimental data.     

ELCIRC源程序代码分析

开放源程序代码ELCIRC是采用基于水平向无结构网格、垂向z坐标体系和半隐格式的欧拉-拉格朗日有限体积/有限差分方法来解浅水方程。研究了ELCIRC中除控制方程组求解以外的部分,分析了源程序在插值计算、拓扑结构、定解条件、分层信息和干湿法等技术上的具体操作,尤其是对欧拉拉格朗日模型特有的逆向追踪算法做了详细阐述。同时讨论了一些细节问题,在不恰当的地方给出一些参考和建议,避免小数做分母、相近数相减引起的较大误差。然而,这些经过实际应用的算法原理,可以为我们开发水动力学模型提供有价值的参考。     

数独游戏的问题生成及求解算法优化

将"数独"问题分解为建立终盘、生成有唯一解初盘和求解初盘等子问题。运用拉斯维加斯随机算法思想结合回溯法建立终盘,采用"挖洞"思想隐去部分数字并结合反序回溯法生成具有唯一解的初盘,依据初盘中空格数的多少对问题的难度进行划分,创建不同等级难度的"数独"游戏,并对求解数独问题的候选数搜索算法进行优化改进。实例分析结果表明,优化后的候选数搜索算法性能提高了50%以上,验证了所提出算法模型的有效性。     

数独问题求解算法的研究与实现

数独是当前流行的一种填字游戏。本文介绍了几种常用的数独求解方法,并通过具体实例,探讨了数独问题 的求解方案,最后使用C#语言编程实现。结果证明,该方案运行效率高,结果易于理解。     

CBack: A simple tool for backtrack programming in C

Backtrack programming is such a powerful technique for problem solving that a number of languages, especially in the area of artificial intelligence, have built-in facilities for backtrack programming. This paper describes CBack, a simple, but general tool for backtrack programming in the programming language C. The use of the tool is illustrated through examples of a tutorial nature. In addition to the usual depth-first search strategy, CBack provides for the more general heuristic best-first search strategy. The implementation of CBack is described in detail. The source code, shown in its full length, is entirely written in ANSI C and highly portable across diverse computer architectures and C compilers.