期刊文献+
共找到13篇文章
< 1 >
每页显示 20 50 100
DEPICT:A High-level Formal Language for Modeling Constraint Satisfaction Problems
1
作者 Abdulwahed M.Abbas Edward P.K.Tsang Ahmad H.Nasri 《International Journal of Automation and computing》 EI 2008年第2期208-216,共9页
The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently de... The past decade witnessed rapid development of constraint satisfaction technologies, where algorithms are now able to cope with larger and harder problems. However, owing to the fact that constraints are inherently declarative, attention is quickly turning toward developing high-level programming languages within which such problems can be modeled and also solved. Along these lines, this paper presents DEPICT, the language. Its use is illustrated through modeling a number of benchmark examples. The paper continues with a description of a prototype system within which such models may be interpreted. The paper concludes with a description of a sample run of this interpreter showing how a problem modeled as such is typically solved. 展开更多
关键词 constraint satisfaction problems (CSPs) and languages formal specifications typed predicate calculus language interpreter
下载PDF
A residual-based message passing algorithm for constraint satisfaction problems 被引量:1
2
作者 Chun-Yan Zhao Yan-Rong Fu Jin-Hua Zhao 《Communications in Theoretical Physics》 SCIE CAS CSCD 2022年第3期77-86,共10页
Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerf... Message passing algorithms,whose iterative nature captures complicated interactions among interconnected variables in complex systems and extracts information from the fixed point of iterated messages,provide a powerful toolkit in tackling hard computational tasks in optimization,inference,and learning problems.In the context of constraint satisfaction problems(CSPs),when a control parameter(such as constraint density)is tuned,multiple threshold phenomena emerge,signaling fundamental structural transitions in their solution space.Finding solutions around these transition points is exceedingly challenging for algorithm design,where message passing algorithms suffer from a large message fiuctuation far from convergence.Here we introduce a residual-based updating step into message passing algorithms,in which messages with large variation between consecutive steps are given high priority in the updating process.For the specific example of model RB(revised B),a typical prototype of random CSPs with growing domains,we show that our algorithm improves the convergence of message updating and increases the success probability in finding solutions around the satisfiability threshold with a low computational cost.Our approach to message passing algorithms should be of value for exploring their power in developing algorithms to find ground-state solutions and understand the detailed structure of solution space of hard optimization problems. 展开更多
关键词 constraint satisfaction problems model RB message passing algorithms residuals of messages
原文传递
An Optimized Constraint Decomposition Method in Concurrent Engineering
3
作者 常天庆 Xu Wensheng +1 位作者 Xiong Guangleng Xing Siming 《High Technology Letters》 EI CAS 2003年第2期72-77,共6页
In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved... In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved from solutions of sub-problems. Ideally, sub-problems are not only mutually independent but also inherent parameters of original problem. Solution of original problem can be directly derived from the collection of solutions from simplified sub-problems. In practice, the degree of interdependency is indeed reduced, sub-problems are neither totally independent nor all inherent parameters of original problem. This paper discusses team coordination under this condition and design solution from each team, which not only satisfies total requirements but also is an optimal one. The suggested optimized constraint decomposition method will insure workable Pareto solution. 展开更多
关键词 constraint satisfaction problems constraint decomposition Concurrent Engineering constraint management
下载PDF
THE Q-MATRIX LOW-DENSITY PARITY-CHECK CODES
4
作者 Peng Li Zhu Guangxi 《Journal of Electronics(China)》 2006年第1期35-38,共4页
This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that t... This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check (LDPC) code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that the problem of constructing the sparse parity-check matrix requires an algorithm that is efficient in search environments and also is able to work with constraint satisfaction problem. The definition of Q-matrix is given, and it is found that the queen algorithm enables to search the Q-matrix. With properly permuting Q-matrix as sub-matrix, the sparse parity-check matrix which satisfied constraint condition is created, and the good regular-LDPC code that is called the Q-matrix LDPC code is generated. The result of this paper is significant not only for designing low complexity encoder, improving performance and reducing complexity of iterative decoding arithmetic, but also for building practical system of encodable and decodable LDPC code. 展开更多
关键词 Low-density parity-check code ENCODER constraint satisfaction problems n-queens problem
下载PDF
Fuzzy Constraint-Based Agent Negotiation 被引量:1
5
作者 Menq-WenLin K.RobertLai Ting-JungYu 《Journal of Computer Science & Technology》 SCIE EI CSCD 2005年第3期319-330,共12页
Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for... Conflicts between two or more parties arise for various reasons andperspectives. Thus, resolution of con-flicts frequently relies on some form of negotiation. Thispaper presents a general problem-solving framework for modeling multi-issue multilateral negotiationusing fuzzy constraints. Agent negotiation is formulated as a distributed fuzzy constraintsatisfaction problem (DFCSP). Fuzzy constrains are thus used to naturally represent each agent''sdesires involving imprecision and human conceptualization, particularly when lexical imprecision andsubjective matters are concerned. On the other hand, based on fuzzy constraint-basedproblem-solving, our approach enables an agent not only to systematically relax fuzzy constraints togenerate a proposal, but also to employ fuzzy similarity to select the alternative that is subjectto its acceptability by the opponents. This task of problem-solving is to reach an agreement thatbenefits all agents with a high satisfaction degree of fuzzy constraints, and move towards the dealmore quickly since their search focuses only on the feasible solution space. An application tomultilateral negotiation of a travel planning is provided to demonstrate the usefulness andeffectiveness of our framework. 展开更多
关键词 agent negotiation distributed fuzzy constraint satisfaction problem fuzzyconstraints
原文传递
Consistent Algorithm for Multi-value Constraint with Continuous Variables 被引量:1
6
作者 常天庆 李敬逸 +1 位作者 徐文胜 熊光楞 《Tsinghua Science and Technology》 SCIE EI CAS 1999年第2期20-24,共5页
Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous v... Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi value constraint. 展开更多
关键词 artificial intelligence constraint satisfaction problem consistency problem
原文传递
Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems
7
作者 Lamia SADEG-BELKACEM Zineb HABBAS Wassila AGGOUNE-MTALAA 《Frontiers of Computer Science》 SCIE EI CSCD 2016年第6期1012-1025,共14页
This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning... This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly genetic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future. 展开更多
关键词 optimization problems partial constraint satisfaction problems frequency assignment problems graph decomposition adaptive genetic algorithm (AGA) AGA guided by decomposition (AGAGD).
原文传递
On the Arc Consistency Problem
8
作者 陈阳军 《Journal of Computer Science & Technology》 SCIE EI CSCD 1999年第4期298-308,共11页
In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposi... In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some of them are executed before the entire inconsis-tency checking has been finished), each constraint subnetwork will be searched with agradually shrunk domain. In addition, the technique of AC-6 can be integrated intoour algorithm, leading to a further decrease in computational complexity. 展开更多
关键词 constraint satisfaction problem constraint network arc consistency divide-and-conquer strategy probabilistic analysis
原文传递
EMERGENCE FROM LOCAL EVALUATION FUNCTION 被引量:2
9
作者 HANJing CAIQingsheng 《Journal of Systems Science & Complexity》 SCIE EI CSCD 2003年第3期372-390,共19页
This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into ... This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a globalsolution emerges from the system in which every agent uses a local evaluation function to decide itsaction, while comparing to other traditional algorithms, such as Local search and SimulatedAnnealing which use global evaluation functions. We also give some computer experimental results onlarge-scale N-queen problems and κ-Coloring problems, and show that emergence only depends onproblem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize toa global solution, but can not in some other CSPs no matter what settings of agents have. 展开更多
关键词 constraint satisfaction problem evolution function multi-agent system
原文传递
Test-Data Generation Guided by Static Defect Detection 被引量:1
10
作者 郝丹 张路 +2 位作者 刘明浩 李合 孙家骕 《Journal of Computer Science & Technology》 SCIE EI CSCD 2009年第2期284-293,共10页
Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques hav... Software testing is an important technique to assure the quality of software systems, especially high-confidence systems. To automate the process of software testing, many automatic test-data generation techniques have been proposed. To generate effective test data, we propose a test-data generation technique guided by static defect detection in this paper. Using static defect detection analysis, our approach first identifies a set of suspicious statements which are likely to contain faults, then generates test data to cover these suspicious statements by converting the problem of test-data generation to the constraint satisfaction problem. We performed a case study to validate the effectiveness of our approach, and made a simple comparison with another test-data generation on-line tool, JUnit Factory. The results show that, compared with JUnit Factory, our approach generates fewer test data that are competitive on fault detection. 展开更多
关键词 test-data generation suspicious statements software testing constraint satisfaction problem
原文传递
Polynomial algorithm of limited propositional deduction 被引量:1
11
作者 史忠植 廖乐健 《Science China(Technological Sciences)》 SCIE EI CAS 1999年第4期418-424,共7页
For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a ... For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways:One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space. 展开更多
关键词 limited propositional deduction polynomial algorithm problem of propositional satisfiability constraint satisfaction problem
原文传递
Intelligent test case generation based on branch and bound 被引量:1
12
作者 XING Ying GONG Yun-zhan +1 位作者 WANG Ya-wen ZHANG Xu-zhou 《The Journal of China Universities of Posts and Telecommunications》 EI CSCD 2014年第2期91-97,103,共8页
Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm ... Path-oriented test case generation is in essence a constraint satisfaction problem (CSP) solved by search strategies, among which backtracking algorithms are widely used. In this article, the backtracking algorithm branch and bound (BB) is introduced to generate path-oriented test cases automatically. A model based on state space search is proposed to construct the search tree dynamically. The BB is optimized from two perspectives. Variable permutation with a heuristic rule to break ties is adopted for the branching operation, and interval computation with analysis on the monotony of branching conditions is utilized for the bounding operation. Empirical experiments show that the proposed method performs well with linear complexity, and reaches 100% coverage on some benchmark programs with an advantage over some static and dynamic algorithms. 展开更多
关键词 test case generation constraint satisfaction problem branch and bound state space search
原文传递
Integrating Standard Dependency Schemes in QCSP Solvers 被引量:1
13
作者 Ji-Wei Jin Fei-Fei Ma Jian Zhang 《Journal of Computer Science & Technology》 SCIE EI CSCD 2012年第1期37-41,共5页
Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering... Quantified constraint satisfaction problems (QCSPs) are an extension to constraint satisfaction problems (CSPs) with both universal quantifiers and existential quantifiers. In this paper we apply variable ordering heuristics and integrate standard dependency schemes in QCSP solvers. The technique can help to decide the next variable to be assigned in QCSP solving. We also introduce a new factor into the variable ordering heuristics: a variable's dep is the number of variables depending on it. This factor represents the probability of getting more candidates for the next variable to be assigned. Experimental results show that variable ordering heuristics with standard dependency schemes and the new factor dep can improve the performance of QCSP solvers. 展开更多
关键词 quantified constraint satisfaction problem standard dependency scheme variable ordering heuristics
原文传递
上一页 1 下一页 到第
使用帮助 返回顶部