UFO(UFOの飛行場) - joi2011-day3 解説

筆者: qnighy

着陸可能なマスを示した地図と、UFOの形状が与えられたとき、UFOを辺隣接させないようにしながらUFOを可能な限り多く配置する問題である。

解析

この問題では、UFOの着陸可能な座標はおよそWH個に限られる。そこで、「その位置にUFOが置けるか」「その位置にUFOが着陸したら他のどの位置には着陸できないか」を考える。するとこれはグラフの安定集合問題(最大独立集合問題)に帰着される。

1番および2番の厳密解法

1番と2番の第一の特徴は、UFOが1x1の最も単純な形状であることである。

1番も2番も横幅が小さいので、bitDPが適用できる。この方法でも厳密解が求まる。

また、前記の解析のように、安定集合問題であるうえに、UFOの形状から対象となるグラフが二部グラフになる。安定集合問題は|V|-最小頂点被覆で求まることが知られていて、最小頂点被覆は二部グラフにおいては最大マッチングに等しいため、最大マッチングを用いれば多項式時間で解ける。

3番以降の戦略

この手の問題のごくごく基本的な戦略は、貪欲法である。すなわち置けるだけ置いてみるということである。

貪欲法(山登り法)に乱数を導入し、それを繰り返すことで良い解を得る方法が最も単純で期待できる解法だろう。これは多スタート局所探索と呼ばれる。

また、この問題では局所改善を導入する手もある。すなわち、UFOを何個か取り除いてまた新たにUFOを配置しなおすという戦略である。

もう少し手の込んだことをするならば、焼きなまし法が使えるだろう。

焼きなまし法を使うときに欠かせないのが、以下の検討である。

例えば、焼きなまし法を用いて巡回セールスマン問題を解く場合などは評価関数は目的関数そのままで良いだろう。しかしこの問題ではこれらの定義があまりよい焼きなましを与えないと考えられる。UFOの個数を評価関数にしても、あまりに離散的であり場面判断の根拠として薄いと思われる。

焼きなまし法のメインルーチンは、温度変数の値を下げながら、乱数で近傍遷移を繰り返すことである。温度が高いうちは、場面が悪化する場合でも高確率で遷移する。

この方法の特長は、それなりに長い実行時間を想定しているということと、パラメーターが多いということである。これは情報オリンピックにおいては相性がいいと言えるだろう。なぜなら、情報オリンピックは手元での実行であり長い実行時間が得られるからである。

また、ぜひともGA(遺伝的アルゴリズム)も試してみる価値はあると思う。なぜなら、この問題では、局所局所に独立な改善がみられる可能性があるからである。

また、同一解の反復を避けるために、適切なタブーサーチを行うのもよいだろう。時間のある限りにおいてさまざまな実装やパラメーター調整を試してもらいたい。

それから、このような難しい問題での厳密最適解は男の浪漫である。(これはqnighyの考えであるが、多くの人に共感してもらえることと思う。)ぜひとも厳密解を求める方法も探ってもらいたい。(しかし普通に考えると絶望的な気がする。)

分枝限定法などの実行不可能な解から探索するような類の最適化は、UFOのような離散性の強い問題でもしっくりくると思われる。(未検証)なので、ぜひとも試していただきたい。