貪欲なアルゴリズム

多くの実用的なアルゴリズムは、「解の一部を選択する計算ステップの繰り返し」という構成になっています。Greedy Algorithm （貪欲アルゴリズム、よくばり法）は、各計算ステップで、局所的に最適（その時点で最も最適と思われるもの）な選択を繰り返し、最終的に大域的な最適解を求める方法です。

さらに一般化すると、Greedy Algorithm では、候補の集合 C、すでに選択された要素の集合 S、各ステップで、まだ選ばれていない候補の中から最適とされる要素を決定する選択関数 F、から成ります。最初は、選択された要素の集合 S は空で、その後１ステップごとに、候補の集合 C から選択関数 F によって決定された最適な要素を S に追加します。選択された要素は候補 C から取り除かれます。

例えば、これから紹介するグラフの最小全域木を求めるための Prim's Algorithm や Kruskal's Algorithm、グラフの単一始点最短経路を求めるための Dijkstra's Algorithm はGreedy Algorithm に分類されます。

この中でも、Prim's Algorithm と Dijkstra's Algorithm は同様の計算スキームをもち、以下のように動作します。

	グラフ G(V, E) のノード全体の集合を V、 問題の最適解を構成するノードの集合を T、 各ノード u に割り当てられる値を cost[u]、 とします。
1.	初期状態で、T は空であり、 T に追加するためのノードの候補の集合は V となります。
	任意の(または指定した)ノード s に対応する cost[s] の値を初期化します。
2.	各計算ステップで、cost の値を基に、 ノードの集合 V - T の中から最も良いとされるノード u を選択します。
	u を T に追加すると同時に、u に隣接しかつ T に含まれない全てのノード v に対する cost[v] を更新します。
	この処理を T = V となるまで繰り返します。