Make delicious recipes!

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.

Color legend




Algorithms
Settings
Num-Rows: Num-Cols:
Impasse blocks' frequency:
Costly blocks' frequency:






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal