3行でまとめると
- (問題を誤読していることに気づかず)とりあえず巡回セールスマン問題で知ってる解法を試してみた
- (問題を誤読したことに気づかないまま)占いを少しだけ使ったら少しだけスコアが改善された
- AIに泣きついてみたが技術力の差にコミュニケーションが成立せずに時間ぎれ
問題の要約
- 座標平面上に都市が800個あります
- 各都市は 0 以上、10000 以下の整数で表せる座標のどこかにあります
- 各都市の正確な座標は誰にもわかりません
- ただし、都市はだいたいこの辺りにある、という長方形の範囲の座標はわかります
- 高橋くんが適当に決めた都市グループに従って、決められた数の都市を道路でつなぎます
- 建設する道路の総長がなるべく短くなるようにしてください
- また占い師は何故か、指定した複数の都市を最短でつなぐ経路(最小全域木)だけ正確に当てることができます
- 占える回数は400回、同時に占える都市は平均10個程度です
誤読してたポイント
結論からいうと、最終的に求める都市グループごとの連結を、 「最小全域木」ではなく、「パス」(分岐がない一直線の木)だと思い込んでいた、という話です。何故そう思い込んだのかは正直なところ原因不明ですが、なんとなく、サンプルプログラムの出力をビジュアライザに突っ込んでみた結果↓がそれっぽく見えたから‥‥なんじゃないかなぁという気がします。
現代美術かよっていう線の荒ぶり具合。
というわけで、いつも以上に全体的にボヤっとした参戦記になっておりますので、この先にはおおらかな気持ちでお進みください。
序盤：ほぼ巡回セールスマン問題とみなして解いてみる
さて、AHC開始ということで問題を読み、前述のような誤解をした結果、「都市をグループに分けて、一本につなげればいいんだな？」と思い込んだ私は、とりあえずこの問題を巡回セールスマン問題(TSP)の亜種として解いてみることにしました。
- 占いは使わない
- 各都市の座標は範囲の中心だと仮定
- すべての都市を巡回するルートを出してみる
- 導いた解を指定された都市グループの数に従って切り離して出力
仮に、全都市をつなげた最短経路が極まった解なら、そのどこを適当に切って都市グループを作っても、最適解とさほど大差ない解になるはずだし、いったんそれでどの程度のスコアになるか見てみようってことです。ついでに、シンプルな実装で、ジャッジサーバ上での試行のループ回数がどれぐらい稼げるか計測してみます。
初期解を都市[0]から[799]を順につないだ場合
巡回セールスマン問題は、過去にヒューリスティックな解法の勉強のために書いたことがあったので、それをベースにコードを作り始めます。ざっくり、以下のようなコードですね。(ちなみに、何故巡回セールスマン問題がこれで最適化されていく（いきやすい）のかは、まるで理解していません)
- 初期解を決める(0から799までの都市番号を順に格納した配列)
- 初期解のスコアを求めて保存
- ランダムで配列の一部をひっくり返す
- 新しい解のスコアが改善されたら暫定解として保持する
- スコアが改善されていなければ戻す
- 制限時間いっぱい、このトライアル＆エラーを繰り返す
どうやら一応合法解はできたみたいなので、いったん提出してみました。
スコア：36482800。数字を見ても全然ピンとこないですが、試しにビジュアライザにかけてみたところ、なかなかにひどい結果でした。
コードテストで実行してみたところ、ループ回数はだいたい100万回前後。思ったより回数回ってますが、頂点が800個もあると、偶然で改善するだけでは難しいみたいですね。
初期解を都市[0]からの貪欲法にしてみる
次はとりあえず、この方針で知ってることを全部やってみます。
- 初期解を貪欲法に変える
- 山登り法を焼きなまし法に変える
スコア： 36482800 → 17945561。意外とそれっぽくなりましたね。スコアも結構上がりました。(前述のように問題を誤読しているわりには)この時点では青perfをとれていたので、自分なりには良い結果でした。
気をよくして、もうちょい改善できないかと、初期解の開始位置をランダムにしてみたり、マップ全体の端から初めてみたりしてみたんですが、特に目立った差はありませんでした。いったんソースをいじるのはやめて、ここからは「占い」について考えてみることにします。
中盤：占いの使い方を模索する
で、次は占いの使い方ですね。占いで得られるのは最小全域木(MST)の連結の仕方だけで、具体的な辺の重みはわからない、と。
そうなるとやることは、都市間の距離(重み)の関係性を利用して、各都市の座標の精度を上げていくってことなんでしょう、多分。
例えば、一番わかりやすい例として、占いに座標の範囲が狭い都市A,C と座標の範囲が広い都市Bを渡して、最小全域木(MST)を取得します。3点でMSTを作るということは、三角形ABCのうち一番長い辺を除いた2辺を選択する、ということなので、MSTの配置によって、どうしても結果が矛盾して都市Bを置くことのできない座標が発生し、ありえる座標の範囲を狭めることができるってことになります、と。
理屈でいえば情報は多ければ多いほどいいので、400回、最大15都市を対象に占った結果と初期条件をずらっと並べて、すべての条件に矛盾しない結果を導くことができれば、後半の都市の連結を決めるときにより正確な値を使用することができます、となりますね。まぁ、とはいえ、これ自体もとても厳密解を求められるような計算量ではないので、これ自体もヒューリスティックな求め方をしないと仕方ない。
つまりこの問題は、 前半にヒューリスティックな解法で都市の位置の精度を上げて、後半にヒューリスティックな解法で都市の連結法を探す っていう、二段構えの問題だってことなんでしょうね、多分。
難しいんですけど。
占いの対象を3都市に絞ってテストしてみる
グラフのことはよくわからないし、幾何的な感覚も脳から抜け落ちているオッサンには、大量の占いを処理する方法などまったくピンときません。
なので、とりあえず先ほど例に挙げた、一番シンプルな例を実装してみることにしました。
- 座標の範囲が広い都市を1個ランダムで選ぶ(B)
- 座標の範囲が狭い都市を2個ランダムで選ぶ(AとC)
- A-C 間でありえる最大距離を求めておく
- 都市Bの範囲、4辺の座標を総当たりして、x座標とy座標を、占いの結果と矛盾しない最大値・最小値に更新する
これを占い400回分繰り返した結果をもって、残りの時間を都市の連結探しに当てます。
スコア： 17945561 → 17520790。ちょっとだけ改善しました。なんとなくですが、方針としては間違ってないらしい、と思いました。(問題は読み間違えてるけど)
終盤：AIに振り回されて何も改善できなかったのち、問題の読み間違いに気づく
ただまぁ、残念なことに、自分でできそうなことはこれで打ち止めです。最大15都市を占った結果の最小全域木をどうやって利用していいやらさっぱりわかりません。
試しに、ランダムに占った結果の最小全域木から、3点の組み合わせを抽出する関数を作成して、自作の3点をなんとかする関数に通してみましたが、座標があいまいな都市同士の組み合わせでは精度を上げることはほとんどできずに単なる計算量の無駄遣いになって、結果的にスコアは落ちました。うーん、手詰まり。
敗因→AIが何を言ってるのかわからない
あとの経緯は端折りますが、ざっくり言うと、AIに丸投げして生成されたコードがよく理解できずに動かしてみて、スコアが悪化した原因を探して、AIに「わたしの聞き方が悪かった」と条件足して、生成されたコードがよく理解できずに動かしてみて、スコアが悪化して、を繰り返しているだけで時間を浪費しました。
いやー、個人的に今回から AHC で AI を解禁したんですけど、人間側のスキルが足りないとコミュニケーションロスがひどくて全然使いこなせませんね。AI向けに正しい厳密なインプットが作れて、アウトプットの正しさを検証するのは、時間さえかければ自分でも作れるっていう人にしか無理だ、という気がします。
結局時間の余裕もなくなり、諦めて、結果的にスコアが一番よかった自作の3都市テスト版を提出しなおすことにしました。
暫定順位
暫定652位。合法回答者数が 1147。予想 perf が 1181、緑なのでシステムテストの結果、運がよければ少し上振れしてギリ水色perfになるかも？というところです。自分のやってたことを鑑みると、全然的外れでもないけど、競技に参加できてるとは言いづらいグレーゾーンぎりぎり、という感覚なので、妥当な評価ではないかと思います。
なお、自分の問題の読み間違いに気づいたのは、最終日4/7(月)の午後3時ぐらい、仕事中にボサッと「AHC上位の人たちは何を理解していて、どんな解法でやってんのかなぁ」とか考えていたら、急に「あれ？ よく考えたら、都市の連結が単純なパスになっていること、なんていう条件は問題に無くない？」と気づいて問題を再読して半確信。締め切り後に上位の方々のポストでビジュアライザを拝見して全確信、でした。
木を勝手にパスだと思い込む勘違いは AHC041 でもやらかしているので泣きそうです。反省。
感想
感想書き忘れた。今回の問題も面白くて楽しかったです。
いろいろ失敗した部分もありましたが、個人的な今回の目標は「山登り法などのヒューリスティックな解法を使用してみる」だったので、一応達成しました。まぁ、知ってた巡回セールスマン問題の解法を適用しただけだし、それは問題の解法としてあんまり適切ではないってのはありますが、まぁ、できたことはできたので。
あと、丸投げできる問題でない場合は、AI の使い方も考えないとだなぁ、という課題もできました。普段AIに対してする質問は、かなり小さな質問ばかりなのでほとんど正解が返ってくるんですけど、質問が大きくなると回答のピントがずれがちで、こっちもそのズレに気づけないとさっぱり話が進まない、ということを学びました。簡単じゃないですね。次回は頑張ります。
（追記）最終結果
システムテストの結果がでました！
理由はわかりませんが順位がやや上がって637位、 1198 perf(緑) でした。惜しい、あと2で水色。参加6回目で、大ポカすると冷えるレーティングに追いついてしまったので、次回から気を引き締めていきたいと思います