東工大スーパーコンピューティング コンテスト (supercon 2008)
東工大が毎年行なっている「電脳甲子園」supercon 2008の結果発表会および表彰式に行ってまいりました．
実を言うと，私は今回の本選問題の提案者であり，かつ，本選問題の作成者でもあったのですが，その割に今週はずっと出張に行っていたので，出張中もいろいろと気になっていました．今日の結果発表会，表彰式はとても楽しかったです．
各チームのいろいろな作戦や「人手」の執念，チューターの活躍など，いろいろと見どころがあったようです．
また東京から大阪への賞状伝達など前衛的な場面もありました．
どんな問題？
さて，私の提案した問題は「最小面積単純多角形構成問題」です．コンテストでは「単純多角形面積最小化問題」と呼んでいました．
これは，平面上に与えられた点集合を頂点とする単純多角形の中で面積が最小のものを求めるという問題です．
この問題はNP困難であることが知られていて (Fekete, 2000)，効率的なアルゴリズム (多項式時間アルゴリズム) がこの問題にはないだろうと思われています．
ということで，どういう感じのアルゴリズムを設計したくなるか，ということになっていくわけですが，以下，私がパッと思いついて，なおかつ実装できそうなものを書いてみます．
どうやって解く？ 基本
単純に思いつくのは局所探索です．1つ単純多角形を求めたら，そこから局所的な変更を加えてより面積の小さな単純多角形を求めていきます．これを繰り返し，局所的な変更で面積を小さくできなくなったらストップします．これを繰り返します．
問題は「(1) はじめに単純多角形を1つ求めるにはどうしたらよいか．どういう単純多角形を求めたらいいのか？」ということと「(2) どういう局所的な変更を考えればよいのか？」というところです．ここが工夫のしどころでしょう．
まず，単純多角形は与えられた点を一度ずつ通過するので，単純多角形とその通過順を同一視 (対応づけ) します．ただし，変な順番を考えてしまうと自己交差を持つ (単純でない) 多角形ができてしまうかもしれないので注意が必要です．
(1)の方ではまずランダムな順番を考えて，それが自己交差を持つならば交差を解消して単純多角形を得ます．
プログラム全体では単純多角形を求める作業を繰り返すので，できるだけ多様性のある単純多角形を(1)の部分で作ればその後の局所的な変更によって得られる多角形の多様性も増えてよりよい多角形が見つかりそうだと思えます．
(2)の方では多角形における点の訪問順を局所的に入れ替えて「単純多角形である」という性質と「面積が小さくなる」という性質を満たすものを見つけられればよいです．
局所的な入れ替え方はいろいろあります．順番における1点だけの場所を変えるとか，ごそっと思いっきり変えるとか，あるいは，幾何情報を利用して，単純多角形にならないような入れ替えは予めやらないようにするとか，おそらくここが一番大きな工夫のしどころに思えます．
ここでよい入れ替え方 (うまく改善ができるという意味と高速であるという意味の両方) を考案できればうまくいきそうです．
どうやって解く？ 言い訳
さて，こんなプログラムで本当にうまくいくのか，と思われそうですが，実際私にはわかりませんでした．
しかし，このアルゴリズムのよいところは，とても柔軟だというところです．
今回のコンテストでは「人手」が許されました．つまり，人間が自ら手を動かして見つけた知見や情報をそのまま答えに組み込んでいってよいのです．(そのため，トライアル時間は各チーム1時間でした．)
何か知見が得られて，ある部分は絶対に使った方が得になりそうだ，と分かったら，その部分を必ず含む単純多角形をはじめの(1)の部分で与えるように変更ができます．(そのようにはじめからプログラムを作っておくわけです．)
もう1つよいところはどんな問題に対しても最小解を求められる確率が0ではない (正である) ことです．
そのため，うまく探索をしていけばかなりよい解が見つけられそうです．
あと，ちゃんと確認していないので間違っているかもしれませんが，この問題には「proximate optimality property」がありそうな気がします．つまり，「よい解のそばにはよい解がある」という性質です．
そのため，ある程度よい解が見つかったら，その周りを徹底的に探索するような「集中化」を行うと効果的かもしれません．
ということで，局所探索の基本的な技法を使えば，かなりよいところまでいけるような気がする問題でした．
並列性をうまく利用するためには，(1)の部分で生成する多角形がノード毎にできるだけ異なるように順番をランダム生成する技法が必要になってきますが，ここも工夫のしどころの1つだと思います．
ここは私自身の研究テーマなので，ちょっと黙っておきます (まだ研究がちゃんとできていないので)．
ちなみに，この問題に対しても分割統治法のようなアルゴリズムが作れますが，かなり難しくなります．幾何的な分割統治ではseparatorが重要な役割を果たしますが，それはかなり高度な内容です．
あと，アルゴリズムを考える前に，自分の手で何問か解いて感覚をつかむことも重要だと思います．特に今回の問題はもしかしたら直観に合わない多角形が最小解であるかもしれません．なので，いろいろな例を自分で作って，実際に手を動かして解いたりすることで問題に対する直感が湧いて，そこからアルゴリズムが思いつくという方向は悪くないでしょう．問題がどういう構造を持っているのか見極めるのは重要なポイントです．
本音の一部
問題作成者としては，「人手」で最小解を求められてしまうことが一番怖かったので，それに注意して問題を作っていたのですが，人手でかなり近いところまで行ったチームもありました．怖いです．
しかし，人手でやったチームではなくて，うまいアルゴリズムを考案し，スパコンをうまく使えたチームが上位に並んだのでその点では安心しました．
上位チームは大体局所探索的なアルゴリズム (＋焼きなまし) を用いていたように記憶しています．
今回は幾何的な問題だったので，最後に全チームの作った多角形が配布されて，それを見てみると多種多様な多角形が作られていることが見て取れて，本当に面白かったです．
やはり「見て分かる」という意味で，こういうコンテストに幾何の問題はよいように思いました．プログラムを書くのは大変ですけどね．
参加した高校生，高専生，大学生の皆様，スタッフの皆様，チューターの皆様，お疲れ様でした．ありがとうございました．
