The defining feature of a greedy algorithm is that it
Aexplores every possible solution before picking the best
Bpicks the locally best candidate at each step and never revisits it
Cmemoises sub-problem answers in a table
Duses randomness to escape local optima
Answer & Solution
Correct answer: B. picks the locally best candidate at each step and never revisits it
Greedy commits to the locally best choice at each step and never reconsiders. The lack of backtracking is what makes it fast. Exhaustive search is brute force; memoised sub-problems is dynamic programming; randomness is randomised algorithms. Greedy's strength and weakness both come from the no-backtracking commitment.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for