Search Algorithms - PrismoSkills

Search Algorithms - PrismoSkills

DFS, BFS, Greedy and A-star Search Algorithms

When searching for a value, following factors affect the quality of search:

1. Estimate of remaining distance: Also called as Heuristic function h.
2. 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:

1. Depth-first Search: Goes into full depth of one side, then other side, then other and so on.
2. Breadth-first Search: Search as near to current node as possible.
3. Greedy Search: Follows the least value of the heuristic function h.
4. Uniform Cost Search: Follows the least value of cost-from-start-to-node g. Thus it behaves very similar to BFS.
5. 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.

Read full article from Search Algorithms - PrismoSkills