We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Probably because if you locate some local minimum distance, that's also the global minimum until you find something better. In other words, if you find a minimum, that's optimal and you take it. In contrast, finding a shortest route in a graph doesn't work if you greedily always take the shortest route at every juncture, since sometimes taking a longer route in the short term offers a better path overall.
Minimum Absolute Difference in an Array
You are viewing a single comment's thread. Return to all comments →
Probably because if you locate some local minimum distance, that's also the global minimum until you find something better. In other words, if you find a minimum, that's optimal and you take it. In contrast, finding a shortest route in a graph doesn't work if you greedily always take the shortest route at every juncture, since sometimes taking a longer route in the short term offers a better path overall.