Developing backtracking algorithm to find the optimal solution path

Abstract EN

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 worstcases).