CrazyEngineers
CrazyEngineers

  • doubt in greedy algorithm?

    Morningdot Hablu

    Member

    Updated: Oct 25, 2024
    Views: 3.7K
    hi friends,
    i read "greedy algorithm always make the choice that look best at the moment it may be the optimal solution or may not be".
    .
    suppose we have to go delhi from bihar and we have two way to go.
    1.bihar___100km___orissa____120km___delhi
    2.bihar___80km___orissa___180km___delhi
    .
    so friends accoding to dynamic programming we chose bihar__80km__orissa__120km__delhi.(because in this way we have to cover the less distance as a whole).
    .
    but according to greedy we look the problem and chose minimum distance from bihar to 1st stopage(80km)and then chose min distance from 1st stopage to delhi(180).
    .
    is that realy means of greedy algorithm or else.
    help me i m in confucian.
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • Manish Goyal

    Member • May 8, 2010

    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
    Are you sure? This action cannot be undone.
    Cancel

  • rushi4444

    Member • May 8, 2010

    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
    Are you sure? This action cannot be undone.
    Cancel

  • durga ch

    Member • May 8, 2010

    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
    Are you sure? This action cannot be undone.
    Cancel

  • Manish Goyal

    Member • May 8, 2010

    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
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register