Spelling suggestions: "subject:"backtracking algorithms"" "subject:"backtracking flgorithms""
1 |
Exploiting Structure in Backtracking Algorithms for Propositional and Probabilistic ReasoningLi, Wei January 2010 (has links)
Boolean propositional satisfiability (SAT) and probabilistic reasoning represent
two core problems in AI. Backtracking based algorithms have been applied in both
problems. In this thesis, I investigate structure-based techniques for solving real world
SAT and Bayesian networks, such as software testing and medical diagnosis instances.
When solving a SAT instance using backtracking search, a sequence of decisions
must be made as to which variable to branch on or instantiate next. Real world problems
are often amenable to a divide-and-conquer strategy where the original instance
is decomposed into independent sub-problems. Existing decomposition techniques
are based on pre-processing the static structure of the original problem. I propose
a dynamic decomposition method based on hypergraph separators. Integrating this
dynamic separator decomposition into the variable ordering of a modern SAT solver
leads to speedups on large real world SAT problems.
Encoding a Bayesian network into a CNF formula and then performing weighted
model counting is an effective method for exact probabilistic inference. I present two
encodings for improving this approach with noisy-OR and noisy-MAX relations. In
our experiments, our new encodings are more space efficient and can speed up the
previous best approaches over two orders of magnitude.
The ability to solve similar problems incrementally is critical for many probabilistic
reasoning problems. My aim is to exploit the similarity of these instances by
forwarding structural knowledge learned during the analysis of one instance to the
next instance in the sequence. I propose dynamic model counting and extend the dynamic
decomposition and caching technique to multiple runs on a series of problems
with similar structure. This allows us to perform Bayesian inference incrementally as
the evidence, parameter, and structure of the network change. Experimental results
show that my approach yields significant improvements over previous model counting
approaches on multiple challenging Bayesian network instances.
|
2 |
Exploiting Structure in Backtracking Algorithms for Propositional and Probabilistic ReasoningLi, Wei January 2010 (has links)
Boolean propositional satisfiability (SAT) and probabilistic reasoning represent
two core problems in AI. Backtracking based algorithms have been applied in both
problems. In this thesis, I investigate structure-based techniques for solving real world
SAT and Bayesian networks, such as software testing and medical diagnosis instances.
When solving a SAT instance using backtracking search, a sequence of decisions
must be made as to which variable to branch on or instantiate next. Real world problems
are often amenable to a divide-and-conquer strategy where the original instance
is decomposed into independent sub-problems. Existing decomposition techniques
are based on pre-processing the static structure of the original problem. I propose
a dynamic decomposition method based on hypergraph separators. Integrating this
dynamic separator decomposition into the variable ordering of a modern SAT solver
leads to speedups on large real world SAT problems.
Encoding a Bayesian network into a CNF formula and then performing weighted
model counting is an effective method for exact probabilistic inference. I present two
encodings for improving this approach with noisy-OR and noisy-MAX relations. In
our experiments, our new encodings are more space efficient and can speed up the
previous best approaches over two orders of magnitude.
The ability to solve similar problems incrementally is critical for many probabilistic
reasoning problems. My aim is to exploit the similarity of these instances by
forwarding structural knowledge learned during the analysis of one instance to the
next instance in the sequence. I propose dynamic model counting and extend the dynamic
decomposition and caching technique to multiple runs on a series of problems
with similar structure. This allows us to perform Bayesian inference incrementally as
the evidence, parameter, and structure of the network change. Experimental results
show that my approach yields significant improvements over previous model counting
approaches on multiple challenging Bayesian network instances.
|
3 |
Computational methods for domination problemsBird, William Herbert 04 October 2017 (has links)
For a graph G, the minimum dominating set problem is to find a minimum size set S of vertices of G such that every vertex is either in S or adjacent to a vertex in the set. The decision version of this problem, which asks whether G has a dominating set of a particular size k, is known to be NP-complete, and no polynomial time algorithm to solve the problem is currently known to exist. The queen domination problem is to find the minimum number of queens which, collectively, can attack every square on an n by n chess board. The related border queen problem is to find such a collection of queens with the added restriction that all queens lie on the outer border of the board. This thesis studies practical exponential time algorithms for solving domination problems, and presents an experimental comparison of several different algorithms, with the goal of producing a broadly effective general domination solver for use by future researchers.
The developed algorithms are then used to solve several open problems, including cases of the queen domination problem and the border queen problem. In addition, new theoretical upper bounds are presented for the border queen problem for some families of queen graphs. / Graduate
|
Page generated in 0.0794 seconds