L'algoritmo nella soluzione è un'esaustiva ricerca in profondità con una coppia di ottimizzazioni. Sfortunatamente, la descrizione non lo spiega esattamente.
Una ricerca esaustiva significa che cerchiamo di enumerare ogni possibile combinazione di bit. In primo luogo, prima cerchiamo di impostare tutti i bit su uno, quindi di impostare l'ultimo a zero, quindi il penultimo, quindi sia l'ultimo che il penultimo ecc.
Il primo l'ottimizzazione consiste nel tornare indietro non appena rileviamo che la parità non è uniforme. Ad esempio, quando iniziamo la ricerca e raggiungiamo la prima riga, controlliamo se quella riga ha zero parità. Se non lo fa, non continuiamo. Ci fermiamo, torniamo indietro e proviamo a impostare l'ultimo bit della riga su zero.
La seconda ottimizzazione è simile a DP, in quanto memorizziamo i risultati parziali e li riutilizziamo. Questo sfrutta il fatto che, in termini di problema, diversi percorsi nella ricerca possono convergere nello stesso stato logico. Cos'è uno stato logico di ricerca? La descrizione nella soluzione inizia a spiegarla ("inizia" essendo la parola chiave). In sostanza, il trucco è che, in un qualsiasi punto nella ricerca, il numero minimo di ulteriori lanci bit non dipende l'esatto stato di tutto il consiglio sudoku, ma solo sullo stato dei vari parità di cui abbiamo bisogno tracciare. (Vedi ulteriori spiegazioni di seguito). Ci sono 27 parità che stiamo monitorando (che rappresentano 9 colonne, 9 righe e 9 caselle 3x3). Inoltre, possiamo ottimizzare alcuni di loro. La parità per tutte le righe più alte, dato il modo in cui eseguiamo la ricerca, sarà sempre pari, mentre la parità di tutte le righe inferiori, non ancora toccate dalla ricerca, non cambia. Monitoriamo solo la parità di 1 riga. Con la stessa logica, la parità delle caselle sopra e sotto non viene presa in considerazione e dobbiamo solo tenere traccia delle caselle "attive" 3.
Pertanto, invece di 2^9 * 2^9 * 2^9 = 134,217,728 stati, abbiamo solo 2^9 * 2^1 * 2^3 = 8,192 stati. Sfortunatamente, abbiamo bisogno di una cache separata per ogni livello di profondità nella ricerca. Quindi, ci moltiplichiamo per le 81 possibili profondità della ricerca, per scoprire che abbiamo bisogno di un array di dimensioni 663,552. Per prendere in prestito da templatetypedef:
int memo[9][9][1<<9][1<<3][2];
^^ ^ ^^
| | | | |
row --+ | | | |
col -----+ | | |
column parity ---+ | |
box parity ----------+ |
current row parity---------+
1<<9 simply means 2^9, given how integers and bit shifts work.
Ulteriori spiegazioni: A causa di come funziona parità, un flip bit sarà sempre capovolgere sue 3 parità corrispondenti. Pertanto, tutte le permutazioni delle tavole di sudoku che hanno le stesse parità possono essere risolte con lo stesso modello vincente di bit flip. La funzione 'solve' dà la risposta al problema: "Supponendo di poter eseguire solo bit flip a partire dalla cella in posizione (x, y), qual è il numero minimo di bit flip per ottenere una scheda risolta."Tutte le schede di sudoku con le stesse parità produrranno la stessa risposta.L'algoritmo di ricerca considera molte permutazioni delle schede.Inizia a modificarle dall'alto, conta quanti bit si girano e poi chiede la funzione 'solve' per vedere come Se "risolva" è già stato chiamato con gli stessi valori di (x, y) e le stesse parità, possiamo solo restituire il risultato memorizzato nella cache
La parte confusa è il codice che effettivamente fa la ricerca e gli aggiornamenti di stato:
/* Try setting the cell to 1. */
ref = !A[r][c] + solve(r, c + 1, mc^1 << c, mb^1 << c/3, !p);
/* Try setting the cell to 0. */
ref = min(ref, A[r][c] + solve(r, c + 1, mc, mb, p));
potrebbe essere più chiaro reso come:
/* Try having this cell equal 0 */
bool areWeFlipping = A[r][c] == 1;
int nAdditionalFlipsIfCellIs0 = (areWeFlipping ? 1 : 0) + solve(r, c + 1, mc, mb, p); // Continue the search
/* Try having this cell equal 1 */
areWeFlipping = A[r][c] == 0;
// At the start, we assume the sudoku board is all zeroes, and therefore the column parity is all even. With each additional cell, we update the column parity with the value of tha cell. In this case, we assume it to be 1.
int newMc = mc^(1 << c); // Update the parity of column c.^(1 << c) means "flip the bit denoting the parity of column c"
int newMb = mb^(1 << (c/3)); // Update the parity of 'active' box (c/3) (ie, if we're in column 5, we're in box 1)
int newP = p^1; // Update the current row parity
int nAdditionalFlipsIfCellIs1 = (areWeFlipping ? 1 : 0) + solve(r, c + 1, newMc, newMb, newP); // Continue the search
ref = min(nAdditionalFlipsIfCellIs0, nAdditionalFlipsIfCellIs1);
Personalmente, avrei implementato i due lati della ricerca come "flip" e "do not flip". Ciò rende l'algoritmo più sensato, concettualmente. Leggerebbe il secondo paragrafo: "Prima di tutto, prima cerchiamo di non capovolgere alcun bit, quindi di lanciare l'ultimo, poi il penultimo, quindi sia l'ultimo che il penultimo, ecc. " Inoltre, prima di iniziare la ricerca, avremmo bisogno di pre-calcolare i valori di 'mc', 'mb' e 'p' per la nostra board, invece di passare 0.
/* Try not flipping the current cell */
int nAdditionalFlipsIfDontFlip = 0 + solve(r, c + 1, mc, mb, p);
/* Try flipping it */
int newMc = mc^(1 << c);
int newMb = mb^(1 << (c/3));
int newP = p^1;
int nAdditionalFlipsIfFlip = 1 + solve(r, c + 1, newMc, newMb, newP);
ref = min(nAdditionalFlipsIfDontFlip, nAdditionalFlipsIfFlip);
Tuttavia, questo cambiamento non sembra influire sulle prestazioni.
UPDATE
più sorprendente, la chiave per la velocità incredibile dell'algoritmo sembra essere che l'array Memoizzazione finisce piuttosto scarsa. Ad ogni livello di profondità, vi sono in genere 512 (a volte, 256 o 128) stati visitati (su 8192). Inoltre, è sempre uno stato per parità di colonne. Le parità di casella e riga non sembrano avere importanza! Omettendoli dall'array di memoizzazione, le prestazioni aumentano di 30 volte. Eppure, possiamo dimostrare che è sempre vero?
Penso che avrete bisogno di fornire molto più background in questa domanda. Di solito non è considerato un buon galateo per mandare persone ad altri siti Web e aspettarsi che digeriscano tutte le informazioni prima di rispondere. Riassumi il problema e cosa hai capito della soluzione fino ad ora? – templatetypedef
@templatetypedef Informazioni di background aggiunte – 1110101001
My two cents ': il codice collegato è scarsamente documentato e molto difficile da decifrare. Si prega di scrivere un codice migliore di quello! – templatetypedef