A * cerca Sudoku

0

Ho un problema di compiti a casa per un corso di Intelligenza Artificiale che ho difficoltà a rispondere.

Consider solving the Sudoku problem using A* search. The start state has some number of cells filled in, and the successors of each state are all legal ways an additional cell can be filled in. At any time we know exactly the number of cells that remain to filled.

Therefore, if K cells remain to be filled at node n, we know that h(n) = K. Thus if we set our heuristic function h(n) to be h(n)=K, we will have perfect heuristic knowledge in A.

Explain the mistake in the above statement.

Comprendo che questa euristica è del tutto inutile poiché se esistesse una funzione che potrebbe trovare successori legali, potresti anche eseguire una prima ricerca approfondita, ma cosa è esattamente sbagliato nell'asserzione precedente.

    
posta Shawn 02.10.2013 - 16:29
fonte

3 risposte

4

Questa non è una risposta, ma è troppo lunga per un commento ...

Usando la metrica della distanza rimanente, puoi certamente implementare una ricerca A * e darà il risultato corretto, ma sarà estremamente inefficiente. Il motivo è che è davvero una ricerca Dijkstra mascherata da A *. Peggio ancora, come osserva Shawn, è davvero una semplice ricerca in ampiezza.

Il motivo per cui è decaduto a Dijkstra è perché la tua metrica non fornisce indizi su quale sia la direzione migliore per passare attraverso lo spazio dello stato. Ogni passaggio da un determinato stato intermedio consiste semplicemente nel riempire una cifra in una cella - precisamente come economico / costoso come il riempimento di qualsiasi altra cifra / cella possibile in quel punto e senza alcun indizio su quale stato successore (con lo stesso numero di vuoto celle) sono più vicini a una soluzione corretta . Tutti i percorsi da quello stato intermedio alla soluzione sono della stessa lunghezza, compresi quelli che conducono attraverso stati illegali a una soluzione rotta.

Questo è legale nel senso che la metrica di distanza è un limite inferiore alla distanza rimanente da una soluzione. Ma non è solo un limite inferiore, è una distanza esatta. La tua "euristica perfetta" non sta guidando la ricerca verso la soluzione in alcun modo utile al di là di ciò che potrebbe fare Dijkstra.

Il motivo per cui è decaduto in una ricerca in ampiezza è la stessa cosa, ma in termini di pesi di spigoli già attraversati finora. Ogni percorso dall'inizio ad uno stato intermedio ha lo stesso numero di spigoli e lo stesso costo totale (lo stesso numero di celle riempite). Ogni edge ha effettivamente il peso uno e non ci sono scorciatoie da sfruttare per Dijkstra.

In pratica, i solutori di Sodoku di solito usano la ricerca di profondità a ritroso con controlli relativamente economici (se ci sono due delle stesse cifre in ogni cella, riga o blocco, questo stato è impossibile come lo sono tutti i possibili stati successivi) per evitare la ricerca parti impossibili dello spazio di ricerca. Non ci sono molte indicazioni su quali stati intermedi siano migliori senza spendere di più sull'euristica e sull'algoritmo di ricerca di quanto si ottiene potando ulteriormente l'albero di ricerca, e inoltre, il backtracking della ricerca con quella semplice potatura è molto veloce.

    
risposta data 02.10.2013 - 17:50
fonte
2

Il "successore legale" non è lo stesso di "successore valido". Per esempio. se una singola cella può contenere N numeri, in base allo stato corrente del campo, allora ognuno di essi è "successore legale". Ma solo uno di essi è "valido successore" (supponendo che abbia una sola soluzione).

Ma non sono d'accordo sul fatto che descriva il numero di celle non riempite come euristica perfetta. Ma questo è solo il mio sentimento.

E non dovresti chiederlo a questo tuo professore?

    
risposta data 02.10.2013 - 16:45
fonte
1

Questo non sembra corretto:

Therefore, if K cells remain to be filled at node n, we know that h(n) = K.

Non sappiamo che h(n) = K a meno che non sappiamo che il puzzle è risolvibile dal nodo n .

    
risposta data 02.10.2013 - 18:23
fonte

Leggi altre domande sui tag