目の前の さいぜんを えらぶ

いま さいぜんを とる

おつり 870ウォンを わたします。
どう しましょう?
どんよくの ほうほうは かんたんです。
「いま つかえる
いちばん 大きい コインから」とるのです。
500ウォン 一つ、
100ウォン 三つ、
50ウォン 一つ、
10ウォン 二つ。
まいかい 大きいのを とった だけなのに
すぐに おわりました。

大きい コインから おして とります。(870ウォン → 500 · 100 · 100 · 100 · 50 · 10 · 10)

これが どんよく アルゴリズムです。
この さき どう なるか
とおくまで しらべません。
ただ「いま この しゅんかん
いちばん よいもの」を えらぶ だけ。
けいさんが かるいので
けっていが はやいです。

ぜんたいは 見ません

どんよくの ほんとうの とくちょうは これです。
ぜんたいの ちずを ひろげません。
わかれみちごとに
「いま よさそうな ほう」へ
一歩 ふみだす だけです。
さきを とおくまで 見ないので
まよいが すくなく はやいです。
そのかわり、いちど えらんだら
ふりかえりません。

わかれみちごとに 大きい かずを おして 一歩ずつ。ぜんたいの ちずは 見えず、目の前の 二つから だけ えらびます。

ぜんたいを 見ないのは
ちょうしょでも あり よわみでも あります。
はやいのは ちょうしょ。
でも とおくが 見えないので、
いま よさそうな みちが
あとで いきどまりかも しれません。
それでも ある もんだいでは
この はやい ほうほうが
ふしぎと ぴったり あいます。

うまく いくとき

かいぎしつ 一つに
かいぎを できるだけ たくさん 入れたいです。
じかんが かさなっては いけません。
どんよくの ひけつは
「いちばん はやく おわる かいぎから」とる ことです。
はやく あくほど
あとに もっと 入るからです。
この よくは ふしぎと
ほんとうの さいぜんの こたえを くれます。

いちばん はやく おわる かいぎから おして とります。かさなる ものは じどうで ぬけ、どんよくが いちばん 多い 4つを うめます。

なぜ これが せいかいでしょう?
いちばん はやく おわるのを えらぶと
へやが いちばん はやく あきます。
あいた じかんが いちばん 多く のこるので
その中に ほかの かいぎが
いちばん 多く 入れます。
だから 一歩ずつ よくばっても
けっきょく ぜんたいが さいぜんに なります。
こういう もんだいは どんよくが こたえです。

まちがう はんれい

こんどは コインが へんです。
1ウォン、3ウォン、4ウォンしか ありません。
6ウォンを かえします。
どんよくで 大きいものから だと
4ウォン 一つ、つぎに 1ウォン 二つ。
コイン 三まいです。
でも 3ウォン 二つなら?
コイン 二まいで おわります。
目の前の さいぜんが
ぜんたいの さいぜんを のがしました。

二つの ほうほうを おして くらべます。どんよく(4·1·1 = コイン 3まい)と もっと よい みち(3·3 = コイン 2まい)。どんよくが わなに おちました。

どんよくが まちがった わけは
4ウォンを さっと とった しゅんかん
のこりの 2ウォンを 1ウォン 二つでしか
うめられなく なったからです。
いまの 大きな 一歩が
あとを だめにしたのです。
だから ふつうの コインなら あたり、
こういう ずれた コインには はずれます。
どんよくが つうじるかは
もんだいごとに たしかめる ひつようが あります。

まとめ

どんよく アルゴリズムを 一行で 見ると こうです。
まいかい いま いちばん よさそうな ものを えらぶ。
ぜんたいを 見ないので はやくて かんたんです。
おつり、かいぎしつのように
ある もんだいでは これが ぴったりの せいかいです。
でも へんな コイン、
こんがらがった みちでは
目の前の さいぜんが わなに なります。
だから どんよくは はやくて よく あたりますが、
ほんとうに あたるかは もんだいごとに しらべる ひつようが あります。

かなめ 四つを じゅんに おして まとめます。いま さいぜん → ぜんたい 見ない → よく あたる → ときどき はずれる。

どんよくは いちばん たんじゅんな よくです。
いま よいものを えらんで さきへ すすみます。
はやくて かるいので みりょくてきですが、
その たんじゅんさが ときどき わなに おちます。
いつ つうじて いつ つうじないか
その かんを つかんだなら
これで もう 一つ たせます。
全部を しらべる もっと しんちょうな ほうほう、
それは つぎで。