Greedy algorithm selects the best choice at each step, instead of considering all sequences of steps that may lead to an optimal solution. Sometimes this algorithm fails to find the globally optimal solution because it does not consider all the data.
Therefore, this approach seems to work very well, but it actually does not produce an optimal solution to many problems. For example, the greedy algorithm seeks to find the path with the largest sum. It means that it does this job by selecting the largest number available at each step as below:
To reach the largest sum, at each step, the greedy algorithm will choose what appears to be the optimal immediate choice, so it will choose 12 instead of 3 at the second step, and will not reach the best solution, which contains 99.
# Applications
- Dijkstra
- Huffman Coding
'Algorithms' 카테고리의 다른 글
| Recursive Algorithm 재귀 알고리즘 (0) | 2021.08.25 |
|---|---|
| Halting Problem 정지 문제 (0) | 2021.08.24 |
| [Search] Linear vs. Binary 선형/이진 탐색 (0) | 2021.08.24 |
| [Sorting] Selection Sort 선택정렬 (0) | 2021.08.24 |
| [Sorting] Insertion Sort 삽입정렬 (0) | 2021.08.24 |