A methodology for solving problems: problem modeling and heuristic generation
- 1 September 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 10 (5) , 676-686
- https://doi.org/10.1109/34.6776
Abstract
A methodology is given for modeling a problem and solving it using the A* algorithm. The heuristic used for A* is mechanically generated from the simplified problem, which is derived by relaxing each of the predicate formulas describing the rules and the goal state of the problem. The generated heuristic satisfies the conditions of admissibility and monotonicity. The methodology is applicable for solving general problems. The overall procedure for this methodology is illustrated by four well-known problems, namely, the eight-puzzle problem, the traveling salesman problem, the robot planning problem, and the consistent labeling problem. The values of the heuristics generated by this procedure are compared to the corresponding values of problem-oriented heuristics reported in the literature.Keywords
This publication has 8 references indexed in Scilit:
- A new basis for state-space learning systems and a successful implementationArtificial Intelligence, 1983
- A method for computing heuristics in problem solvingInformation Sciences, 1979
- The Consistent Labeling Problem: Part IIEEE Transactions on Pattern Analysis and Machine Intelligence, 1979
- Reduction operations for constraint satisfactionInformation Sciences, 1978
- Consistency in networks of relationsArtificial Intelligence, 1977
- The heuristic search under conditions of errorArtificial Intelligence, 1974
- The Traveling-Salesman Problem and Minimum Spanning TreesOperations Research, 1970
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968