貪欲法 Greedy algorithms
2006.06.06 17:17 貪欲法
"Greedy" とは、食べ物や飲み物などに対する強い "欲求" や "欲望" を意味しますが、Greedy algorithms (貪欲アルゴリズム、よくばり法)では、この食べ物や飲み物をアルゴリズムで扱うデータと見なすことができます。
一般的に、最適化問題 (optimazation problems) のためのアルゴリズムの多くは、あるデータの "選択" の繰り返しという構造になっています。Greedy algorithms は、各計算ステップで、局所的に最適(その時点で最も最適と思われるもの)な選択を繰り返し、最終的に大域的な最適解を求める方法です。
すでに紹介したものも含めて、以下のように Greedy algorithms は多くの問題に対して、最適解を求めることができます。このセクションでは、これらの問題と対応するアルゴリズムを紹介します。
- Minimum Spanning Tree Problem (Prim's algorithm)
- Minimum Spanning Tree Problem (Kruskal's algorithm)
- Shingle Source Shortest Path Problem (Dijkstra's algorithm)
- File Compression (Huffman encoding)
- etc.
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |