Greedy Algorithm
摘要
When we play chess, we calculate extensively to find the “strongest” move on each of our turns. We hope that by spotting these most accurate moves step-by-step, we will beat our opponent eventually. This shares the similarity with the Greedy Algorithm in computer science in that both try to find the local best solution at each intermediate step, and a combination of these local best solutions may lead to a global optimum solution. In chess, if we are bothered by the local best move too much, we could overlook the brilliant tactics of a sequence of forcing moves (such as a queen sacrifice) that win us the game. Same for the Greedy Algorithm, a succession of local best solutions does not guarantee a global optimum solution. However, the Greedy Algorithm is still an important algorithm that excels at finding quick, approximate solutions to complex problems that would otherwise require an exponential time algorithm. In this chapter, we will dive deep into the Greedy Algorithm with a selection of examples.