When searching for a value, following factors affect the quality of search:
Estimate of remaining distance: Also called as Heuristic function h.
Cost of moving: Denoted by g. This is applicable if all nodes do not have uniform cost for passing through them.
With the above definitions, search algorithms can be classified as:
Depth-first Search: Goes into full depth of one side, then other side, then other and so on.
Breadth-first Search: Search as near to current node as possible.
Greedy Search: Follows the least value of the heuristic function h.
Uniform Cost Search: Follows the least value of
cost-from-start-to-node g. Thus it behaves very similar to BFS.
A-star Search: Follows the least value of the
expression: cost-from-start-to-node + heuristic-cost-from-node-to-end (g+h).
Search Algorithms Playground:
For the below algorithms, passing a blue grid-box is 4 times costlier than a yellow one.
Heuristic value for any node is the
Manhattan Distance between that node and the end-point.
Got a thought to share or found a bug in the code? We'd love to hear from you: