http://riverocean.blog85.fc2.com/ 機械学習、組合せ最適化などのプログラミングをして遊ぶブログです。 ja http://riverocean.blog85.fc2.com/blog-entry-35.html TopCorder SRM460 に参加しました。　Divison2でございますLevel 1Div2のLevel 1はいつものように簡単です。サクッと実装してSubmit。Point 241.84→システムテスト通過。Level 2確率は苦手にしております。とまいどいまながらもアルゴリズムを決定して実装。しかし、問題にあるテストケースが通りません。アルゴリズムに間違いがあるのかと思いましたが、何度考えても正しいように思います。コードをステップ実行してデバッグ。int
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です。残留できれば良いのですが・・・。
]]> 未分類 2010-02-07T11:29:43+09:00 riverocean FC2-BLOG http://riverocean.blog85.fc2.com/blog-entry-34.html 今度は巡回セールスマン問題で遊びます。とりあえず2-opt近傍を使った局所探索を実装して試してみました。問題例はTSPLIBから、アメリカ本土48州の州都の問題をいただいてきました。得られた局所最適解はで、巡回路の長さは11095。ちなみにこの問題例の最適解はで、巡回路の長さは10628。まあ、2-opt近傍だけだとこんなものでしょうか。本日はここまで。 とりあえず2-opt近傍を使った局所探索を実装して試してみました。

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

得られた局所最適解は

で、巡回路の長さは11095。

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

で、巡回路の長さは10628。

まあ、2-opt近傍だけだとこんなものでしょうか。
本日はここまで。 ]]> 組合せ最適化 2010-01-29T00:30:09+09:00 riverocean FC2-BLOG http://riverocean.blog85.fc2.com/blog-entry-32.html 粘菌が東京近郊の鉄道網そっくりのネットワークを構成したそうですね。イグノーベル賞受賞のときにも感じたことですが、なんとなくアリさんと同様のことをしているような気がします。もしかしたら、全く別の方法かもしれませんけど・・・。最適化の世界には「焼きなまし法」とか「遺伝的アルゴリズム」とか自然界からヒントを得たアルゴリズムがたくさんあります。粘菌からも新たなアルゴリズムが開発されれば面白いですね。以上、 イグノーベル賞受賞のときにも感じたことですが、なんとなくアリさんと同様のことをしているような気がします。もしかしたら、全く別の方法かもしれませんけど・・・。
最適化の世界には「焼きなまし法」とか「遺伝的アルゴリズム」とか自然界からヒントを得たアルゴリズムがたくさんあります。粘菌からも新たなアルゴリズムが開発されれば面白いですね。

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


]]> 組合せ最適化 2010-01-23T21:37:21+09:00 riverocean FC2-BLOG http://riverocean.blog85.fc2.com/blog-entry-31.html 焼きなまし法が失敗するような評価関数を作ってみました。この関数はx=0のとき最小値0をとります。この関数を焼きなまし法で探索してみました。失敗してほしかったのですが、見事に最小値を発見しました。（x=0を一度は評価しているということ）詳しく見ると、温度が高いランダムウォーク状態のときにx=0を通っているようです。使った探索プログラムが解の評価をする回数は、探索空間の大きさをはるかに超えているので、考えてみれ
この関数はx=0のとき最小値0をとります。

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

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

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

以上、失敗談でした。では、今日はここまで。
]]> 焼きなまし法 2010-01-11T17:10:05+09:00 riverocean FC2-BLOG http://riverocean.blog85.fc2.com/blog-entry-30.html あけましておめでとうございます。新年ということで2010年の目標を考えました。目標1.機械学習、メタヒューリスティクスの記事を充実させる　もう少し更新頻度をあげたいです。2.TopCoderでDiv1に昇格、かつ残留する　今の調子なら昇格はできそうな気がしています。3.Haskellの勉強をする　関数型の言語に興味がわいてきました。でも、第一の目標が「頑張らない」なのは変わりません。というわけで、あまり期待しないでください。 新年ということで2010年の目標を考えました。

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

でも、第一の目標が「頑張らない」なのは変わりません。
というわけで、あまり期待しないでください。
]]> 日記 2010-01-04T22:47:09+09:00 riverocean FC2-BLOG