貪欲法 Greedy algorithms

"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.

随時追加予定です。