Blue Nova

管理人のフリーダム横行地帯。別名:管理人の反省室。

logs

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

解/戦支度

前回の記事の続きです。

夏の陣の計画も立ってきたし、プログラムも書けたし、
後は持ち物の準備をするだけになったところで、
前回提示した"巡回セールスマン問題"について自分なりに考えてみようと思います。
素人同然なので色々と考えの及ばないところはありますが、その辺はご勘弁を。



むしろ何時に家を出発するかが問題だったりする。
いずれにせよ、結局はタフなスケジュールになりそうだが。



今回、一つの地区に回りたい箇所が16ほど固まっています。
最短距離で巡回するにはどのような順番で回ればいいかという話ですが、
総当りで解こうとなると16地点の順列で、
16! = 20922789888000(約21兆)通りのルートを試さないとなりません。
天文学的な数字ですね。

総当りの方法は実際に作ってみましたが、
地点数10で計算時間が1分を超える結果となりました。
これで16地点の解を求めようとすると、単純計算で10年以上掛かることになります。
ぶっちゃけ、計算してみて驚きました。
・・・そういう訳で、総当りで答を探すのは止めにします。

さて次に、試行の回数を減らす方法を考えましょう。
21兆あるルートの集合を覗いてみると、
割と効率のいいルートと明らかに無駄の多いルートが存在するわけです。
総当りではこれらを全て試してきましたが、
実際のところは後者のルートを試しても時間の無駄なのですよ。

という訳で、なるべく後者のルートは試さない方向でいきたい。
ここでアルゴリズムを導入すると、試行の回数を大幅に減らす事ができます。
詳細を話そうとすると収拾がつかないので省略しますが、
興味のある人は"遺伝的アルゴリズム"で調べてみると良いかな、と。


問題
で、肝心要の問題ですが、
今回はこういう点の集合をコンピュータに与えてみました。
この点全てを最短で回るには、
どのようなルートにすれば良いかをコンピュータに調べさせるわけです。

解3
とりあえず短そうなルートを無難に辿ってみるとこんな感じになるし、

解2
面倒臭そうなルートにしてみると、こんな感じになります。

解1
やろうと思えば、こんな壮絶なルートにすることだって可能です。
ぶっちゃけありえないけど。

最適解
まぁ巡回ルートの取り方にも色々とありますが、これが恐らく最短のルートです。
正確には、発見できたルートの中で最短のもの、ですが。
図示してみれば実にシンプルなものですね。

さて、実際には各々のブースに優先の度合いも付けているため、
最短のルートをそのまま適用するというわけにはいきません。
また、問題の定義の関係で、図ではぐるりと一周するルートを表示していますが、
わざわざそんな真似をする必要もないので、改めて始点と終点を定めます。


・・・まあ、こうして当日の巡回ルートを決定していく訳です。
今回の場合、巡回セールスマン問題の非常に簡単な場合しか用いませんでしたが、
もっと奥深い領域まで行くと、巡回する都市数が1000や10000を超える問題も存在します。
自分が組んだアルゴリズムではこのレベルの問題には対抗できないので、
そういう意味では自分もまだまだですね。

この課題は早くも一段落してしまった感じですが、
自分の知識で改善できる部分はまだあるので、今後も少しずつ弄っていこうと思っています。


ところで今回の例題は、実際に地図に書き込んだチェックポイントの位置に即していますが、
これらは全て同一の区画に存在するチェックポイントです。

・・・そう、他の区画にもチェックポイントがあるんですよ。
それも合わせて、チェックポイントの数は全部で26。正直恐ろしい数字です。
体力的にも時間的にも、サイフの中身的にも恐ろしいです。
というか、結局ここまで膨れ上がってしまった辺り、どうしようもないんですが・・・。

流石にこれら全てを回るのは厳しいので、可能な限りシェイプアップしたいところです。
いずれにせよ、覚悟を決める必要はありそうですが。

まあ、今日はこの辺で。

トラックバックURL

http://veiscroiz.blog53.fc2.com/tb.php/214-b6fb9d44

この記事へのトラックバック

この記事へのコメント

Battle without honor or humanity

かなり久しぶりだな。なんかそうでもない気がするけど。

たかだか買い物、って言ったらアレかもしれないが、一大事のようだな。俺は行ったことがないのでわかんねーがさながら戦場のようで。まさしく天下分け目の有明ってか。それで現代の戦乱は情報戦だと。そういうことだな!で、まあその通りにいけば勝てるのか?とにかく幸運を祈る。

俺は明日は平和的にポップン18のインストアイベントに招待されたから行ってきます(自慢)。抽選で40名様だぜ(自慢)。ファンなら垂涎だろうな(Jiman)。うへへ(自慢)。でも羨ましがってくれる趣味の合う友人がいないんだぜ(落胆)。うへへ(嗚咽)。

  • 13/08/2010
  • ***の伝道師 ♦-
  • URL
  • 編集 ]

環境が環境だからな、コメントで喋るのは久し振りだw

"買い物"か。まぁ表面的には本屋巡りみたいなものだよね。
まぁ、あの地獄っぷりは行った事がある人じゃないと分からないタイプの物なのかも。
そういうわけで、情報は大事だよ。
ただ集めるだけじゃなくて、集めた情報を分かりやすくまとめるのも大事だと思う。
勝てるか・・・というより目標達成できるかは、
つまる所実践だから当日にならないとわからないけど、
ここはひとつ頑張ってみますw

音ゲーといえば、jubeatやってみて楽しかったから、
家の近くや大学の近くの配置店舗を調べてみた。
気が向いたらちょくちょく触っていこうと思ってる。
やっぱりLv6が限界だけどねw

  • 14/08/2010
  • 管理人 ♦CFjt9lo6
  • URL
  • 編集 ]
コメント投稿フォーム

Paging Navigation

Navigations, etc.

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。