Adaptive Backtracking Search Strategy to Find Optimal Path for Artificial Intelligence Purposes

Abstract

There are numerous of Artificial Intelligence (AI) search strategies that used for finding the solution path to a specific problem, but many of them produce one solution path with no attention if it is the optimal path or not. The aim of our work is to achieve the optimality by finding direct path from the start node to the goal node such that it is the shortest path with minimum cost .In this paper adaptive backtracking algorithm is produced to find the optimal solution path, such that all possible paths in the tree graph of the search problem that have an expected optimal solution is tested, also a heuristic function related to the actual cost of the moving from one node to another is used in order to reduce the search computation time. The adaptive algorithm ignored any path that it is not useful in finding the optimal solution path, our adaptive algorithm implemented using visual prolog 5.1, evaluated on tree diagram and produced good result in finding the optimal solution path with efficient search time equivalent to O(b^d/2) and space complexity O(b^d).

Keywords: Backtracking Algorithm, Optimal solution Path, Heuristic function, Dead end, shortest path, Minimum cost.