グリーディアルゴリズム(greedy algorithm)、直訳して貪欲算法と呼ばれるアルゴリズムのグループがあります。ネットワークアルゴリズムでは最小スパニング木を求めるアルゴリズムが貪欲算法の代表として有名です*1。今回はこれをアニメーションで紹介しましょう。
最小スパニング木問題はネットワークのすべての頂点を結ぶ重みの和最小の辺の集合を求める問題です。次のネットワークでは
の最小スパニング木は
こうなります。「重みの和最小」の条件から、ループ(閉路)ができることはないので*2、必然的に「木*3」になります。ネットワークの辺が通信路とか水道管で重みが設置費用とすれば、すべてのユーザをつなぐ建設費用最小の方法を求めたことになります。実用上大切ですね。
さて、これを解く貪欲アルゴリズムは、重みの小さい辺からスパニング木に取り入れていきます。ループができるとダメなのでその時はスパニング木に入れません。アニメーションを次に示します。
いかにも貪欲そうな実行風景でした。このやり方で正しく最小スパニング木ができることは証明されています。興味のある方は教科書などを参照して下さい。
こういう小さい例を見ているとループができるかどうかなど人間にはひと目でわかりますが、大きな例ではそうはいきません。また、アルゴリズム(コンピュータ)的には「ひと目でわかる」という手続きはありません。ですが、ループができるかどうかの判断は効率よくできます。前にも書きましたが、最小スパニング木問題は貪欲算法がハマる代表例です。
しかし、貪欲算法では正しい解が得られない、最小なんとか、最大なんとか問題が多数あります。貪欲算法が常に正解をもたらす問題の方が例外と言って良い。あまり欲張ると思わぬところで足をすくわれる、次回はそんな問題を取り上げます。
