Introduction:
In this report I will describe searching algorithms that I analysed during development process of our program. First of them, sequential search, was covered within our course material. The other two are focused on path finding as this function was our purpose of implementing them in our project.
Sequential:
Also known as linear, sequential search is considered to be the simplest search algorithm. It basically goes sequentially through every element in given data structure, comparing each of them with the searched value. It ends once the matching value has been found or all the elements were checked. In worst case scenario the algorithm will have as many iterations as there are items in data structure, since no matching value was found. For a programmer, linear search is usually less efficient than the other ones, but it is very easy to implement, as it typically requires only one loop with most of the programming languages. (openmymind.net 2011)
A* (A star):
Vastly more advanced than sequential, A* search algorithm is widely used in pathfinding and graph traversal. The reason for this is because it plots efficiently traversable way between multiple nodes. In other words, it finds shortest path from the first, initial node to last one. The way it works is that it follows path expected to be the quickest, whilst maintaining sorted list of alternate paths along the way. There are 3 values used to determine which node offers quickest way to end node. First one, known as heuristic is denoted as h. It is calculated as sum of the distance between 2 nodes of x and y values. It can also be represented in other various ways, however, the most popular is by measuring distance between 2 consecutive nodes. Second value needed for A* is something called „movement cost”, denoted as g. This value is calculated by measuring position of other node compared to the current one. When the second node is positioned vertically or horizontally relative to current node, the movement cost equals 10. If second node is placed diagonally relative to current node this variable equals 14 instead. These two numbers can vary, but 14 and 10 are commonly considered as „standard” ones. Difference between these two values seems reasonable, as diagonal movement costs more than horizontal/vertical one. The last value needed to calculate minimum distance is the sum of node heuristic and movement cost, denoted as f. (Wikipedia 2016)
Breadth-First:
Similar to A*, breadth-first search algorithm can also be used in pathfinding and graph traversal. When given a tree of nodes, the algorithm starts at the first level of the tree. Then it proceeds to next one, starting from the leftmost one to rightmost one. After that, it iterates to next level of the tree, repeating all instructions until it finds the desired value or until all nodes were scanned. (khanacademy.org 2015)
List of references
Khanacademy.org (2015) Breadth-first search algorithm [online] available from
<https://www.khanacademy.org/computing/computer-science/algorithms/breadth-first-search>
[1 March 2016]
Wikipedia [2016] A* search algorithm [online] available from
<https://en.wikipedia.org/wiki/A*_search_algorithm>
[1 March 2016]
Openmymind.net (2011) Linear search [online] available from
<http://algorithms.openmymind.net/search/linear.html>
[1 March 2016]
