Sudoku Solver BackTracking vs Simulated Annealing

Naviga le tue risposte
2

Prima di leggere oltre, supponi di sapere quale gioco di sudoku e come risolverlo.

Quindi ho creato un risolutore di sudoku con forza bruta: L'algoritmo va come

  1. calcola (attraverso un semplice controllo delle regole) tutti i possibili valori di ogni cella vuota.
  2. Conta celle vuote
  3. Se una cella ha una sola possibilità, imposta il valore della cella e ricalcola tutte le possibilità
  4. conta nuovamente le celle vuote
  5. Se il vecchio numero di celle vuote < nuovo conteggio delle celle vuote, ripetere
  6. else apply bruteforce

Algoritmo della forza bruta
 1. (nidificato) per ogni cella si applica la prima possibilità
 2. Controllare isSolved se è vero? pausa: altrimenti applica la seconda possibilità e ripeti.

Sebbene l'algoritmo B.F. di cui sopra funzioni per problemi facili e medi, ma problemi difficili con molte possibilità per ogni cella, il programma si blocca a causa del ciclo annidato

Il mio algoritmo di backtracking utilizza lo stesso primo algo per restringere la ricerca, quindi

  1. imposta la prima possibilità per la prima cella vuota
  2. controlla se grid isValid == true; (se risolto quindi interrompi), altrimenti imposta la prima possibilità per la cella successiva, ripeti
  3. se grid isValid == false, torna alla cella precedente e imposta la prossima possibilità e continua

Ho applicato l'algoritmo BackTracking sulla griglia 6x6 e funziona, devo ancora applicarlo sulla griglia 9x9.

Algoritmo di Annealing simulato:

  1. imposta in modo casuale i valori di ogni cella vuota
  2. calcola il conteggio degli errori
  3. Genera una soluzione adiacente casuale e ri-conta gli errori
  4. se il nuovo numero di errori < vecchio conteggio degli errori: mantieni la nuova griglia, altrimenti mantieni la vecchia
  5. se la griglia viene risolta, quindi interrompere; altrimenti ripeti

Ora per le mie domande:

  1. Il mio algoritmo di annealing simulato è corretto?
  2. Ovviamente BackTracking risolverà il problema molto più velocemente di BruteForce, quanto più velocemente la ricottura simulata risolverà un problema? Dal momento che mescola in modo casuale, potrebbe richiedere più tempo per risolverlo rispetto a BackTracking.
  3. Come faccio a generare una soluzione adiacente casuale nel passaggio 3
posta j4rey 13.04.2016 - 07:27
fonte

1 risposta

2
  1. Is my simulated annealing algorithm correct?

Questo non è Ricottura simulata , ciò che descrivi è chiamato Stochastic Hill Climbing . SA accetterà anche nuove configurazioni con una certa probabilità quando sono peggiori rispetto alla vecchia configurazione (e diminuiscono quella probabilità nel tempo). Non hai specificato come calcoli esattamente il "conteggio degli errori" e, come hai già detto, il modo in cui produci "soluzioni vicine". Dipenderà da questi dettagli se un algoritmo non deterministico rimarrà bloccato in un minimo locale (il che significa che non produrrà una soluzione con il conteggio degli errori 0). Nota che anche quando implementi un algoritmo SA corretto, non c'è alcuna garanzia che troverà un optimum globale, che è probabilmente quello che stai cercando qui.

  1. Obviously BackTracking will solve the problem much faster than BruteForce, How much faster will Simulated Annealing solve a problem?

Dipende dall'attuale implementazione di entrambi e dall'impegno di ottimizzazione che investi in ciascuna implementazione. Tuttavia, un vero algoritmo SA ha bisogno di specificare una "temperatura iniziale" e una velocità di "raffreddamento", e se si specificano questi parametri errati, si finisce con un algoritmo molto lento o con un algoritmo che non trova una soluzione affatto. Molto probabilmente "Hill Climbing" ti darà il secondo.

  1. How do I generate random neighboring solution in step 3

Puoi provare diverse cose, ma un semplice approccio sarebbe probabilmente quello di modificare una cella e scambiare un numero con un altro. Un altro approccio semplice consiste nel distribuire ogni cifra da 1 a 9 esattamente 9 volte nella griglia, quindi scambiare il contenuto della cella in modo casuale.

Controlla anche la mia risposta su questa vecchia domanda SO .

    
risposta data 13.04.2016 - 07:54
fonte

Leggi altre domande sui tag

Scrittura di casi di test automatizzati per una classe di archiviazione di cartelle. Test delle proprietà con setter privati