17-09-2012, 04:48 PM
Investigation of the (Star) Search Algorithms: Characteristics, Methods and Approaches
1Investigation of the (Star).pdf (Size: 49.1 KB / Downloads: 171)
INTRODUCTION
A search algorithm is an algorithm for finding an item with specified properties among a collection of items. There is a
type of search algorithms called * (star) search algorithms. This paper will briefly take a look to them. So, in the
second section, the most popular star algorithms will be talked and their features and details will be investigated
separately. Finally, conclusion is placed in the end of paper.
MOST POPULAR STAR ALGORITHMS
In this section we will cover the most important star algorithms. Due to it, we will study the A*, B*, D* (including
original D*, Focused D* and D* Lite), IDA* and SMA*. The details for them will be talked separately.
A* is a search algorithm that is widely used in path finding and graph traversal, the process of plotting an efficiently
traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. Peter
Hart, Nils Nilsson and Bertram Raphael first described the algorithm in 1968 [1]. It is an extension of Edsger Dijkstra's
1959 algorithm. A* achieves better performance (with respect to time) by using heuristics.
In 1964 Nils Nilsson invented a heuristic based approach to increase the speed of Dijkstra's algorithm. This algorithm
was called A1. In 1967 Bertram Raphael made dramatic improvements upon this algorithm, but failed to show
optimality. He called this algorithm A2. Then in 1968 Peter E. Hart introduced an argument that proved A2 was
optimal when using a consistent heuristic with only minor changes. His proof of the algorithm also included a section
that showed that the new A2 algorithm was the best algorithm possible given the conditions. He thus named the new
algorithm in Kleene star syntax to be the algorithm that starts with A and includes all possible version numbers or A*
[2].
CONCLUSION
In this paper, we had an investigation on the basic concepts of star search algorithms, and the features of them.
Different types of star algorithms were specified and they were talked separately. They were: A*, B*, D* (including
original D*, Focused D* and D* Lite), IDA* and SMA*.