6

距離変換の問題を解決しようとしています(マンハッタンの距離を使用)。基本的に、0 と 1 の行列を指定すると、プログラムはすべての位置の距離を最も近い 1 に割り当てる必要があります。たとえば、この

0000
0100
0000
0000

距離変換行列は

2123
1012
2123
3234

私の頭から考えられる解決策は次のとおりです。

最も遅いもの（実装しようとしたため最も遅い-非常に大きな行列で遅れていた）：

  1. ブルートフォース - プログラムが読み取る 1 ごとに、最初から最後までそれに応じて距離を変更します。

  2. 0 からの幅優先検索 - 0 ごとに、プログラムは最も近い 1 を裏返しに探します。

  3. 2 と同じですが、1 のマークから開始し、すべての距離を裏返しにします。

  4. はるかに高速（他の人のコードから読み取る）

    1 からの幅優先検索

    1. Assign all values in the distance matrix to -1 or very big value.
2. While reading matrix, put all positions of 1's into queue.
3. While queue is not empty
    a. Dequeue position - let it be x
    b. For each position around x (that has distance 1 from it)
        if position is valid (does not exceed matrix dimensions) then
            if distance is not initialized or is greater than (distance of x) + 1 then
                I. distance = (distance of x) + 1
                II. enqueue position into queue

その問題に対するより速い解決策があるかどうか尋ねたかった. 距離変換のアルゴリズムを検索しようとしましたが、それらのほとんどはユークリッド距離を扱っています。

前もって感謝します。

4

2 に答える 2

5

幅優先検索では、とが行列の幅と高さであるΘ(n*m)操作が実行されます。nm

数値を出力する必要があるΘ(n*m)ため、理論的にはそれ以上速くなることはできません。

キャッシュやそのような最適化を含む議論に行くことに興味がないと思います。

このソリューションは、より興味深いケースで機能することに注意してください。たとえば、同じ質問を想像してみてください。ただし、異なる「ソース」が存在する可能性があります。

00000
01000
00000
00000
00010

BFS を使用すると、同じ時間の複雑さで次の距離から最も近いソースまでの距離が得られます。

21234
10123
21223
32212
32101

ただし、ソースが 1 つの場合、実際のパフォーマンスがわずかに向上する別のソリューションがあります (複雑さは同じですが) 。

その前に、次の性質を観察しましょう。

プロパティ: ソースが (a, b) にある場合、点 (x, y) のマンハッタン距離は次のとおりです。

d(x, y) = abs(x - a) + abs(y - b)

これは非常に簡単に証明できるはずです。したがって、別のアルゴリズムは次のようになります。

for r in rows
  for c in cols
    d(r, c) = abc(r - a) + abs(c - b)

これは非常に短くて簡単です。

作成してテストしない限り、2 つのアルゴリズムを簡単に比較する方法はありません。効率的なバインドされたキューの実装 (配列を使用) を想定すると、セルごとに次の主要な操作があります。

  • BFS: キューの挿入/削除、各ノードの訪問 5 回 (ネイバーで 4 回、キューから 1 回)
  • 直接式: 2 つの減算と 2 つifの s

どちらがより優れたパフォーマンスを発揮するかは、コンパイラとその最適化、および特定の CPU とメモリ アーキテクチャに大きく依存します。

そうは言っても、あなたにとってより簡単に思える方を選ぶことをお勧めします。ただし、複数のソースがある場合、2 番目のソリューションでは、アレイ上で複数のパス (または 1 つのパスで複数の距離計算) が必要になり、十分な数のソースに対して BFS よりも明らかにパフォーマンスが低下することに注意してください。

于 2013-05-06T16:31:17.730 に答える
2

キューなどはまったく必要ありません。(i,j) が (k,l) から距離 d にある場合、その距離を実現する 1 つの方法は、左または右 |ik| に移動することです。|jl| 回、次に上下 |jl| 回。

したがって、マトリックスを大きな数値で初期化し、入力のどこにでもゼロを貼り付け1ます。次のようにします。

for (i = 0; i < sx-1; i++) {
  for (j = 0; j < sy-1; j++) {
    dist[i+1][j] = min(dist[i+1][j], dist[i][j]+1);
    dist[i][j+1] = min(dist[i][j+1], dist[i][j]+1);
  }
  dist[i][sy-1] = min(dist[i][sy-1], dist[i][sy-2]+1);
}
for (j = 0; j < sy-1; j++) {
  dist[sx-1][j] = min(dist[sx-1][j], dist[sx-2][j]+1);
}

この時点で、下または右に行くだけの最短経路がすべて見つかりました。上下に同様のことを行うと、dist[i][j](i, j) から1入力行列の最も近いものまでの距離が得られます。

于 2013-05-07T09:28:23.030 に答える