[[DensanWiki]]~ プロコン~ **再試合用プログラムRC版公開 [#hba290e6] デバッグ作業頼んだ。~ #java(プロコン/salesman_applet.jar,Salesman,left,600x400)~ 使用方法~ ものを置いてCalc→Walk~ 右下で最短経路トップ10を切り替え~ 自分が使うソフトなので、入力チェックとかいちいちしません。~ ***実装内容 [#haa5b872] ・''全面''書き直し(前回があまりに醜いコーディングしてたから)~ ・''A*''を用いて、ノード(荷物)間の''距離テーブル''を生成~ ・''巡回セールスマン''を''分岐限定法''を用いながら丁寧に解いている~ ・得られた最短経路トップ10を保持 切り替え可能~ ・経路の距離を表示~ ・計算の高速化(''数100%''の高速化を図ってる。測ってないから具体数はないが)~ ・そのため荷物13~5個位までなら実用レベルの計算量に抑えている。~ ***まとめると [#sb9e86fd] ・''100%''最短経路を提示する~ ・荷物の積載を含めた計算を行ってない為、コスト最良解ではない。~ ・が、どーせ取り合いですし、簡単にならExcelで計算可能。~ ・また、一度戻って取ってくる場合には非対応(ほとんどこれが最適解になることはないし)~ ***今後に向けて [#re8a2a0f] ・やる気ない~ **再試合に向けて [#q68be7d5] 前回のエキシビジョンからどう変えるか~ 現状~ ・全通り探索~ ・計算量が酷い~ ・人間の意志の反映量が大きすぎる気がする~ ~ 現在考えてる案~ ・荷物と荷物のルート探索(A*)をあらかじめ全荷物に対して行う~ ・GA使って巡回セールスマンを解く。~ ・できれば多数生成して、競わせた中で一番いいルートを選ぶ~ ~ が、面倒だから全通り探索の計算量を低減させて使うことになりそう。~ 相手の動きを読む?部分がまったく欠落してしまうけどね。~ ま、どーせ運ですし。~ ***分かりやすいデータ [#n04f9764] #ref(graph.png) 青の所で戦わないと予選通過は厳しい か。~ ルート探索精度に差があまりないからやっぱり運ですね。~ **大まかな流れとか [#o8a16021] 簡単に言うと~ とりあえず最初にいく目的地を決める~ ↓~ %%最短%%でそこまでいく~ 追記:最初は遠い方がいいかも。最後に近場の荷物を拾う方が効率よさそう。~ ↓~ 着いたら荷物拾って次へ(%%ここから先はなるべく近い順に回った方がいいかもね%%)~ 追記:どうも障害物が多くなるとちゃんと考えないと遅くなっちゃうねぇ。。面倒だねぇ('A`)~ ↓~ ループ~ ↓~ 荷物を全部回ったらゴール~ (まだ荷物が余ってた場合そこまでいってもいい。ただそれで有利になるかといえば微妙)~ ~''こんな感じが一番処理も少なくてシンプルかつ融通のきくプログラムが書けるような気がする''~ ~まぁ結局は運も大事。~ ***というわけで書いてみた。 [#fa409e17] 言語は''Java''。んーJavaがインターフェース作るの楽っ♪(Swing使用)~ バグとか結構放置気味だけど、なかなか楽しめる。~ 大体三日位で書いてみた。(1000行弱)~ ま、デバッグ兼ねて公開中~ どんな迷路でもサクサク解くのでお試しあれ。(まぁフィールドのサイズは常識の範囲内で)~ #java(プロコン/procon2.jar,Astar_Frame,left,600x400)~ Java入れてないミジンコは[[こちら:http://www.java.com/ja/]]からダウンロードしてくれ~ あなたと JAVA,今すぐダウンロード☆~ -次の荷物までのルートは''必ず''最短ルートを示す。 -が、荷物を選ぶ行程が適当(直線距離で近いやつを積極的に選ぶ)なので、全体で最短ではない。(もっといい次の荷物の選び方がある) -モチベーションがちょっと落ちてるのでそのへん後回し。。。 -まぁ今後そのへんはなんとかするとして、あとは荷物を運ぶ数を決めることか。 -荷物の数は、基本的に''勘''で設定しようかなぁ。。。ルール微妙だからわかんね。 ***10/5 改良 [#k626f6d4] -とりあえず次の荷物の選び方をなんとかした。(実際の道のりの長さで判定)計算量が膨大に増えた。けど体感できないレベル。最近のコンピュータはすごい。 -また暫定的に最初の荷物は一番遠くを取るようにした。これにより、最後のほうに残る荷物がゴール周辺になり、そのあたりの荷物を回収することで、重量による燃料ロストを減らす効果あり。 -かなり高確率で最短ルートを通るようになったはず。(90%位?) -あとは評価関数でも作って、荷物の数、ゴールまでの距離、あたりからよりよい可能性の高いルートを探す方法をとるかな。。。面倒ですねぇ。大体、人間様が考えてもどーすれば一番いいか分からないという時点で。。。w ~Intneko 私的メモ~ 線形リストで保持してるもの:荷物。探索されたマス。~ 内部で距離の取得もやってる。~ 上記外で計算部で保持してるもの:プレイヤーの位置。開始位置。フィールド。最近のルート。別スレッドの有無~~ - Test -- [[IntNeko]] &new{2008-09-22 (月) 00:12:00}; - 自分のはコンパイルが通らない・・・orz しかも文字化けしやがった(泣) ○速報:公式ページに追加情報あり! -- [[cls]] &new{2008-10-05 (日) 19:59:04}; - ↓ に主なルールをまとめた物を。9/1に作成したものなので大まかなものです。 -- [[cls]] &new{2008-10-05 (日) 20:13:03}; - 了解っ まったり目を通しとく。 -- [[IntNeko]] &new{2008-10-06 (月) 02:02:03}; #comment