我有一個二進制矩陣。每列對應于圖中的一個頂點。如果我沿著路徑行走（從“col 1”頂點開始，然后繼續到“col 2”等），我必須支付一些罰款。但是由于路上只有這么多警察，我可以等一段時間，直到下一個頂點沒有警察剩余，然后再過去。為了澄清，以下矩陣（第一行是“標題”行）：
A B C D
0 0 1 0
1 0 0 1
1 1 0 0
1 1 1 1
0 0 0 0
編碼如果我在 A 點之前額外等待 1、2 或 3 小時后我將支付費用；在 B 上，我將在 2 或 3 個額外小時后付款；在 C 上，我會在 0 或 3 小時后付款；在 D 上，如果我等待 1 或 3 個小時，我將付款。
因此，這里的最優路徑是“移動到B，等待1小時，移動到C，等待1小時，移動到D”，總成本為0。（這條路徑在下面用“X”標記）
A B C D
X X 1 0
1 X X 1
1 1 X X
1 1 1 1
0 0 0 0
但是，實作 0 并不總是可能的，我只對從左上角條目到右列的最小總和路徑之一感興趣。
如何有效地生成這樣的路徑？
天真的演算法“生成所有路徑，找到最小值”在指數時間內起作用，這對我來說并不是最優的。
我曾想過使用 DP 方法，但無論我嘗試逐行添加還是逐列添加，我都無法制定出在某些情況下不會中斷的方法
uj5u.com熱心網友回復：
讓我們從一個簡單的問題開始。假設您位于矩陣的行i、列j（即單元格(i,j)）。下一步你有什么選擇？
由于我們按列移動，因此j變為j 1. 但是對于該行，您可以貪婪地選擇支付最低罰款的行。也就是說，您可以選擇最小的i'范圍。（注意：由于行代表時間點，不能從行到，有效地縮短了我們的搜索空間）。(i 1, row_count)fine(i,j)ii-1
演算法：
( n = number of rows = len(matrix), m = number of columns)
- 對于最右邊的列，我們沒有任何進一步的路徑，因此無需修改
- 對于列
m-1 to 1，單元格的最低罰款(i,j)為
fine(i,j) = (matrix[i][j] == 1) (min_value in matrix[i][j 1] to matrix[n][j 1])
- 最小路徑成本將是
matrix[0][0]，通過檢查每列的最小值來跟蹤路徑。
我們需要討論的最后一點是，如何進入min_value in matrix[i][j 1] to matrix[n][j 1]第 2 步？如果您從row nto遍歷row 1，該任務基本上可以歸結為跟蹤已訪問的最小元素，這可以使用簡單的變數/計數器來完成。
該方法不需要額外的空間（因為我們修改了給定的矩陣）和O(M*N)時間復雜度。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452489.html
上一篇：角度測驗throwError