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:
“What had really caused the women’s movement was the additional years of human life. At the turn of the century women’s life expectancy was forty-six; now it was nearly eighty. Our groping sense that we couldn’t live all those years in terms of motherhood alone was “the problem that had no name.” Realizing that it was not some freakish personal fault but our common problem as women had enabled us to take the first steps to change our lives.”
—Betty Friedan (20th century)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)