일반적 문제 해결법을 위한 A* 알고리즘의 적용 = A Generalized Problem Solving Approach Using A* Algorithm

국문 초록 (Abstract)

이 논문은 A* 알고리즘을 이용하여 일반적인 문제를 해결할 수 있는 방법론을 제시한다. A*이용에 핵심이 되는 휴우리스틱 (heuristics)은 주어진 문제의 제약조건들을 완화시켜 유도되는 단순화된 문제로부터 생성되어진다. 이 논문에서 제시되어지는 일반적인 방법론은 5개의 널리 알려진 문제들을 통해 예증되어지고 그 효율성이 이 5개의 각각에 대해 개발된 특정한 문제풀이 방법과 비교되어진다.

다국어 초록 (Multilingual Abstract)

This paper provides a methodology for modelling a problem for its solution using the A*algorithm. The heuristic used for A*is computed 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 is claimed to satisfy the conditions of admissibility and monotonicity. The overall procedure for deriving the heuristic is illustrated by five well known problems, namely, the 8-puzzle problem, the travel ing salesman problem, the robot planning problem, the theorem proving problem, and the consistent labeling problem. The values of the heuristic generated by our procedure are compared against those for the problem-oriented heuristics for some of these problems.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. Introduction
• 2. A Problem Model
• 3. Heuristic h(ex)
• 4. Examples
• 5. Comparison With Other Results
• 6. Discussion
• 7. Conclusion
• References
• 저자소개