1

この問題は、単純に O(n 3 ) 時間で簡単に解決できます。問題は次のようなものです。

数直線上には N 個の固有点があります。一定の間隔で数直線上のすべての点をカバーしたいとします。間隔はどこにでも配置できます。間隔を作成するにはコストがかかりB + MXます。ここで、 は間隔をB作成する初期コストであり、 Xは間隔の長さの半分Mであり、 は間隔の長さあたりのコストです。すべての間隔をカバーするための最小コストを見つけたいとします。

サンプルデータ：

Points = {0, 7, 100}
B = 20
M = 5

20 + 3.5×5 のコストで間隔 [0,7] を構築し、コスト 100 + 0×5 で [100,100] の間隔を構築できるため、最適解は 57.50 になります。合計すると 57.50 になります。

私は O(n 3 ) ソリューションを持っています。ここで、DP は からのポイントをカバーするための最小コスト[left, right]です。したがって、答えは になりますDP[1][N]。すべてのペアについて、(i,j)反復しk = {i...j-1}て計算するだけDP[i][k] + DP[k + 1][j]です。

ただし、このソリューションは O(n 3 ) (行列乗算のようなものだと思います) であるため、N > 2000 では遅すぎます。これを最適化する方法はありますか?

4

1 に答える 1

2

二次解は次のとおりです。

  1. すべてのポイントを座標で並べ替えます。ポイントを呼び出しpます。

  2. 最初のポイントをカバーするための最小コストになるAような配列を保持します。ゼロに設定し、他のすべての要素を無限大に設定します。A[k]kA[0]

  3. からまでのそれぞれとkから からまでのそれぞれについて、設定します。0n-1lk+1nA[l] = min(A[l], A[k] + B + M*(p[l-1] - p[k])/2);

最終的には、すべてのポイントA[n]をカバーするための最小コストであると確信できるはずです。n(すべての可能な最小カバー間隔を考慮し、ある意味で「左から右」に行いました。)

これを高速化して、O(n log n) 時間で実行できます。手順 3 を次のように置き換えます。

設定しA[1] = Bます。kから2までのそれぞれについてn、 を設定しA[k] = A[k-1] + min(M/2 * (p[k-1] - p[k-2]), B)ます。

ここでの考え方は、前のインターバルを延長して次のポイントをカバーするか、前のインターバルを で終了しp[k-2]て新しいインターバルを開始することp[k-1]です。そして、その決定を下すために知っておく必要がある唯一のことは、2 点間の距離です。

また、 を計算するときにA[k]の値だけが必要だったことにも注意してくださいA[k-1]。特に、配列全体を格納する必要はありませんA。その最新の要素のみ。

于 2012-12-15T06:05:38.410 に答える