SMAWK algorithm - Wikipedia, the free encyclopedia
The SMAWK algorithm is an algorithm for finding the minimum value in each row of an implicitly-defined totally monotone matrix. It is named after the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber, and Maria Klawe.[1]
For the purposes of this algorithm, a matrix is defined to be monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum. It is totally monotone if the same property is true for every submatrix (defined by an arbitrary subset of the rows and columns of the given matrix). Equivalently, a matrix is totally monotone if there does not exist a 2×2 submatrix whose row minima are in the top right and bottom left corners. Every Monge array is totally monotone, but not necessarily vice versa.
For the SMAWK algorithm, the matrix to be searched should be defined as a function, and this function is given as input to the algorithm (together with the dimensions of the matrix). The algorithm then evaluates the function whenever it needs to know the value of a particular matrix cell. If this evaluation takes O(1), then, for a matrix with r rows and c columns, the running time and number of function evaluations are both O(c(1 + log(r/c))). This is much faster than the O(rc) time of a naive algorithm that evaluates all matrix cells.
http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html
http://www.egr.unlv.edu/~larmore/Courses/CSC477/monge.pdf
https://code.google.com/p/mytestpjt/source/browse/branches/ImprovedInclusionIdentification/src/neobio/alignment/Smawk.java
Read full article from SMAWK algorithm - Wikipedia, the free encyclopedia
The SMAWK algorithm is an algorithm for finding the minimum value in each row of an implicitly-defined totally monotone matrix. It is named after the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber, and Maria Klawe.[1]
For the purposes of this algorithm, a matrix is defined to be monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum. It is totally monotone if the same property is true for every submatrix (defined by an arbitrary subset of the rows and columns of the given matrix). Equivalently, a matrix is totally monotone if there does not exist a 2×2 submatrix whose row minima are in the top right and bottom left corners. Every Monge array is totally monotone, but not necessarily vice versa.
For the SMAWK algorithm, the matrix to be searched should be defined as a function, and this function is given as input to the algorithm (together with the dimensions of the matrix). The algorithm then evaluates the function whenever it needs to know the value of a particular matrix cell. If this evaluation takes O(1), then, for a matrix with r rows and c columns, the running time and number of function evaluations are both O(c(1 + log(r/c))). This is much faster than the O(rc) time of a naive algorithm that evaluates all matrix cells.
http://www.csie.ntnu.edu.tw/~u91029/DynamicProgramming.html
時間複雜度 O(X+Y) 。
有兩個步驟。第一步叫做 REDUCE ：把一個 n x m 矩陣，砍掉幾個直行，變成 n x n 方陣。
把 n x m 矩陣的每一橫列最小值圈出來的話，砍掉的直行都是沒有最小值的；留下的直行會包含所有最小值，但是不一定每行都有最小值。
http://www.egr.unlv.edu/~larmore/Courses/CSC477/monge.pdf
https://code.google.com/p/mytestpjt/source/browse/branches/ImprovedInclusionIdentification/src/neobio/alignment/Smawk.java
Read full article from SMAWK algorithm - Wikipedia, the free encyclopedia
