プログラミング!?で遊ぶ

TopCorder SRM460 に参加しました。　Divison2でございます

Level 1
Div2のLevel 1はいつものように簡単です。サクッと実装してSubmit。
Point 241.84→システムテスト通過。

Level 2
確率は苦手にしております。とまいどいまながらもアルゴリズムを決定して実装。しかし、問題にあるテストケースが通りません。アルゴリズムに間違いがあるのかと思いましたが、何度考えても正しいように思います。コードをステップ実行してデバッグ。intをdoubleにキャストしていなかったのが原因でした。
デバッグに少し時間がかかってしまったように思います。
Point 368.08→システムテスト通過。

Level 3
グラフの問題は嫌いではありません。しばらく考えて方針を思いつき、実装していたのですが、最終的には時間切れになりました。(方針自体が誤りだったかもしれません)
Point 0.0

結果
いつものようにLevel 1 と Level 2は解けて、Level 3 が解けず。
とはいえ、Rateは少しあがって1200を超えました。次回はDiv1に挑戦することになります。

感想
キャスト忘れが気になります。実は練習でSRM459 Level 1 を解いたときにもキャスト忘れをしていました。本日の教訓は「キャストを忘れるな！」でしょうか。
さて、次回はいよいよDiv1です。残留できれば良いのですが・・・。

今度は巡回セールスマン問題で遊びます。
とりあえず2-opt近傍を使った局所探索を実装して試してみました。

問題例はTSPLIBから、アメリカ本土48州の州都の問題をいただいてきました。

得られた局所最適解は

で、巡回路の長さは11095。

ちなみにこの問題例の最適解は

で、巡回路の長さは10628。

まあ、2-opt近傍だけだとこんなものでしょうか。
本日はここまで。

粘菌が東京近郊の鉄道網そっくりのネットワークを構成したそうですね。
イグノーベル賞受賞のときにも感じたことですが、なんとなくアリさんと同様のことをしているような気がします。もしかしたら、全く別の方法かもしれませんけど・・・。
最適化の世界には「焼きなまし法」とか「遺伝的アルゴリズム」とか自然界からヒントを得たアルゴリズムがたくさんあります。粘菌からも新たなアルゴリズムが開発されれば面白いですね。

以上、ニュースを見ての感想でした。

焼きなまし法が失敗するような評価関数を作ってみました。

この関数はx=0のとき最小値0をとります。

この関数を焼きなまし法で探索してみました。
失敗してほしかったのですが、見事に最小値を発見しました。（x=0を一度は評価しているということ）

詳しく見ると、温度が高いランダムウォーク状態のときにx=0を通っているようです。
使った探索プログラムが解の評価をする回数は、探索空間の大きさをはるかに超えているので、考えてみれば当然です。(そもそも解空間全てを評価する時間があるのなら、焼きなまし方などを行う必要はありません)

これまで小さな例で遊んでましたが、もっと大きな例で遊ばないと面白くないですね。
NP困難な問題に手を出そうかしら・・・。

以上、失敗談でした。では、今日はここまで。

あけましておめでとうございます。
新年ということで2010年の目標を考えました。

目標
1.機械学習、メタヒューリスティクスの記事を充実させる
　もう少し更新頻度をあげたいです。
2.TopCoderでDiv1に昇格、かつ残留する
　今の調子なら昇格はできそうな気がしています。
3.Haskellの勉強をする
　関数型の言語に興味がわいてきました。

でも、第一の目標が「頑張らない」なのは変わりません。
というわけで、あまり期待しないでください。