プロコンのバックアップ(No.16)

DensanWiki
プロコン
跡地。

え？今日再試合！？ †

というわけで再試合があった。
結果だけ書くと６位。予選落ち。

↑

敗因 †

最終的なコストをちょっと見誤ったかな
どの荷物を取ればいいか計算すべきだったかな。勘でやっちゃった。
（これに関しては通信の不具合やらでばたばたしてたし仕方ないけど)
運がなかった。勝負事には仕方ないねこれ。

↑

語られない伝説 †

当事者（俺）が開始直前に今日が再試合があることを知った（帰りそうだった）
プログラムを用意してなくてブラウザからこのサイト開いて計算させた。
熊本電波高専は準備の段階は最速だった（運営から「まだ早い」と言われるほどに）
経路探索時間はなんと３秒弱（計算時間として３０分ほど時間が与えられるのに）

↑

総評 †

もうちょっとルールを考えてほしかったかな。。。（全体的に浅い）
みんな経路がかぶるかぶる。。あとは運という。。。
ま、エキシビジョンでのプログラムでは１年かけても計算できなかったであろう経路探索を
わずか３秒で計算できたことに満足した。
(てか、高速化に無駄に力入れすぎた感もあるが。。）
以上

↑

再試合用プログラムＲＣ版公開 †

デバッグ作業頼んだ。

使用方法
ものを置いてCalc→Walk
右下で最短経路トップ１０を切り替え
自分が使うソフトなので、入力チェックとかいちいちしません。

↑

実装内容 †

・全面書き直し(前回があまりに醜いコーディングしてたから）
・A*を用いて、ノード（荷物）間の距離テーブルを生成
・巡回セールスマンを分岐限定法を用いながら丁寧に解いている
・厳密解の計算なので確実に最短経路
・得られた最短経路トップ１０を保持　切り替え可能
・経路の距離を表示
・バイトコードレベルの計算の高速化（数１００%の高速化を図ってる。測ってないから具体数はないが）
・そのため荷物１３～５個位までなら実用レベルの計算量に抑えている。

↑

まとめると †

・100％最短経路を提示する
・荷物の積載を含めた計算を行ってない為、コスト最良解ではない。
・が、どーせ取り合いですし、簡単にならExcelで計算可能。
・また、一度戻って取ってくる場合には非対応（ほとんどこれが最適解になることはないし）

↑

今後に向けて †

・やる気ない

↑

再試合に向けて †

前回のエキシビジョンからどう変えるか
現状
・全通り探索
・計算量が酷い
・人間の意志の反映量が大きすぎる気がする

現在考えてる案
・荷物と荷物のルート探索(A*)をあらかじめ全荷物に対して行う
・GA使って巡回セールスマンを解く。
・できれば多数生成して、競わせた中で一番いいルートを選ぶ

が、面倒だから全通り探索の計算量を低減させて使うことになりそう。
相手の動きを読む？部分がまったく欠落してしまうけどね。
ま、どーせ運ですし。

↑

分かりやすいデータ †

青の所で戦わないと予選通過は厳しい　か。
ルート探索精度に差があまりないからやっぱり運ですね。

↑

大まかな流れとか †

簡単に言うと
とりあえず最初にいく目的地を決める
↓
最短でそこまでいく
追記：最初は遠い方がいいかも。最後に近場の荷物を拾う方が効率よさそう。
↓
着いたら荷物拾って次へ（~~ここから先はなるべく近い順に回った方がいいかもね~~)
追記：どうも障害物が多くなるとちゃんと考えないと遅くなっちゃうねぇ。。面倒だねぇ（'Ａ`）
↓
ループ
↓
荷物を全部回ったらゴール
(まだ荷物が余ってた場合そこまでいってもいい。ただそれで有利になるかといえば微妙）

こんな感じが一番処理も少なくてシンプルかつ融通のきくプログラムが書けるような気がする

まぁ結局は運も大事。

↑

というわけで書いてみた。 †

言語はJava。んーJavaがインターフェース作るの楽っ♪(Swing使用)
バグとか結構放置気味だけど、なかなか楽しめる。
大体三日位で書いてみた。(1000行弱)
ま、デバッグ兼ねて公開中
どんな迷路でもサクサク解くのでお試しあれ。(まぁフィールドのサイズは常識の範囲内で)

Java入れてないミジンコはこちらからダウンロードしてくれ
あなたと JAVA,今すぐダウンロード☆

次の荷物までのルートは必ず最短ルートを示す。
が、荷物を選ぶ行程が適当（直線距離で近いやつを積極的に選ぶ）なので、全体で最短ではない。(もっといい次の荷物の選び方がある)
モチベーションがちょっと落ちてるのでそのへん後回し。。。
まぁ今後そのへんはなんとかするとして、あとは荷物を運ぶ数を決めることか。
荷物の数は、基本的に勘で設定しようかなぁ。。。ルール微妙だからわかんね。

↑

10/5 改良 †

とりあえず次の荷物の選び方をなんとかした。（実際の道のりの長さで判定）計算量が膨大に増えた。けど体感できないレベル。最近のコンピュータはすごい。
また暫定的に最初の荷物は一番遠くを取るようにした。これにより、最後のほうに残る荷物がゴール周辺になり、そのあたりの荷物を回収することで、重量による燃料ロストを減らす効果あり。
かなり高確率で最短ルートを通るようになったはず。(90%位？)
あとは評価関数でも作って、荷物の数、ゴールまでの距離、あたりからよりよい可能性の高いルートを探す方法をとるかな。。。面倒ですねぇ。大体、人間様が考えてもどーすれば一番いいか分からないという時点で。。。ｗ
Intneko

私的メモ
線形リストで保持してるもの：荷物。探索されたマス。
内部で距離の取得もやってる。
上記外で計算部で保持してるもの：ﾌﾟﾚｲﾔｰの位置。開始位置。フィールド。最近のルート。別スレッドの有無~

Test -- IntNeko 2008-09-22 (月) 00:12:00
自分のはコンパイルが通らない・・・orz しかも文字化けしやがった(泣)　○速報：公式ページに追加情報あり！ -- cls? 2008-10-05 (日) 19:59:04
↓ に主なルールをまとめた物を。9/1に作成したものなので大まかなものです。 -- cls? 2008-10-05 (日) 20:13:03
了解っ　まったり目を通しとく。 -- IntNeko 2008-10-06 (月) 02:02:03
あら・・・26日だったの？テスト前日かよ・・・。とにかく皆さんお疲れ様でした（遅れてこういうこと言って申し訳ない）。「制限時間の600分の１以下で計算終了」って言うと凄いいい感じ。 -- cap 2008-11-28 (金) 22:52:22

プロコン のバックアップ(No.16)