Dissertation > Excellent graduate degree dissertation topics show

The Research on QBF Solver Based on Backdoor Sets via Local Search

Author: LiShuXia
Tutor: GuWenXiang
School: Northeast Normal University
Course: Computer Software and Theory
Keywords: Intelligent planning QBF problem QBF problem solver Hidden set Local search Rename
CLC: TP18
Type: Master's thesis
Year: 2010
Downloads: 33
Quote: 0
Read: Download Dissertation

Abstract


Intelligent planning is one of the more popular areas of research in artificial intelligence, one of the main methods of Smart Solver is smart planning problems into propositional satisfiability problem (Propositional Satisfiability Problem, SAT), and then using efficient SAT solver solved. Propositional satisfiability problem (SAT) is a core issue for today's artificial intelligence research. SAT problem can be described as a propositional logic formula, given its argument whether there is a true value assignment to the propositional formula established (to meet), if set up, then return to the assignment of the true value of the variable $. SAT problem is difficult to solve the problem, its computational complexity is NP-complete, but instances of hidden structure be able to find effective SAT solving methods, Backdoors is one of the hidden structure. The covert set (backdoor sets) is a hidden structure of the SAT problem, have a great relationship with the problem difficulty. The choice can make the rest of the problem is solved in polynomial time. Hidden set can be described as a small variable subset B truth assignment of the variables in the B, the simplified formula can be solved in polynomial time. Because of its importance in complex problem solving, the hidden set of research in recent years has gradually become a hot research. Hidden set of solving method has been extended to QBF problem. Quantified Boolean formulas (Quantified Boolean Formulae, referred QBF) is a propositional logic formulas with the presence of a quantifier and universal quantifier prefix. Quantifiers in QBF formula containing only existential quantifiers, QBF problem is transformed to the SAT problem. QBF problem can be seen as a generalization of the SAT problem. QBF problem is more puzzling than the SAT problem, its computational complexity is PSPACE complete. Hidden set to improve the QBF problem solving efficiency. Firstly, the existing hidden set of problems solving algorithm for a general overview, followed designed based algorithm rename the hidden set the hidden set for the first time applied to a new QBF solver for QBF problem thus design a a new BDQBF solver. In BDQBF concealed concentrated variable heuristic guide algorithm branch search, thereby reducing the search space of the algorithm and the number of back-off, and improve the the QBF problem solving efficiency. Finally, for this algorithm, the two types of experiments: the first category of experiments with standard C implementation of this algorithm in a Windows environment, and compared with the original to solve QBF problem of hidden set algorithm, the results show that this algorithm The second type of experiment is realized the the QBF problem solver BDQBF system using the standard C language in Linux environment can solve the problems of the smaller hidden set; The results showed that whether it is the QBF problem of random or standard test the problem, BDQBF solver has a good solution performance. These experiments verify the actual value of the hidden set QBF problem solving.

Related Dissertations

  1. Research on UCAV Tactical Operation Sequence Planning Based on Graphplan,E844
  2. Research on the Problem of Course Arrangement Based on Intelligent Plan,TP18
  3. Approximate Knowledge Compilation for Quantified Boolean Formulas,TP182
  4. Opponents plan based on planning graph recognition method,TP391.41
  5. Planning Encodings Based on Quantified Boolean Formulas,TP18
  6. Online Parallelization in Conformant Planning,TP18
  7. A Study of Constructing General Software Platform for Intelligent Payload Planning and Scheduling System,TP311.52
  8. The Research on Extending Trajectory GraphPlan with Probabilistic PDDL Subset,TP18
  9. Research on Technologies of Planning-based Semantic Web Services Composition,TP393.09
  10. The Research and Implementation on Goal-Directed Flexible Graphplan Algorithm,TP18
  11. The Research on Probabilistic Planning Graph Based on Multi-Agent Technology,TP18
  12. Research of Flexible Planning Algorithm Based on Heuristic Searching,TP18
  13. Adversarial Planning via Symbolic Model Checking,TP311.52
  14. The Study and Realization of Plan Recognition Algorithm Based on Flexible Planning,TP301.6
  15. Research on Uncertainty Planning Algorithms,TP301.6
  16. Research and Implementation of probabilistic planning Figure planning under the framework of the decision-making,TP18
  17. Research and Implementation of the possibility of the planning framework planning,TP18
  18. Research on Self-Organizing Metamorphic Planning for Modular Self-Reconfigurable Multi-Fingered Hands,TP242
  19. A Counterplanning Approach Based on Goal Driven Theory,TP11
  20. The Research on Goal-Directed Temporal Graphplan Algorithm,TP18

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