2D-Peak-Finding-Algorithmus in O (n) Worst-Case-Zeit?

Question

Ich machte this Kurs auf Algorithmen von MIT. In der allerersten Vorlesung stellt der Professor folgendes Problem vor: -

Ein Peak in einem 2D-Array ist ein Wert, so dass alle 4 Nachbarn kleiner oder gleich sind, d. für

a[i][j] ein lokales Maximum zu sein, finden

a[i+1][j] <= a[i][j] 
&& a[i-1][j] <= a[i][j] 
&& a[i][j+1] <= a[i][j] 
&& a[i+1][j-1] <= a[i][j] 

Jetzt gegeben einen NxN 2D-Array, einen Spitzen in der Anordnung.

Diese Frage kann in O(N^2) Zeit gelöst werden, indem man über alle Elemente iteriert und einen Peak zurückgibt.

Jedoch kann es optimiert werden, um in O(NlogN) Zeit gelöst werden, indem Sie eine teilen und erobern Lösung wie erklärt here.

Aber sie haben gesagt, dass es einen O(N) Zeitalgorithmus gibt, der dieses Problem löst. Bitte schlagen Sie vor, wie wir dieses Problem in O(N) Zeit lösen können.

PS (Für diejenigen, die Python kennen) Der Kurs Mitarbeiter hat einen Ansatz here (Problem 1-5. Peak-Finding Proof) erklärt und auch einige Python-Code in ihren Problem-Sets zur Verfügung gestellt. Aber der erklärte Ansatz ist absolut nicht offensichtlich und sehr schwer zu entziffern. Der Python-Code ist gleichermaßen verwirrend. Daher habe ich den Hauptteil des folgenden Codes für diejenigen kopiert, die Python kennen und wissen, welcher Algorithmus aus dem Code verwendet wird.

def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None): 
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0: 
     return None 

    subproblems = [] 
    divider = [] 

    if rowSplit: 
     # the recursive subproblem will involve half the number of rows 
     mid = problem.numRow // 2 

     # information about the two subproblems 
     (subStartR1, subNumR1) = (0, mid) 
     (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1)) 
     (subStartC, subNumC) = (0, problem.numCol) 

     subproblems.append((subStartR1, subStartC, subNumR1, subNumC)) 
     subproblems.append((subStartR2, subStartC, subNumR2, subNumC)) 

     # get a list of all locations in the dividing column 
     divider = crossProduct([mid], range(problem.numCol)) 
    else: 
     # the recursive subproblem will involve half the number of columns 
     mid = problem.numCol // 2 

     # information about the two subproblems 
     (subStartR, subNumR) = (0, problem.numRow) 
     (subStartC1, subNumC1) = (0, mid) 
     (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1)) 

     subproblems.append((subStartR, subStartC1, subNumR, subNumC1)) 
     subproblems.append((subStartR, subStartC2, subNumR, subNumC2)) 

     # get a list of all locations in the dividing column 
     divider = crossProduct(range(problem.numRow), [mid]) 

    # find the maximum in the dividing row or column 
    bestLoc = problem.getMaximum(divider, trace) 
    neighbor = problem.getBetterNeighbor(bestLoc, trace) 

    # update the best we've seen so far based on this new maximum 
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen): 
     bestSeen = neighbor 
     if not trace is None: trace.setBestSeen(bestSeen) 

    # return when we know we've found a peak 
    if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen): 
     if not trace is None: trace.foundPeak(bestLoc) 
     return bestLoc 

    # figure out which subproblem contains the largest number we've seen so 
    # far, and recurse, alternating between splitting on rows and splitting 
    # on columns 
    sub = problem.getSubproblemContaining(subproblems, bestSeen) 
    newBest = sub.getLocationInSelf(problem, bestSeen) 
    if not trace is None: trace.setProblemDimensions(sub) 
    result = algorithm4(sub, newBest, not rowSplit, trace) 
    return problem.getLocationInSelf(sub, result) 

#Helper Method 
def crossProduct(list1, list2): 
    """ 
    Returns all pairs with one item from the first list and one item from 
    the second list. (Cartesian product of the two lists.) 

    The code is equivalent to the following list comprehension: 
     return [(a, b) for a in list1 for b in list2] 
    but for easier reading and analysis, we have included more explicit code. 
    """ 

    answer = [] 
    for a in list1: 
     for b in list2: 
      answer.append ((a, b)) 
    return answer 

Answer 1

1. Lassen Sie sich die Breite des Feldes annimmt größer als die Höhe ist, sonst werden wir in einer anderen Richtung aufgespalten werden.
2. Teilen Sie das Array in drei Teile: zentrale Spalte, linke Seite und rechte Seite.
3. Gehen Sie durch die zentrale Spalte und zwei benachbarte Spalten und suchen Sie nach Maximum.
   • Wenn es in der mittleren Spalte ist - das ist unser Spitzen
   • Wenn es auf der linken Seite ist, führen Sie diesen Algorithmus auf Subarray left_side + central_column
   • Wenn es auf der rechten Seite ist, führen Sie diesen Algorithmus auf Subarray right_side + central_column

Warum dies funktioniert:

Für Fälle, in denen das maximale Element in der mittleren Spalte ist - offensichtlich. Wenn dies nicht der Fall ist, können wir von diesem Maximum zu steigenden Elementen übergehen und werden die zentrale Reihe definitiv nicht überschreiten, so dass definitiv ein Peak in der entsprechenden Hälfte existiert.

Warum diese O (n) ist:

Schritt # 3 in weniger als oder gleich max_dimension Iterationen und max_dimension mindestens Hälften auf je zwei Algorithmusschritte. Dies ergibt n+n/2+n/4+..., was O(n) ist. Wichtiges Detail: Wir teilen uns nach der maximalen Richtung auf. Bei quadratischen Arrays bedeutet dies, dass die Splitrichtungen alternieren. Dies ist ein Unterschied zum letzten Versuch in der PDF-Datei, mit der Sie verknüpft sind.

