Search code examples
artificial-intelligence

Greedy search algorithm

Currently, I am a new to the Artificial Intelligence. I have a problem with the greedy search algorithm. I saw one question in a tutorial but can't understand how to answer it. Please help me. Any help much appreciated.

Consider the given figure 1. The values in each node represent the heuristic cost from that node to goal node (G) and the values within the arcs represent the path cost between two nodes.

  1. If B is the starting node and G is the goal node,
  • Find the traversal using Greedy Search Algorithm.
  • Find the traversal using A* Search Algorithm
  1. Using the result of part (1) show that greedy search is not optimal. enter image description here
Solution

  • I assume that the greedy search algorithm that you refer to is having the greedy selection strategy as follows: Select the next node which is adjacent to the current node and has the least cost/distance from the current node. Note that the greedy solution don't use heuristic costs at all.

    Consider the following figure well crafted such that it proves that greedy solution is not optimal. enter image description here

    The path highlighted with red shows the path taken by Greedy Algorithm and the path highlighted with green shows the path taken by Heuristic A* algorithm.

    Explanation:

    Greedy algorithm

    • Starting from Node B, the greedy algorithm sees the path costs (for A it's 6, for C it's 6 and for E it's 5)
    • We greedily move to node E because it is having least path value.
    • From E we have only one option to move to F
    • From F we again have only one option to move to H and from H we move to G (Goal state/node)

    Cost for the path by Greedy Algorithm (highlighted in red): B -> E -> F -> H -> G = 5+6+6+3 = 20

    A* algorithm (before going forward have a look at the wiki page for A* algorithm and understand what g(n) and h(n) are if you haven't already understood this concept):

    • Starting from node B, we have three options A, C and E. For each node we calculate f(n) = g(n) + h(n). Here g(n) is the immediate cost on the arc and h(n) is the heuristic value on the node
      • For node A, f(n) = 6 + 12 = 18
      • For node B, f(n) = 6 + 10 = 16
      • For node C, f(n) = 5 + 14 = 19
    • We choose to proceed with the node that has least f(n). So we move to node B.
    • We proceed in the similar fashion and find the path highlighted in green.
    • The path by A* algorithm is B -> C -> D -> H -> G and it's cost is 6+6+4+3 = 19

    By the above example we can see that the cost of heuristic path is less than greedy algorithm. Hence greedy algorithm is not always optimal.