Perché l'euristica è uno svantaggio per i problemi decidibili?

Question

Perché l'euristica è uno svantaggio per i problemi decidibili?

#1 da (3 voti)

2

Sto leggendo Introduzione all'intelligenza artificiale di Ertel.

Questa riga mi ha fatto uscire dal libro di testo (pagina 102):

For decidable problems such as the 8-puzzle this means that the whole search tree must be traversed up to a maximal depth whether a heuristic is being used or not.

E decidibile può essere definito così:

an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely)

Perché il programma non può tornare se incontra lo stato obiettivo prima che abbia attraversato l'intero albero? Cosa mi manca?

Nel caso in cui il contesto sia importante, questa è la frase precedente:

In closing, it remains to note that heuristics have no performance advantage for unsolvable problems because the unsolvability of a problem can only be established when the complete tree has been searched through.

Vedi pagina 102 .

Si dice altrove nel libro che l'euristica spesso riduce drasticamente il calcolo per "problemi risolvibili"! C'è una differenza tra i problemi "decidibile" e "risolvibile" che è rilevante qui? Non è spiegato perché l'euristica è buona per i problemi "risolvibili" e cattivi per quelli "decidibili".

artificial-intelligence search trees heuristics

posta nullpointer 15.02.2015 - 23:52

fonte

1 risposta

Leggi altre domande sui tag artificial-intelligence search trees heuristics

Consenti all'utente di inserire DSL, regole o codice? Problema di programmazione dinamica - Per trovare il numero intero più piccolo 'x' che contiene solo le cifre 1 e 0 in modo che x mod n = 0

score 3 · Accepted Answer

Un problema è risolvibile se esiste una soluzione.
Un problema è decidibile se possiamo dire se il problema è risolvibile o meno, cioè se esiste una soluzione.

L'8-puzzle non è sempre risolvibile, ma è decidibile in quanto se esiste una soluzione, sappiamo che ci vorranno al massimo 31 mosse a tessera singola. Quindi, per decidere se un dato 8-puzzle è risolvibile, dobbiamo trovare una soluzione. Se nessuna sequenza di mosse con una lunghezza massima di 31 risolve il problema, sappiamo che questo puzzle è irrisolvibile.

Ora possiamo ribadirlo in termini di risolvibilità del problema:

Per un problema risolvibile, abbiamo solo bisogno di trovare una soluzione per dimostrare che è risolvibile. Qui, l'euristica può accelerare la ricerca di una soluzione.
Per un problema irrisolvibile, dobbiamo dimostrare che non esiste un'unica soluzione. Dal momento che un'euristica non porterà a una soluzione per un problema irrisolvibile, dobbiamo esaminare l'intero albero del gioco per essere sicuri che non contenga soluzioni. Dal momento che dobbiamo investigare su ogni possibile stato di gioco, un'euristica non conta (tutto ciò che un euristico fa è dare priorità a mosse promettenti). Dal momento che un euristico aggiunge un costo computazionale, l'utilizzo di un'euristica sarà una perdita netta per problemi irrisolvibili.

La cosa divertente è che generalmente non sappiamo a priori se un dato problema sia risolvibile.

Modifica: questo commento di un altro utente (@esoterico) aggiunge ulteriore chiarezza:

Try thinking of it as a statement of what happens in the worst case, especially given that half of the initial positions are unsolvable, and viewing the opportunity for early termination as a happy accident. Consider also that if the traversal is unlucky, it still may be required to walk the entire tree before finding a solution even if the instance is solvable. So, for > 50% of all instances, a full traversal is required. Given that, it's reasonable for the algorithm to expect to have to traverse the entire tree.