Ein Hinweis: Ich bin mir nicht sicher, ob es genau den Algorithmus in dem Code entspricht, den Sie gaben, es kann oder kann nicht ein anderer Ansatz sein.

Answer 2

, die @ Max1000-Algorithmus implementiert. Der folgende Code findet eine Spitze im 2D-Array in linearer Zeit.

import java.util.*; 

class Ideone{ 
    public static void main (String[] args) throws java.lang.Exception{ 
     new Ideone().run(); 
    } 
    int N , M ; 

    void run(){ 
     N = 1000; 
     M = 100; 

     // arr is a random NxM array 
     int[][] arr = randomArray(); 
     long start = System.currentTimeMillis(); 
//  for(int i=0; i<N; i++){ // TO print the array. 
//   System. out.println(Arrays.toString(arr[i])); 
//  } 
     System.out.println(findPeakLinearTime(arr)); 
     long end = System.currentTimeMillis(); 
     System.out.println("time taken : " + (end-start)); 
    } 

    int findPeakLinearTime(int[][] arr){ 
     int rows = arr.length; 
     int cols = arr[0].length; 
     return kthLinearColumn(arr, 0, cols-1, 0, rows-1); 
    } 

    // helper function that splits on the middle Column 
    int kthLinearColumn(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){ 
     if(loCol==hiCol){ 
      int max = arr[loRow][loCol]; 
      int foundRow = loRow; 
      for(int row = loRow; row<=hiRow; row++){ 
       if(max < arr[row][loCol]){ 
        max = arr[row][loCol]; 
        foundRow = row; 
       } 
      } 
      if(!correctPeak(arr, foundRow, loCol)){ 
       System.out.println("THIS PEAK IS WRONG"); 
      } 
      return max; 
     } 
     int midCol = (loCol+hiCol)/2; 
     int max = arr[loRow][loCol]; 
     for(int row=loRow; row<=hiRow; row++){ 
      max = Math.max(max, arr[row][midCol]); 
     } 
     boolean centralMax = true; 
     boolean rightMax = false; 
     boolean leftMax = false; 

     if(midCol-1 >= 0){ 
      for(int row = loRow; row<=hiRow; row++){ 
       if(arr[row][midCol-1] > max){ 
        max = arr[row][midCol-1]; 
        centralMax = false; 
        leftMax = true; 
       } 
      } 
     } 

     if(midCol+1 < M){ 
      for(int row=loRow; row<=hiRow; row++){ 
       if(arr[row][midCol+1] > max){ 
        max = arr[row][midCol+1]; 
        centralMax = false; 
        leftMax = false; 
        rightMax = true; 
       } 
      } 
     } 

     if(centralMax) return max; 
     if(rightMax) return kthLinearRow(arr, midCol+1, hiCol, loRow, hiRow); 
     if(leftMax) return kthLinearRow(arr, loCol, midCol-1, loRow, hiRow); 
     throw new RuntimeException("INCORRECT CODE"); 
    } 

    // helper function that splits on the middle 
    int kthLinearRow(int[][] arr, int loCol, int hiCol, int loRow, int hiRow){ 
     if(loRow==hiRow){ 
      int ans = arr[loCol][loRow]; 
      int foundCol = loCol; 
      for(int col=loCol; col<=hiCol; col++){ 
       if(arr[loRow][col] > ans){ 
        ans = arr[loRow][col]; 
        foundCol = col; 
       } 
      } 
      if(!correctPeak(arr, loRow, foundCol)){ 
       System.out.println("THIS PEAK IS WRONG"); 
      } 
      return ans; 
     } 
     boolean centralMax = true; 
     boolean upperMax = false; 
     boolean lowerMax = false; 

     int midRow = (loRow+hiRow)/2; 
     int max = arr[midRow][loCol]; 

     for(int col=loCol; col<=hiCol; col++){ 
      max = Math.max(max, arr[midRow][col]); 
     } 

     if(midRow-1>=0){ 
      for(int col=loCol; col<=hiCol; col++){ 
       if(arr[midRow-1][col] > max){ 
        max = arr[midRow-1][col]; 
        upperMax = true; 
        centralMax = false; 
       } 
      } 
     } 

     if(midRow+1<N){ 
      for(int col=loCol; col<=hiCol; col++){ 
       if(arr[midRow+1][col] > max){ 
        max = arr[midRow+1][col]; 
        lowerMax = true; 
        centralMax = false; 
        upperMax = false; 
       } 
      } 
     } 

     if(centralMax) return max; 
     if(lowerMax) return kthLinearColumn(arr, loCol, hiCol, midRow+1, hiRow); 
     if(upperMax) return kthLinearColumn(arr, loCol, hiCol, loRow, midRow-1); 
     throw new RuntimeException("Incorrect code"); 
    } 

    int[][] randomArray(){ 
     int[][] arr = new int[N][M]; 
     for(int i=0; i<N; i++) 
      for(int j=0; j<M; j++) 
       arr[i][j] = (int)(Math.random()*1000000000); 
     return arr; 
    } 

    boolean correctPeak(int[][] arr, int row, int col){//Function that checks if arr[row][col] is a peak or not 
     if(row-1>=0 && arr[row-1][col]>arr[row][col]) return false; 
     if(row+1<N && arr[row+1][col]>arr[row][col]) return false; 
     if(col-1>=0 && arr[row][col-1]>arr[row][col]) return false; 
     if(col+1<M && arr[row][col+1]>arr[row][col]) return false; 
     return true; 
    } 
}