3

私はこの質問に出くわしました：

2人います。n 都市の順序付けられたシーケンスがあり、都市のすべてのペア間の距離が与えられます。人物 A が最初のサブシーケンスのすべての都市を (順番に) 訪れ、人物 B が 2 番目のサブシーケンスのすべての都市を (順番に) 訪れ、その合計がA と B の移動距離の合計が最小になります。人物 A と人物 B が、それぞれのサブシーケンスの最初の都市から出発するとします。

その答えを探したところ、答えは次のとおりでした。
最初の人が都市 i に立ち寄り、2 人目が都市 j に立ち寄った場合の最小移動距離を c[i,j] とします。i< j と仮定します

c[0,j]= 1 から j-1 までの k に対する (d[k,k+1]) の合計
c[i,j] = min(c[k,j]+ d[k,i]) i!=0 の場合 ここで 0

解決策は、こちらの質問 10 でも確認できます。

さて、私の問題は次のとおり
です。1.このソリューションにはi = 1の定義がありません（kには値がないため）。
2. ここで、c[2,3] を見つけたとします。c[1,3]+ d[1,2] になります。ここで、c[1,3] は、B が 0、2、3 を訪問し、A が 1 のままか、B が 2、3 を訪問し、A が 0、1 を訪問したことを意味します。また、c[2,3] は、A が 2/2 だけを訪問したことを意味します。 0,1,2 /0,2 /1,2。そう、

 c[1,3] = min(d[0,1]+ d[2,3], d[0,2]+ d[2,3])
 c[2,3] = min(d[0,1]+ d[1,2], d[0,2]+ d[1,3], d[1,2]+d[0,3], d[0,1]+d[1,3])

ご覧のとおり、ソリューションは重複していません。

別の言い方をすれば、2 は c[1,3] の B によって既にカバーされています。したがって、c[2,3] に c[1,3] を含めると、A と B の両方が 2 を訪問することになり、コストが増えるだけなので必要ありません。

間違っている場合は修正してください。

4

2 に答える 2

1

提案された解決策がやや面倒で間違っていることは正しいです。

問題について考える方法は、いつものように、帰納的です: サイズ n の問題を解決する必要がある場合、どうすればそれをより小さな問題 (0,..., n-1) に減らすことができますか? サイズ n についてこの問題を解決したい場合、プレイヤーの 1 人がノード n をパスに入れる必要があることに注意してください。

C[i, j] 関数は、あなたが説明したように、「A が i で停止し、B が j で停止する最小コスト」を示すヘルパー関数です。

状態 C[i,j] に到達するには、プレイヤー B は j-1 から j に到達する必要がありました。ただし、もちろん j-1 = i の場合を除きます。j-1 = i の場合、j は何らかの k < i に由来する必要があります。したがって、関数 C[i, j] は次のように記述できます。

C[i,j] = {
   C[i,j-1] + d[j-1,j]                   (if i < j-1)
   min C[k,i] + d[k,j] for 0 <= k < i    (if i = j-1)
}

この設定では、基本ケースは単純に C[0, 1] = d[0,1] です。

最終的な答えは、0 <= k < n の最小 C[k, n] です。

于 2012-12-17T17:06:59.310 に答える