1

与えられた 1 つの地域があり、それは行列で表され、すべてのエントリはその地域の車の数を示します。私たちのタスクは、ガソリン ポンプを行列の 1 つのエントリに配置して、最小の移動コストを与えるブロックを選択することです。

O(n^4)すべてのエントリのプロセス全体を計算するのに時間がかかる解決策を見つけました。

この質問に対する他の良いアプローチを教えてもらえますか?

4

2 に答える 2

4

私があなたの質問を正しく理解していれば、あなたのコスト関数は Haile が彼/彼女のコメントで説明しているように、1 次元の問題に還元できるため、簡単な解決策があります。

マンハッタン メトリックでは、車が通過しなければならない列の距離が行の距離と合計されるだけなので、それらを個別に最小化できることに注意してください。

そのため、問題を 1 つの次元に縮小しました。何が起こっているのかを理解するために、これを継続的な問題に切り替える必要がありました。したがって、密度関数 p(x) があるとします (数学が機能するように、コンパクトなサポートで連続しているとしましょう)。次に、コスト関数は次のように与えられます。

\int p(x) |x-x0|

これを 2 つに分割して mod 記号を取り除き、微分します (これは、p(x) の動作が適切であると仮定する必要がある場所です)。

\int_-\infty^x_0 p(x) - \int_{x_0}^\infty p(x)

ここで、x0 の最適な位置は、この導関数をゼロにする位置になります。ただし、これは分布の中央値であることに注意してください。

元の質問であった個別の設定については、同じ議論が機能します。基本的に、E(k+1)-E(k) である離散微分を取ることができます。位置 n の車の数を a[n] と書くと、コスト関数は次のように分割されます。

E(k) = \sum_{n<k} a_n(kn) + \sum_{n>k} a_n(nk)

愚かな間違いを犯していないと仮定すると、離散微分は次のようになります。

E(k+1)-E(k) = \sum_{n<k+1} a_n - \sum_{n>k+1} a_n

したがって、解は再び中央値になります (半分の整数になる場合は、いずれかの方向に丸められます)。これが真である理由を理解するために、k が大きな負の数である場合、この導関数は明らかに負であることに注意してください (したがって、k を 1 増やすとコストが減少します)。ここで、k が増加するにつれて、導関数はゆっくりと増加します。ある時点で、初めてプラスになります。これは、k+1 が中央値より大きくなるとすぐに発生します。その後、それは正のままであるため、選択する正しい k は、中央値以下の最大の k です。

元の質問は 2 次元であったため、これを 2 回 (各軸に対して 1 回) 実行する必要があります。

于 2012-08-25T18:16:38.420 に答える
4

ルパートの答えを実用的な例 (つまり、彼が中央値の行と列と呼んでいるものを計算する方法) で拡張します。

彼が言ったように、ポンプに最適な行と最適な列を別々に見つけることができます. どのように？

問題の次の例を考えてみましょう。

3 2 7
1 8 9 
7 2 2
  • まず、ポンプに最適な列を見つけます

行列のすべての行を追加し始めます

3 2 7 -> 12
1 8 9 -> 18
7 2 2 -> 11

ポンプを最初の行に配置すると、垂直方向の合計コストは

11*2 + 18*1 + 12*0 = 30

3 列の 11 台の車両は 2 垂直単位で移動する必要があるため、2 列の 18 台の車両は 1 垂直単位で移動する必要があり、1 列の車両は垂直に移動する必要はありません。すべての行の垂直移動コストの合計を計算する必要があります。

pump in 1st row -> cost 30 = 11*2 + 18*1 + 12*0
pump in 2nd row -> cost 23 = 11*1 + 18*0 + 12*1
pump in 3rd row -> cost 42 = 11*0 + 18*1 + 12*2

したがって、ポンプの最適な列は 2 番目です。

これを O(n^2) で計算しました。これは、 n行のn台の車すべてを合計するときにO(n^2) の合計を実行し、合計を計算するときに O(n^2) の合計と乗算を実行したためです。ポンプの可能な各行の垂直コスト。

  • これで、ポンプに最適なカラムが見つかりました

各列の車を合計します。

3  2  7
1  8  9 
7  2  2
_______
11 12 18

今：

pump in 1st col -> cost 48 = 11*0 + 12*1 + 18*2
pump in 2nd col -> cost 29 = 11*1 + 12*0 + 18*1
pump in 3rd col -> cost 34 = 11*2 + 12*1 + 18*0

したがって、ポンプに最適な列は 2 番目です。

O(n^2) ステップで、ポンプを [2][2] に配置する必要があることがわかりました。

于 2012-08-25T19:36:27.987 に答える