そのアルゴリズム、貪欲につき――貪欲法のススメ:最強最速アルゴリズマー養成講座(3/3 ページ)
アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。
今回の解法
今回の問題は、「条件を満たす回答が存在するか」をいかに高速に検出するかが鍵となります。そこで発想を転換し、逆にどういったケースで条件を満たす回答がなくなるのかを考えれば、この問題は案外簡単に解くことができます。
まず簡単なのは、「国Aから飛び立つ飛行機の数と、国Uに着陸する飛行機の数が一致しない場合」です。これでは成立するはずがなく、1つずつ経路を絞っていっても差が変わるわけではないので、最初の1回だけ判定を行えば十分です。こちらはあまり問題ではないでしょう。
問題となるのは、「飛行機の数は一致しているが、飛び立った飛行機の受け入れ先が存在しない場合」です。これは少し複雑になるので、図を見ながら考えます。
上の図は、成立しないケースの1つです。これは極端な例ですが、A国の空港0から飛び立つ飛行機の数が、U国の空港の数を上回っています。こうしたケースは極端ですが、このように、受け入れる先が存在しない場合は、合計値が一致していたとしても、成立する組み合わせが存在しません。
もう少し複雑な例を考えます。
こちらの図は、前ページで挙げた例題の番号順を変えて、一部の経路だけを確定させたものです。空港A0からはできるだけ番号の大きい空港とつなぎたいので空港U3とつなぎ、空港A1からは、空港U2と繋いでしまうと、残りの空いている空港が3つ未満となり、空港A3の飛行機が余ってしまうので、空港U1へつなぎました。さて、これでも成立するでしょうか?
当然答えはNoです。空港A2から2つ飛行機を飛ばすと、国Uの空港U1、空港U2のどちらかが受け入れ不可能となり、空港A3から飛行機を3つ飛ばすことができなくなります。このように、少し複雑となってくるケースも存在し、最大数などを確かめるだけでは、受け入れ可能かどうかは判別できません。この場合において、空港A1から飛び立つ飛行機を、空港U1に向かわせてしまうと成立せず、空港0へ向かわせれば成立させることができます。
ここまで考えた上で、あることに気づくことができれば、この問題は解けたも同然です。つまり、「受け入れ可能な空港をできるだけ多く残すことができれば、成立する組み合わせが残りやすい」という点に気付くことができるかどうかです。逆に言えば、成立する組み合わせが存在するかを調べるには、できるだけ受け入れ可能な空港を残す配分の仕方を試し、それが成立するかを調べるだけでよい、ということにもなります。
配分の仕方もさほど難しくありません。受け入れ可能な空港を残すということは、受け入れ数が多い空港から積極的に使っていけばよいので、
- 残りの受け入れ可能数が多い順にソートする
- 多いほうから1個ずつ経路を確定させる
- すべての空港について1、2を繰り返し、すべての配分が成功したら成立する
という手順で判定できることが分かります。この関数は、国Aの空港数をn、国Uの空港数をmとして、O(nm)程度の実行時間しか掛からず、ソートを利用した適当な実装でもO(nmlogn)程度で、これは2500回程度なら十分間に合うでしょう。この関数をC#のソースコードに直すと、以下のようになります。
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
なお、今回は貪欲法を利用する問題であり、貪欲法では厳密性が問題となりやすいので、あえて競技中の思考を追った説明にしました。筆者がこの問題を解いたときは、問題を開いた時点で終了30分前、方針が立ったのが終了15分前でしたので、このような非常にラフな証明で実際のコードを書く形になりました。もう少し余裕があれば、きちんと厳密性を検証してみてもよいかもしれません。
なお、上記の説明では証明が十分ではありませんので、厳密な証明を転載しておきます。
Proof: Take any solution. Repeat the following process until V is connected to the K vertices with largest degrees: Let W be a vertex connected to V, and let X be a vertex that is not connected to V and has a larger degree than W. We will now change the graph to connect V to X instead of W. This is done as follows: There must be a vertex Y that is connected to X but not to W. Take the original graph, delete the edges V-W and Y-X, and instead of these add the edges V-X and Y-W. Obviously, we got a valid bipartite graph with the same degrees, and V is now connected to X.
英語で書かれていますが、内容としては、国Aと国Uの空港をそれぞれ頂点とするグラフを考えた際に、成立する解が存在するのであれば、辺の入れ替えを行うことで、今回の方法で見つけ出せる組み合わせに変換可能である、といったことが書かれています。本連載ではあまり厳密な証明を考えることを重視していませんので、説明はこの程度にとどめます。気になる方は原文を読んでみてください。
ここまでできれば後は簡単ですね。前ページのヒントに記述したとおり、1本1本の経路に対してverifyを行い、答えとなる文字列を1個ずつ作っていけばよいということになります。なお、成功する経路が1つも存在しない場合も、上記の関数で1発で調べられますので、かなり短いコードで表現できます。実際のソースコードに直すと、以下のようになります。
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
なお、今回は取り扱いませんでしたが、「空港を頂点、経路を辺としたグラフを考え、探索によって解を見つける」といった解法を思いついた方もおられるでしょう。この考え方は、まだ本連載では解説していませんが、最大流・最大費用流といったフロー問題に繋がる考え方で、非常に筋のよい考え方です。この考え方でも解くことができますが、回答が辞書順でなくなってしまったり、制限時間を超過してしまったりなど、回答にたどり着くまでに少し苦労するかもしれません。時間がある方は挑戦してみてください。
さて、今回の問題はいかがだったでしょうか? 貪欲法はさまざまな場面で活用できますが、明らかな場合を除いて、使う際に思い切りが必要になってきます。TopCoder上には多くの問題が掲載されていますので、これらに触れることで、直感的に判断が下せるようになるでしょう。
今回紹介したものよりも美しい実装方針を思いついたり、きれいなコードが書けたら、ぜひご意見いただければと思います。ソーシャルブックマークのコメントでも、筆者個人のブログに書き込んでいただいても構いません。可能な限り反応したいと思っていますので、どんどんご意見をお寄せください。
なお、今回もTwitter用のハッシュタグも用意しました。今回の連載に関するTweetは「#SSAlgo09」をつけてツイートしていただければと思います。
それでは、次回もお楽しみに!
*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***
著者プロフィール:高橋直大(たかはし なおひろ)
Microsoftが主催する技術コンテスト「Imagine Cup」の2008年アルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。現在、慶應義塾大学環境情報学部3年。TopCoderでは誰もが恐れるRedcoderとして活躍中。TopCoderの祭典「TopCoder Open 2010」では、Marathon Match部門で決勝に駒を進め、世界の上位12人として、10月にラスベガスで行われる決勝で世界一を目指す。
また、同じくTopCoderで開催されたNASA-Challengeで、惑星外探査などの長期ミッションに必要な医療物資の量と配分を適切に行うアルゴリズムを競い、5位入賞。このアルゴリズムを参考にして作られたアルゴリズムは、来年からロシアで実運用される。
口癖の「みょんみょん」が聞けるTopCoderニコ生オープン実況も視聴者を増やしつつある。
世界でも有数のRedcoder、高橋直大がアルゴリズムの魅力と極意を伝授する「最強最速アルゴリズマー養成講座」はこちらから
関連記事
- 病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 - アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった
動的計画法・メモ化再帰というと難しいアルゴリズムであるかのように聞こえますが、実際には小学生でも分かるほど簡単なアルゴリズムです。使用できるメモリと実行時間を意識しながら、同じ計算をする無駄を省くことができれば、かなりの実力者となれます。 - トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 - 知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 - 細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック
競技プログラミングはレベルの高い人たちの集まり――そんな考えを持っている初心者の方、TopCoderはあなたのコーディングスキルを爆発的に高める魔法のような場です。今回は、初心者にこそお勧めしたいTopCoderの魅力について考えます。 - 「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」
典型的なアルゴリズムをたくさん知っている人間が最強か――? いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。 - オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 - あなたの論理的思考とコーディング力は3倍高められる
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 - 高橋直大、Imagine Cupアルゴリズム部門で世界の三強に
- フランスの地でアルゴリズムの未来を切り開く男 高橋直大
Microsoftが主催する学生向けの技術コンテスト「Imagine Cup」。そのアルゴリズム部門で世界の頂点に挑むのは、プログラミング歴が2年にも満たない一人の数学好きだった。 - アルゴリズムと戯れる元野球少年が手に入れた宝物
Imagine Cup 2008のアルゴリズム部門で世界第3位となった高橋直大氏。彼の軌跡を眺めてみると、わたしたちが忘れてしまったことにすら気づかない何かを思い出させてくれるような気持ちになる。
関連リンク
Copyright © ITmedia, Inc. All Rights Reserved.