Qual è il modo più veloce per trovare la somma maggiore di elementi adiacenti M in una matrice

Question

Supponiamo di avere una matrice quadrata di dimensione N (N < = 50) e gli elementi adiacenti non includono le diagonali.

Come posso trovare la somma più grande tra M elementi adiacenti, dato M?

Ad esempio, prendere questa matrice 4x4:

Matrix:   For M = 3   For M = 4 

3 1 5 2   3 1 5 2   3 1 5 2 
2 6 1 3   2 [6] 1 3   2 [6] 1 3 
1 4 4 2   1 [4][4] 2   1 [4] 4 2 
5 3 2 7   5 3 2 7   [5][3] 2 7 

        Biggest = 14  Biggest = 18 

tentato di eseguire questo modo, ma dopo una certa dimensione, è molto lenta.

#include <bits/stdc++.h> 

using namespace std; 

int mat[51][51]; 
int mark[51][51]; 
int m, n; 
int biggest; 

void search(int row, int column, int sum, int steps){ 
    if(row < 0 || row >= n || column < 0 || column >= n || mark[row][column]) { 
     return; 
    } 

    sum += mat[row][column]; 

    mark[row][column] = 1; 

    if(steps == m){ 

     if(biggest < sum) biggest = sum; 

    } 

    else{ 

     search(row - 1, column, sum, steps+1); 
     search(row + 1, column, sum, steps+1); 
     search(row, column + 1, sum, steps+1); 
     search(row, column - 1, sum, steps+1); 
    } 

    mark[row][column] = 0; 
} 


int main(){ 

    memset(mat, 0, sizeof(mat)); 
    memset(mark, 0, sizeof(mark)); 

    biggest = 0; 
    scanf("%d", &n); 
    scanf("%d", &m); 

    for(int i = 0; i < n; i++){ 
     for(int j = 0; j < n; j++){ 
      scanf("%d", &mat[i][j]); 
     } 
    } 


    for(int i = 0; i < n; i++){ 
     for(int j = 0; j < n; j++){ 
      search(i, j, 0, 1); 
     } 
    } 


    printf("%d", biggest); 
    return 0; 

} 

Answer 1

_{Questa risposta non include codice (ancora) e sarà successivamente esteso con un'implementazione dell'algoritmo descritto}

La difficoltà principale è che certe "forme" vengono elaborati molte volte. Considera una selezione che è un rettangolo pieno. Può iniziare da qualsiasi cella e attraversare in più modi diversi ("percorsi ricorsivi") per raggiungere la stessa selezione (e ovviamente lo stesso calcolo). È questo problema che deve essere affrontato.

Per fare questo, è necessario precompute le varie forme che possono essere selezionati per la proposta M, quindi scorrere la matrice e per ogni cella (che serve come parte superiore sinistra della figura) calcolare e confrontare la somma per tutte le selezioni di forma.

Il precomputation viene fatto utilizzando una funzione ricorsiva proprio come nella domanda che "dipinge" un (2M-1) matrice con le cellule del percorso, iniziando nel mezzo. Nella condizione di fine (le celle M selezionate), la forma generata viene confrontata con le forme esistenti nella "lista di forme" che si accumula e viene aggiunta solo se non è già presente. necessario risolvere per lo scenario di forma "+".

ottimizzazioni dovrebbero essere utilizzati nella fase Precompute evitare "trasferimento" il problema del calcolo alla fase precomputation molto grandi M s, per esempio, attraversamenti limite tale che è illegale andare sopra la riga iniziale (e come risultato, la matrice di forma deve essere solo M (2M-1) grande).

Answer 2

Ecco una ricerca elementare di primo livello in Python, utilizzando i set per cancellare le forme (è una revisione della mia risposta qui, Maximum sum of k connected elements of a matrix). Mi sembra che un DFS dovrebbe mantenere le dimensioni dello stack nell'ordine di O(m) (sebbene lo spazio di ricerca sia ancora enorme).

from sets import Set 

def f(a,m): 
    stack = [] 
    hash = Set([]) 
    best = (0,[]) # sum, shape 
    n = len(a) 

    for y in range(n): 
    for x in range(n): 
     stack.append((a[y][x],Set([(y,x)]),1)) 

    while len(stack) > 0: 
    s,shape,l = stack.pop() 

    key = str(sorted(list(shape))) 

    if l == m and key not in hash: 
     hash.add(key) 
     if s > best[0]: 
     best = (s,shape) 
    elif key not in hash: 
     hash.add(key) 
     for (y,x) in shape: 
     if y < n - 1 and (y + 1,x) not in shape: 
      copy = Set(shape) 
      copy.add((y + 1,x)) 
      stack.append((s + a[y + 1][x],copy,l + 1)) 
     if y > 0 and (y - 1,x) not in shape: 
      copy = Set(shape) 
      copy.add((y - 1,x)) 
      stack.append((s + a[y - 1][x],copy,l + 1)) 
     if x < n - 1 and (y,x + 1) not in shape: 
      copy = Set(shape) 
      copy.add((y,x + 1)) 
      stack.append((s + a[y][x + 1],copy,l + 1)) 
     if x > 0 and (y,x - 1) not in shape: 
      copy = Set(shape) 
      copy.add((y,x - 1)) 
      stack.append((s + a[y][x - 1],copy,l + 1)) 

    print best 
    print len(hash) 

uscita:

matrix = [[3, 1, 5, 2,]   
     ,[2, 6, 1, 3,]   
     ,[1, 4, 4, 2] 
     ,[5, 3, 2, 7]] 

f(matrix,4) 
""" 
(18, Set([(3, 1), (3, 0), (2, 1), (1, 1)])) 
205 hash length 
"""