The Cheapest Way to Obtain Solution by Graph-Search Algorithms

Abstract

Graph-search algorithms belong to the set of basic problem-solving algorithms in Artificial Intelligence. There are systematic graphs search algorithms and also heuristic ones. Depending on the aim, e.g., to find any solution, all solutions, the best solution, one can choose an appropriate algorithm. The best-first algorithm is apt to find the best solution if a good heuristic is provided. Even, the obtained solution itself is the cheapest one, the way to obtain it may contain several useless branches. In this paper, a modified approach is shown which finds a solution having the minimal number of useless branches (depending also on the used heuristic). For the new algorithm, called minimum total cost search, the concept of the heuristic function is also changed: instead of predicting the cost of the closest goal state a kind of directed heuristic function is used: providing an estimation to the closest goal state from the given state to the given direction.