Problem Solving
In the simplified, propositional case in which a logic program and a top-level atomic goal contain no variables, backward reasoning determines an and-or tree, which constitutes the search space for solving the goal. The top-level goal is the root of the tree. Given any node in the tree and any clause whose head matches the node, there exists a set of child nodes corresponding to the sub-goals in the body of the clause. These child nodes are grouped together by an "and". The alternative sets of children corresponding to alternative ways of solving the node are grouped together by an "or".
Any search strategy can be used to search this space. Prolog uses a sequential, last-in-first-out, backtracking strategy, in which only one alternative and one sub-goal is considered at a time. Other search strategies, such as parallel search, intelligent backtracking, or best-first search to find an optimal solution, are also possible.
In the more general case, where sub-goals share variables, other strategies can be used, such as choosing the subgoal that is most highly instantiated or that is sufficiently instantiated so that only one procedure applies. Such strategies are used, for example, in concurrent logic programming.
The fact that there are alternative ways of executing a logic program has been characterised by the equation:
Algorithm = Logic + Control
where "Logic" represents a logic program and "Control" represents different theorem-proving strategies.
Read more about this topic: Logic Programming
Famous quotes containing the words problem and/or solving:
“From cradle to grave this problem of running order through chaos, direction through space, discipline through freedom, unity through multiplicity, has always been, and must always be, the task of education, as it is the moral of religion, philosophy, science, art, politics and economy; but a boy’s will is his life, and he dies when it is broken, as the colt dies in harness, taking a new nature in becoming tame.”
—Henry Brooks Adams (1838–1918)
“Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
—James Conant (1893–1978)