Il problema della miniera d'oro può essere risolto utilizzando divide et impera?

Si scopre che c'era una risposta.

L'algoritmo per farlo funziona come segue:

Dividi la griglia in quadranti. Inizia a risolvere i valori DP per il quadrante in alto a destra, quindi in alto a sinistra, quindi in basso a destra. Quando lo fai, salva solo i dati DP per le celle che delimitano gli altri quadranti e sbarazzati di tutti gli altri spazi di lavoro.

La ricorsione effettiva inizia quindi nel quadrante in basso a sinistra. Questo sottoproblema sembra identico al problema più grande - divide il quadrante in quattro e fa di nuovo la stessa cosa.

Quando arrivi a una griglia di dimensioni 2x2, risolvi normalmente usando l'approccio DP. Questo è un tempo costante. Quando hai finito di seguire il percorso attraverso quella griglia, saprai anche quale quadrante stai entrando dopo perché hai tenuto in memoria le celle di confine e puoi fare una scelta. Ora, risolvi il percorso attraverso quel quadrante, e poi l'ultimo.

Il percorso percorre solo tre quadranti a causa dei vincoli sul gruppo di mosse. Quindi stiamo solo risolvendo tre sotto-problemi, non quattro. È per questo che la ricorrenza semplifica ancora a O (n ^ 2):

T (n) = 3T (n / 2) + O (n ^ 2)

L'O (n ^ 2) è la prima parte dell'algoritmo, in cui si ottengono le celle DP confinanti. Il 3T (n / 2) è la soluzione dei tre quadranti. Questo appartiene al caso nel Teorema Master dove log_b (a) < c, quindi T (n) = O (n ^ c) = O (n ^ 2).

La ricorrenza per lo spazio è questa:

T (n) = T (n / 2) + n

Questo appartiene allo stesso caso nel Teorema Master come ricorrenza per il tempo di esecuzione. Lo spazio totale utilizzato è O (n).

C'è un problema con il tuo approccio divide et impera di dividere la griglia in quattro quadranti: le soluzioni per i quadranti non sono indipendenti l'una dall'altra. E non riesci a trovare la soluzione ottimale combinando le sub-soluzioni localmente ottimali di ogni quadrante.

+---+---+
| C | D |
+---+---+
| A | B |
+---+---+

Qui, D può essere calcolato indipendentemente. Tuttavia, la soluzione per C dipende da D, B dipende da D e A dipende da B, C, D. (La dipendenza è determinata dalla raggiungibilità.)

Risolvere il problema per un quadrante non significa che troviamo il percorso migliore. Invece, dobbiamo trovare il miglior percorso per ogni cella ai loro bordi sinistro e inferiore, poiché non sappiamo dove il miglior percorso entrerà in quel quadrante.

Le esatte complessità spaziali dipendono da ciò che stiamo cercando di calcolare:

• il percorso migliore: questo richiederà O (n) spazio per record per un quadrante con bordi n-lunghi.
• il valore del percorso migliore: questo richiederà O (1) spazio per record.

Farò un passo falso per questa discussione e denoterò lo spazio richiesto con s (n). Quindi, la soluzione di un quadrante richiede lo spazio O (n · s (n)) per i record del margine sinistro e inferiore.

La complessità spaziale totale dell'algoritmo viene quindi fornita attraverso la relazione di ricorrenza T (n) = 4 · T (n / 4) + O (n · s (n)). Questo darebbe T (n) & in; Θ (n · s (n)) per entrambe le opzioni per s (n).

Annotare l'algoritmo sarebbe estremamente noioso, quindi non lo farò qui. Tuttavia, la firma del risolutore ricorsivo potrebbe essere:

solve_quadrant(grid: int[n, n],
               x_start: int, x_end: int,
               y_start: int, y_end: int,
               upper_edge: Result[],
               right_edge: Result[])
               -> (left_edge: Result[], lower_edge: Result[])

E l'invocazione di livello superiore sarebbe:

solve(grid: int[n, n]) -> Result {
  left_edge, lower_edge = solve_quadrant(grid, 0, n, 0, n, {0, ..., 0}, {0, ..., 0})
  return lower_edge[0] // assuming bottom-left is at coordinate (0, 0)
}

Poiché l'algoritmo divide et impera deve soddisfare le stesse dipendenze dei dati di una soluzione di programmazione dinamica, è improbabile che superi la soluzione DP con la complessità dello spazio Θ (n · s (n)). In effetti, la complessità del "divide & conquistare "algo e algo DP sono equivalenti, poiché fanno la stessa cosa allo stesso modo - solo la strategia per la suddivisione è diversa. Tuttavia, la soluzione DP è molto più semplice da programmare poiché non deve considerare quante più condizioni di bordo.