A greedy algorithm forever makes the best available choice. In this case the best available choice is given by the order of the actions: the best selection among the available activities (those compatible with all previous choices) is, by meaning, that of an activity with the latest start. At each choice point, all actions overlap with the already chosen ones are discarded and the latest starting one among those remaining is chosen.
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. On some problems, a greedy strategy need not produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution.
No comments:
Post a Comment