プロコンのバックアップソース(No.8)

[[DensanWiki]]~
プロコン~
**大まかな流れとか [#o8a16021]
簡単に言うと~
とりあえず最初にいく目的地を決める~
↓~
%%最短%%でそこまでいく~
追記：最初は遠い方がいいかも。最後に近場の荷物を拾う方が効率よさそう。~
↓~
着いたら荷物拾って次へ（%%ここから先はなるべく近い順に回った方がいいかもね%%)~
追記：どうも障害物が多くなるとちゃんと考えないと遅くなっちゃうねぇ。。面倒だねぇ（'Ａ`）~
↓~
ループ~
↓~
荷物を全部回ったらゴール~
(まだ荷物が余ってた場合そこまでいってもいい。ただそれで有利になるかといえば微妙）~
~''こんな感じが一番処理も少なくてシンプルかつ融通のきくプログラムが書けるような気がする''~
~まぁ結局は運も大事。~

***というわけで書いてみた。 [#fa409e17]
言語は''Java''。んーJavaがインターフェース作るの楽っ♪(Swing使用)~
バグとか結構放置気味だけど、なかなか楽しめる。~
大体三日位で書いてみた。(1000行弱)~
ま、デバッグ兼ねて公開中~
どんな迷路でもサクサク解くのでお試しあれ。(まぁフィールドのサイズは常識の範囲内で)~
#java(プロコン/procon2.jar,Astar_Frame,left,600x400)~

Java入れてないミジンコは[[こちら:http://www.java.com/ja/]]からダウンロードしてくれ~
あなたと JAVA,今すぐダウンロード☆~
-次の荷物までのルートは''必ず''最短ルートを示す。
-が、荷物を選ぶ行程が適当（直線距離で近いやつを積極的に選ぶ）なので、全体で最短ではない。(もっといい次の荷物の選び方がある)
-モチベーションがちょっと落ちてるのでそのへん後回し。。。
-まぁ今後そのへんはなんとかするとして、あとは荷物を運ぶ数を決めることか。
-荷物の数は、基本的に''勘''で設定しようかなぁ。。。ルール微妙だからわかんね。

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

プロコンのバックアップソース(No.8)
