算法：距離變換 - 任何更快的算法？

Question

我試圖解決距離轉換問題（使用曼哈頓的距離）。基本上，使以0和1點的矩陣，程序必須分配的每個位置的距離至最接近1.例如，對於這一個

0000 
0100 
0000 
0000 

距離變換矩陣是從我的頭

2123 
1012 
2123 
3234 

可能的解決方案是：

最慢的人（最慢的，因爲我已經嘗試實現他們 - 他們落後於非常大的矩陣）：

1. 蠻力 - 每1該程序讀取，從開始發生相應的變化，直到距離終點。

   0的

2. 廣度優先搜索 - 每一個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 
   

我想問問，如果有更快的解決這一問題（從別人的代碼讀取）

廣度優先搜索。我試圖搜索距離變換的算法，但其中大部分都在處理歐幾里德距離。

在此先感謝。

Answer 1

廣度優先搜索將執行Θ(n*m)操作，其中n和m是矩陣的寬度和高度。

你需要輸出Θ(n*m)號碼，所以你不能從理論角度得到任何比這更快。

我假設你不感興趣的一個涉及緩存和優化等討論會。

---

請注意，此解決方案在更有趣的情況下工作。例如，假設同樣的問題，但也可能有不同的「來源」：

00000 
01000 
00000 
00000 
00010 

使用BFS，你將得到下面的距離到最接近源在同一時間複雜度：

21234 
1
21223 
32212 
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) 

這是非常短暫和容易。

---

除非您編寫和測試它，否則沒有簡單的方法來比較兩種算法。假定一個有效的有界隊列實現（具有陣列上），有每個細胞下列主要操作：

• BFS：隊列插入/缺失，每個節點的訪問5次（四次由鄰居，以及一個超時隊列
• 直接公式）：兩個減法和兩個if小號

它真的會依賴於編譯器和優化，以及具體的CPU和內存架構，說這將有更好的表現。

這就是說，我建議你去看看哪個更簡單。但是請注意，對於多個來源，在第二種解決方案中，您需要對陣列進行多次通過（或一次通過多次距離計算），並且對於足夠數量的源，肯定會比BFS具有更差的性能。

Answer 2

你不需要一個隊列或任何類似的東西。注意，如果（i，j）距離（k，l）的距離爲d，則實現該距離的一種方式是左移或右移| i-k |次，然後向上或向下| j -l |倍。

因此，用大數字初始化您的矩陣，並在您輸入的任何地方都有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的距離。