Dissertation > Excellent graduate degree dissertation topics show

Research on Consistency Techniques in Constraint Satisfaction Problems

Author: XingShiMei
Tutor: YangFengJie
School: Jilin University
Course: Computer Software and Theory
Keywords: Artificial Intelligence Constraint satisfaction problems Compatibility technology Constraint solving
CLC: TP181
Type: Master's thesis
Year: 2011
Downloads: 44
Quote: 2
Read: Download Dissertation

Abstract


Constraints is a ubiquitous concept, it is dependent on people's daily life experience: they represent the conditions to restrict people's freedom in decision-making. Daily life in a variety of combinatorial optimization problems with it have a very close relationship, especially in some of the academic value and commercial value, such as graph coloring problem, product configuration problems, scheduling problems, and so on. The past, mainly using traditional algorithms in operations research to solve the solution but sometimes generate unreasonable or not in line with the actual situation, and take a long solution time. Space for this kind of problem solving are generally exponentially, in order to improve efficiency, usually the practical problems in the conditions into constraints, the whole problem into constraint satisfaction problems (Constraint Satisfaction Problem-CSP), and then take for The related art for solving problems studied CSP. A constraint satisfaction problem (CSP) consists of three parts: a limited set of variables, there is a limited range of each variable domain, a limited set of constraints (constraint restrictions relationship between the variables and the variables). Each constraint will restrict the values ??of the variables of the constraints associated collection, if the value of the variable in the current collection does not violate the constraint, the constraint is said to be currently assigned collection meet. CSP a solution for each of the variables in the problem to assign a value of theory domain, so that all of the constraints are satisfied at the same time. In order to improve the efficiency of solving CSP problems, researchers will be the problem of the treatment process is divided into two processes: offline pre-processing (filtering), and online solution. The two processes can be applied to the current and effective technology for compatibility technology. Researchers at home and abroad in recent years, a series of algorithms, such as AC, PC, SAC, etc. This article is mainly listed some of the more popular compatible technology and solution techniques, and on this basis for the filtering process to remove redundant values the ability of the SAC series algorithm research, as follows: (1) This paper mainly studies in the pretreatment process the compatibility algorithm SAC3 algorithm, which is mainly based on depth first thought, greedy search strategy, with a low The amount of space complexity and time complexity of the relatively better. Based the the static heuristic strategy FFP principles SAC3-FFP algorithms, the algorithm in the constraint propagation process can advance found a variable universe is empty and backtracking to improve the efficiency of the algorithm to the SAC3 algorithm framework based on the complexity of the algorithm and the correctness of the analysis, the experiments prove the efficiency of the new propagation algorithm improved. (2) The combination of the above work, is given based on dynamic the heuristic strategy SAC3-MINIsup algorithm, constraint propagation process variable values ??of the constraint propagation queue dynamically sort the data recorded in accordance with the algorithm implementation process support information , and correctness of the new algorithm for complex analysis, and gives the experimental data show that efficiency is improved. (3) SAC3 algorithm in the constraint propagation process treat to deal with the variable value to the lack of validity of the judgment, and constraint propagation process must check variable values ??lack of specificity, the appropriate strategy to get the added to the SAC3 algorithm SAC3-Revised algorithm, the algorithm only perform constraint checking again, rather than the values ??of all variables constraint checking suspected variable values, reduce the number of transmission, improve the efficiency of the algorithm is given the complexity and The correctness of the analysis, and the experimental results.

Related Dissertations

  1. Research on Queue QoS Algorithms Based on Diffserv,TP393.02
  2. DCSP coal mine emergency rescue based resource allocation study,TP18
  3. Programme of the basic problems of artificial intelligence research and development trends,TP18
  4. English -based expert system assisted teaching system design and implementation,TP311.52
  5. Evolutionary Logic Research in Artificial Intelligence,B812.3
  6. Research of Generating Interactive Explanation Algorithms Based on Constraint Programming,TP181
  7. Parametric design effective range to determine the parameters of the DM decomposition algorithm,TP391.72
  8. Solution to the Problems: The Teaching Practical Research into "Artificial Intelligent in High School",G633.67
  9. Development of Wireless Data Service and Artificial Intelligence Designment Based on Brew,TN919.72
  10. Research on Geometric Constraint Modeling and Solving Technology,TP391.72
  11. Constraint Solving Reasoning Technology,TP181
  12. Anti sensor network environment monitoring algorithm,TP212.9
  13. Research of Routing in the Game Map Based on Improved A* Algorithm,TP18
  14. Research on Artificial Endocrine Emotion Models,R318.0
  15. Research and Implementation on Diagnosis of Power Network Expert System Based on Fuzzy Identification,TP182
  16. Game engine Al System Design and Implementation,TP311.52
  17. Research on Algorithm Recognition Based on Autonomous Mental Development,TP311.1
  18. Research on Constraint Solution Based on Interactive Feature Modeling System,TP391.72
  19. Research on Constraint Solving and Validity Maintenance of Freeform Surface Feature,TP391.72
  20. Research on Semantic Feature Modeling and Constraint Solving,TP391.72

CLC: > Industrial Technology > Automation technology,computer technology > Automated basic theory > Artificial intelligence theory > Automated reasoning,machine learning
© 2012 www.DissertationTopic.Net  Mobile