2005/Contest/国内予選/Problem D

2005/Contest/国内予選

Problem D : Traveling by Stagecoach †

↑

問題概要 †

↑

解法 †

普通に思いつく分には、

n! 通りの全ての馬車券の使い方について、変形した Dijkstra 法を実行
1 つの都市を 2^n 個に増やしたグラフを作って、その上で Dijkstra 法

の二通りくらい。

前者は経路途中でのチケット使用状態を保存する工夫が必要。後者は (も) 試してないのだけど、計算量が大丈夫かなあ、というのがちょっと不安。 (最大で頂点数 30 * 256 = 7680 か。...どうにかなるかなあ)

こっちの解き方なら、ハマらなければ 30 〜 40 分が目標かなあ。多分、ハマりやすいコードになりそうだけど。

もう一つには Memorization 付き TSP という荒業でも解ける模様。動的計画法っぽく行けないかなあ、と考えてての思いつき。書いてみれば実にシンプル (Memorization 付きってのは自分は実は普段やらないんだが...。普段は泉が書くコードだw) なのだけど、本番中に、実はこれで行ける、と思い至るのは難しいんじゃないかなあ、自分は思考に二時間半費やしました。ただ単に自分の頭が固くなってるだけかも...。 oTL

こちらは、正確に考えられさえすれば 20 分で書けると思います。 (三廻部; Jul 4, 2005)

ちなみに、上に書いた「動的計画法」も不可能ではないはず。本質的には、表の更新コストは Memorization TSP と変わらず。 (軽く指摘があったので。コードは書きたくないので諦めましたが)

一方に都市、もう一方に「どの馬車券を持っているか」を表す状態 (2^n 通り) という軸を持つ表を作って埋めていく。表の中には「その都市にその馬車券を持って存在している時、目的の都市にたどり着くためのコスト (時間) 」が入る。

また、縦軸の状態は、それぞれの馬車券をビットで表して 0 〜 255 までの整数に落としてしまうと、そのまま表の座標になるのでラクかな。 (これは上の TSP でも変わらず)

以下、表の例。

券集合	都市1	都市2 = b	都市3 = a	...
0 = φ	∞	0.0	∞
1 = {t1}	?	0.0	?
2 = {t2}	?	0.0	?
3 = {t1. t2}	?	0.0	?
4 = {t3}	?	0.0	?
5 = {t1. t3}	?	0.0	?
...	?	0.0	?
2^n - 1 = {t1. t2. .... tn}	?	0.0	? = 解

ただ、この表の更新順序が問題。単純に左から or 上から更新、というわけには行かないので、ちょっとやりたくない感じがして諦めました。要はこれを解消しようとしたら Memorization になったんだけど。なんか DP のままやるいい方法無いかね? (三廻部; Jul 5, 2005)

馬車券集合の方向については半順序関係を定義できるが，都市の方向については順序関係を定義できないため，単純な動的計画法は無理．都市方向について 2 重ループを回せば可能かもしれないが（cf. Warshall-Floyd 法），memorization と比較してメリットがあるとは思えない．［泉，5 Jul 2005］

↑

議論・その他 †

下の三廻部のコードは、上記の TSP のコードです。素の TSP からちくちく拡張して書いたせいで Memorization のやりかたが汚い...。 (三廻部; Jul 4, 2005)

追記。

田中君＠ combat : http://d.hatena.ne.jp/tanakh/20050702

こっちのが俺のよりよっぽどきれいだよ...。書くの早いし。 oTL (三廻部; Jul 4, 2005)

本番で思いついていたけれども、Dijkstraで解けると分かってしまったからそれでいっちゃったな。自分としては計算に5-15分くらいかかると見積もっていたけれどもそうではなかったのか。気づいてたら節約した時間でE解けてたかもなぁ。野田はあれから20分で書けたって言ってたし。（たにぐち）

256個分割の方法について、よくよく頂点数を計算してみると、 30*256よりかなり少ないことが分かりました。スタート都市は馬券を使っていないので1個、 2番目に到達する都市では8Ｃ1で8個、以降n番目(0<=n<=8)に到達する都市は8Ｃn個しか頂点を使いません。よって、完全グラフでも無い限りこの方法で十分解けると思います。それにしても自分のコードは汚い・・・。(野田 05/07/06)

↑