KATOエンジニヤリング開発日誌

「アウトプット無きエンジニアにインプットもチャンスも無い」の精神で書いています

「なっとくアルゴリズム」を読んだ - 貪欲法 -

前回に続いて「なっとくアルゴリズム」を読んで理解したことのまとめです。

www.kato-eng.info

www.kato-eng.info

www.kato-eng.info

www.kato-eng.info

www.kato-eng.info

貪欲法

貪欲法は単純なアルゴリズムで、各ステップで局所的最適解を選んでいく(各ステップで最適な「手」を選ぶ)。各ステップで局所的最適解を選んでいくと、最終的には大域的最適解が残る。

貪欲法では必ずしも最適解が得られるとは限らないが、完璧な最適解を目指すと「巡回セールスマン問題」のようなO(!n)の計算時間が必要となる場合があり、現実的な時間では問題が解決しないことがありえる。このような場合に貪欲法で問題にあたると計算時間の短縮になるし、アルゴリズムの考え方自体が単純なので、実装に時間がかからないというメリットもある。

以下に貪欲法を用いた問題解決の方法を記載する。

教室の時間割問題

ある教室の時間割で、できるだけ多くの授業を行いたいが、授業の時間が重なっているため全ての授業をこの教室で行うことはできない。

授業 開始時間 終了時間
美術 9:00 10:00
国語 9:30 10:30
算数 10:00 11:00
コンピュータ 10:30 11:30
音楽 11:00 12:00

この問題を解くアルゴリズムは下記の通り。

  1. 最も早く終る授業を選ぶ。
  2. 次に最初の授業の後に始まる授業から、最も早く終る授業を選ぶ。
  3. この作業を繰り返す。

このアルゴリズムを実行すると次のようになる。

  1. 最も早く終る授業である「美術」を選ぶ。
  2. 次に美術が終わる時間の「10:00」以降に始まる授業のうち、最も早く終る「算数」の授業を選ぶ。
    • 国語は美術と授業時間が被るので除外される。
  3. 次に算数が終わる時間の「11:00」以降に始まる授業のうち、最も早く終る「音楽」の授業を選ぶ。
    • コンピュータは算数と授業時間が被るので除外される。

従って、この教室では「美術、算数、音楽」の授業を行うことになる。この答えが厳密的な最適解とは限らないが、局所的には最適解となっている(大域的最適解である)。

ナップザック問題

自分が泥棒だとして、ナップザックを持って店に忍び込み、ナップザックに収まるだけ商品を盗む場合の局所的最適解を求める。ナップザックには35ポンドの重さに耐えることができるとする。

この問題を貪欲法で解くアルゴリズムは下記の通り。

  1. ナップザックに収まる最も高価な商品を選ぶ。
  2. ナップザックに収まる商品のうち、次に高価な商品を選ぶ。
  3. この作業を繰り返す。

盗む商品は下記3つから選ぶ。

商品 価値 重さ
ステレオ 3,000ドル 30ポンド
ラップトップパソコン 2,000ドル 20ポンド
ギター 1,500ドル 15ポンド

貪欲法で解くと次のようになる。

  1. ナップザックの容量(残り35ポンド)に収まる最も高価な商品である「ステレオ」を選ぶ。
  2. 残りの商品から、ナップザックの容量(残り5ポンド)に収まる最も高価な商品を探すも見つからない。

従って最も効率の良い、盗む商品は「ステレオ」ということになる。

だが、この問題は本当は「ラップトップパソコン、ギター」を盗むのが最適解となる。

盗む商品 価値
ステレオ 3,000ドル
ラップトップパソコン、ギター 3,500ドル

ナップザック問題を貪欲法で解くと厳密的最適解は得られなかったが、そこそこ良い結果は得られた。