そのアルゴリズム、貪欲につき――貪欲法のススメ：最強最速アルゴリズマー養成講座（3/3 ページ）

[高橋直大，ITmedia]

今回の解法

　今回の問題は、「条件を満たす回答が存在するか」をいかに高速に検出するかが鍵となります。そこで発想を転換し、逆にどういったケースで条件を満たす回答がなくなるのかを考えれば、この問題は案外簡単に解くことができます。

　まず簡単なのは、「国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. 残りの受け入れ可能数が多い順にソートする
2. 多いほうから1個ずつ経路を確定させる
3. すべての空港について1、2を繰り返し、すべての配分が成功したら成立する

という手順で判定できることが分かります。この関数は、国Aの空港数をn、国Uの空港数をmとして、O(nm)程度の実行時間しか掛からず、ソートを利用した適当な実装でもO(nmlogn)程度で、これは2500回程度なら十分間に合うでしょう。この関数をC#のソースコードに直すと、以下のようになります。

using System;
using System.Collections.Generic;
public partial class ConnectingAirports
{
    public string[] getSchedule(int[] capacityA, int[] capacityU)
    {
        int i, j;
        int lenA = capacityA.Length;
        int lenB = capacityU.Length;
        string[] res = new string[lenA];
        for (i = 0; i < lenA; i++) if (capacityA[i] > capacityU.Length) return new string[0];
        for (i = 0; i < lenA; i++)
        {
            res[i] = "";
            for (j = lenB - 1; j >= 0; j--)
            {
                if (capacityA[i] == 0 || capacityU[j] == 0) { res[i] = "0" + res[i]; continue; }
                capacityU[j]--; capacityA[i]--;
                if (check(capacityA, capacityU)) { res[i] = "1" + res[i]; }
                else { capacityU[j]++; capacityA[i]++; res[i] = "0" + res[i]; continue; }
            }
            if (capacityA[i] != 0) return new string[0];
        }
        for (j = 0; j < lenB; j++) if (capacityU[j] != 0) return new string[0];
        return res;
    }
}

　なお、今回は貪欲法を利用する問題であり、貪欲法では厳密性が問題となりやすいので、あえて競技中の思考を追った説明にしました。筆者がこの問題を解いたときは、問題を開いた時点で終了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発で調べられますので、かなり短いコードで表現できます。実際のソースコードに直すと、以下のようになります。

using System;
using System.Collections.Generic;
public partial class ConnectingAirports
{
    bool check(int[] _capA, int[] _capU)
    {
        int i, j;
        int[] capA = (int[])_capA.Clone();
        int[] capU = (int[])_capU.Clone();
        Array.Sort(capA);
        for (i = 0; i < capA.Length; i++)
        {
            Array.Sort(capU);
            Array.Reverse(capU);
            for (j = 0; j < capA[i]; j++) capU[j]--;
        }
        for (i = 0; i < capU.Length; i++) if (capU[i] != 0) return false;
        return true;
    }
}

　なお、今回は取り扱いませんでしたが、「空港を頂点、経路を辺としたグラフを考え、探索によって解を見つける」といった解法を思いついた方もおられるでしょう。この考え方は、まだ本連載では解説していませんが、最大流・最大費用流といったフロー問題に繋がる考え方で、非常に筋のよい考え方です。この考え方でも解くことができますが、回答が辞書順でなくなってしまったり、制限時間を超過してしまったりなど、回答にたどり着くまでに少し苦労するかもしれません。時間がある方は挑戦してみてください。

　さて、今回の問題はいかがだったでしょうか？　貪欲法はさまざまな場面で活用できますが、明らかな場合を除いて、使う際に思い切りが必要になってきます。TopCoder上には多くの問題が掲載されていますので、これらに触れることで、直感的に判断が下せるようになるでしょう。

　今回紹介したものよりも美しい実装方針を思いついたり、きれいなコードが書けたら、ぜひご意見いただければと思います。ソーシャルブックマークのコメントでも、筆者個人のブログに書き込んでいただいても構いません。可能な限り反応したいと思っていますので、どんどんご意見をお寄せください。

　なお、今回もTwitter用のハッシュタグも用意しました。今回の連載に関するTweetは「#SSAlgo09」をつけてツイートしていただければと思います。

　それでは、次回もお楽しみに！

著者プロフィール：高橋直大（たかはし　なおひろ）

Microsoftが主催する技術コンテスト「Imagine Cup」の2008年アルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。現在、慶應義塾大学環境情報学部3年。TopCoderでは誰もが恐れるRedcoderとして活躍中。TopCoderの祭典「TopCoder Open 2010」では、Marathon Match部門で決勝に駒を進め、世界の上位12人として、10月にラスベガスで行われる決勝で世界一を目指す。

また、同じくTopCoderで開催されたNASA-Challengeで、惑星外探査などの長期ミッションに必要な医療物資の量と配分を適切に行うアルゴリズムを競い、5位入賞。このアルゴリズムを参考にして作られたアルゴリズムは、来年からロシアで実運用される。

口癖の「みょんみょん」が聞けるTopCoderニコ生オープン実況も視聴者を増やしつつある。

世界でも有数のRedcoder、高橋直大がアルゴリズムの魅力と極意を伝授する「最強最速アルゴリズマー養成講座」はこちらから

変更履歴：文中のソースコードを修正しました。［2010/09/11 2:30］