In this dissertation we investigate theoretical aspects of some practical approaches used
in solving and understanding search problems. We concentrate on the Satisfiability
problem, which is a strong representative from search problem domains. The work develops
general theoretical foundations to investigate some practical aspects of satisfiability
search. This results in a better understanding of the fundamental mechanics for search
algorithm construction and behaviour. A theory of choice or branching heuristics is
presented, accompanied by results showing a correspondence of both parameterisations and
performance when the method is compared to previous empirically motivated branching
techniques. The logical foundations of the backtracking mechanism are explored alongside formulations for reasoning in relevant logics which results in the development of a
malleable backtracking mechanism that subsumes other intelligent backtracking proof
construction techniques and allows the incorporation of proof rearrangement strategies.
Moreover, empirical tests show that relevant backtracking outperforms all other forms of
intelligent backtracking search tree construction methods. An investigation into
modelling and generating world problem instances justifies a modularised problem model proposal which is used experimentally to highlight the practicability of search algorithms
for the proposed model and related domains.
| Identifer | oai:union.ndltd.org:ADTP/216750 |
| Date | January 2003 |
| Creators | Slater, Andrew, andrew.slater@csl.anu.edu.au |
| Publisher | The Australian National University. Research School of Information Sciences and Engineering |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | http://www.anu.edu.au/legal/copyrit.html), Copyright Andrew Slater |
Page generated in 0.0021 seconds