doubt in greedy algorithm?

Replies

• 

  Manish Goyal

  According to me In both case the solution will be same
  
  I think this is not the appropriate problem to understand difference of efficiency between both
  
  Take just travelling salesman person problem try to solve it using both approaches you will definitely understand difference in view of all
  
  factors between both
• 

  rushi4444

  i agree to goyal....this is not appropriate example to understand difference between both....
  
  here is an example....hope it can solve ur doubt....
  
  suppose we have coins of value 1,4,6 units.......and we want to make change for 8 units.....with minimum no of coins....
  
  according to greedy it will choose 6,1,1.....
  where as
  according to dynamic programming it will choose 4,4
  so ofcourse greedy doesnot give optimal solution
• 

  durga ch

  Hi Mohit,
  
  I am assuming this post is related to networks.the example what you have provided is apt. Many of the networks still follow greedy algorithm. The fundamental principle of greedy algorithm lies in estimating the nearest immediate neighbor. The source doesn't look beyond this node and sometimes ends up in dead ends or in loops
  You might ask them why do we use greedy at all? Thats because, every time the network layout changes, there wont be a need for the node to store the details of the entire path, the node can infact quickly see whose next to it and send the packet down in other words- it reduces the overhead in routing tables
• 

  Manish Goyal

  I agree to durga for finding the shortest path greedy approach is quite well as compared to dynamic programming as there is no use of storing path details and also complexity wise it is worst because in case of dp complexity increases to exponentially(not sure) which is absolutely not acceptable