Developing Backtracking Algorithm to Find the Optimal Solution Path | ||
| Engineering and Technology Journal | ||
| Article 1, Volume 28, Issue 24, December 2010, Pages 6995-7003 PDF (176.95 K) | ||
| DOI: 10.30684/etj.28.24.13 | ||
| Authors | ||
| Suhad M. Kadhum; Israa A. Abdul-Jabbar | ||
| Computer Science Department, University of Technology/ Baghdad | ||
| Abstract | ||
| There are numerous search methods in A.I used to find the solution path to a subjected problem, but many of them return one solution path with no consider it is the optimal or not. The aim of this work is to find a direct path from the start state to the goal state such that it is the shortest path with minimum cost (the optimal solution path). We develop the backtracking algorithm in order to find the optimal solution path, such that all possible paths of the problem that expected to contain the optimal solution path can be checked, also we use a heuristic function depends on the actual cost of transition from one state to another. And in order to reduce the search time we discard any path that it is not useful in finding the optimal solution path. The proposed algorithm was implemented using visual prolog 5.1 and tested on tree diagram and the result was good in finding the optimal solution path (with efficient search time equivalent to O(bd/2) and space complexity O(bd) in worst cases). | ||
| Keywords | ||
| artificial intelligence; Search Algorithm; optimal path; Heuristic Search; Backtracking Strategy | ||
|
Statistics Article View: 273 PDF Download: 135 |
||