排序方式: 共有15条查询结果,搜索用时 859 毫秒
1.
Value ordering for quantified CSPs 总被引:1,自引:0,他引:1
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). 相似文献
2.
3.
非二元约束满足问题求解 总被引:12,自引:1,他引:12
在约束满足问题(CSP)的研究中,大部分工作集中在二元约束,但处理实际问题时,常常会遇到非二元约束的情况.该文在概要地讨论了两类求解非二元约束问题方法的基础上,研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法,并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法,以典型例子给出了实现系统的运行结果. 相似文献
4.
5.
《国际计算机数学杂志》2012,89(12):1465-1476
A finite binary Constraint Satisfaction Problem (CSPs) is defined as consisting of a set of n problem variables, a domain of d potential values for each variable and a set of m binary constraints involving only two variables at a time. A solution to such a CSP is specified by assignment of a value to each variable that does not violate any of the constraints. The CSPs belong to the class of NP-Complete Problems. Backtracking and its variants have been generally used for solving CSPs. The class of Partial Constraint Satisfaction Problems (PCSPs) is a subclass of CSPs that are either too difficult to solve or are unsolvable. Near optimal solutions are always desired to these problems. In this article, we have considered only finite binary CSPs or PCSPs and developed a method of time complexity O(n 2 d 2) to obtain a near optimal solution for them. The performance of the method in terms of the average number of consistency checks and the average number of constraint violations is measured on various randomly generated binary CSPs and compared with the Branch and Bound (BB) method used to obtain the same solution. The BB method is a widely used optimization technique that may be viewed as a variation of backtracking. Thus, it was a natural choice in seeking an analog of backtracking to find optimal partial solutions for PCSPs. The proposed method moves much faster to the solution. The performance results indicate that in terms of the number of consistency checks, the proposed method has much less consistency checks than BB whereas in terms of average number of constraint violations both methods are same. An upper bound on the distance of the solution from the optimal solution is obtained analytically as ?n(n???2)(d???2)/(d???1)?. 相似文献
6.
Production management as a constraint satisfaction problem 总被引:2,自引:0,他引:2
MARKKU SYRJÄNEN 《Journal of Intelligent Manufacturing》1998,9(6):515-522
Production management problems can be quite straightforwardly presented as constraint satisfaction problems, where values for some variables are searched for under a set of constraints. A combination of an operation and a resource is usually interpreted as the variable, and a time window is usually interpreted as the value to be searched for. This convention is challenged. A case is considered where the most appropriate interpretation treats the combination of a resource and a time window as the variable, and an operation as the value. A third possible interpretation is also briefly covered, where the combination of an operation and a time window is the variable, and the resource is the value. 相似文献
7.
约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法. 相似文献
8.
基于结合空间拓扑和方向关系信息的空间推理 总被引:3,自引:1,他引:3
结合了定性空间推理中著名的区域连接演算(region connection calculus,RCC)和基于区域的方向关系演算(cardinal direction calculus,CDC),并且给出两个演算在两个方向上的交互表,即RCC8-To-CDC和CDC-To-RCC8.给出了结合RCC8和CDC知识的约束满足问题的路径一致算法(path consistency algorithm)(该算法是对Allen著名的路径一致算法的修改),并且采用两个队列实现了该算法,采用这种结构可以实现并行计算.在该算法中,基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性.算法的计算复杂性证明是多项式的, 相似文献
9.
In this paper, we present a constraint-based model of cooperative agents for information systems dialogues, with an emphasis on how the agents detect and resolve situations in which the user's information needs have been over-constrained. The constraint-based model of the information agents integrates and extends the AI techniques of constraint satisfaction, solution synthesis and constraint hierarchy, providing an incremental computational mechanism for constructing and maintaining partial parallel solutions. Such a mechanism supports immediate detection of over-constrained situations. In addition, we explore using the knowledge in the solution synthesis network to support different relaxation strategies to support cooperative dialogue behaviors. 相似文献
10.
Hongjie Fu Dantong Ouyang Jiaming Xu 《Computers & Mathematics with Applications》2011,62(7):2712-2718
A novel self-adaptive differential evolution (SADE) algorithm is proposed in this paper. SADE adjusts the mutation rate F and the crossover rate CR adaptively, taking account of the different distribution of population. In order to balance an individual’s exploration and exploitation capability for different evolving phases, F and CR are equal to two different self-adjusted nonlinear functions. Attention is concentrated on varying F and CR dynamically with each generation evolution. SADE maintains the diversity of population and improves the global convergence ability. It also improves the efficiency and success rate and avoids the premature convergence. Simulation and comparisons based on test-sets of CSPs demonstrate the effectiveness, efficiency and robustness of the proposed algorithm. 相似文献