Quindi almeno due professori hanno detto che il backtracking rende un algoritmo non deterministico senza dare troppe spiegazioni sul perché. I penso Capisco come succede, ma ho difficoltà a metterlo in parole. Qualcuno potrebbe darmi una spiegazione concisa del motivo di ciò?Perché il backtracking rende un algoritmo non deterministico?
Non è tanto il backtracking che rende un algoritmo non deterministico.
Piuttosto, di solito è necessario eseguire il backtrack per elaborare un algoritmo non deterministico, poiché (con la definizione di non deterministico) non si conosce il percorso da eseguire in un determinato momento del processo, ma è necessario provare parecchi.
mi limiterò a citare Wikipedia:
Un linguaggio di programmazione non deterministica è una lingua che può specificare, in certi punti del programma (chiamati "punti di scelta"), varie alternative per il flusso del programma. A differenza di un'istruzione if-then, il metodo di scelta tra queste alternative non è specificato direttamente dal programmatore; il programma deve decidere in fase di esecuzione tra le alternative, tramite un metodo generale applicato a tutti i punti di scelta. Un programmatore specifica un numero limitato di alternative, ma in seguito il programma deve scegliere tra di esse. ("Scegli" è, di fatto, un nome tipico per l'operatore non deterministico.) Può essere formata una gerarchia di punti di scelta, con scelte di livello superiore che portano a rami che contengono scelte di livello inferiore al loro interno.
Un metodo di scelta è incorporato nei sistemi di backtracking, in cui alcune alternative possono "fallire", causando il backtrack del programma e provare altre alternative. Se tutte le alternative falliscono in un particolare punto di scelta, allora un intero ramo fallisce, e il programma tornerà indietro, verso un punto di scelta più vecchio. Una complicazione è che, poiché ogni scelta è provvisoria e può essere rifatta, il sistema deve essere in grado di ripristinare i vecchi stati del programma annullando gli effetti collaterali causati dall'esecuzione parziale di un ramo che alla fine non ha funzionato.
Su Nondeterministic Programming articolo.
Congrats. Una risposta "leggi wikipedia" che non mi ha fatto sentire totalmente stupido. :-) –
che non rende il sistema indeterminato, andrei con la risposta di Mark Harrison: è un modo per simulare una macchina (non teorica) non deterministica. – hasen
hasen j, che sistema vuoi dire? il backtracking ovviamente può solo simulare il non-determinismo, a patto che funzioni su un computer deterministico. un primo esempio è una libreria di espressioni regolari. essi prendono una descrizione non deterministica e devono trasformarli in macchine a stati deterministici. –
Considera un algoritmo per colorare una mappa del mondo. Nessun colore può essere utilizzato nei paesi adiacenti. L'algoritmo inizia arbitrariamente in un paese e lo colora di un colore arbitrario. Quindi si muove, colorando paesi, cambiando il colore in ogni passaggio fino a quando, "uh oh", due paesi adiacenti hanno lo stesso colore. Bene, ora dobbiamo tornare indietro e fare una nuova scelta di colori. Ora non stiamo facendo una scelta come farebbe un algoritmo non deterministico, non è possibile per i nostri computer deterministici. Invece, stiamo simulando l'algoritmo non deterministico con il backtracking. Un algoritmo non deterministico avrebbe fatto la scelta giusta per ogni paese.
vedi i miei commenti sulla risposta di litb – hasen
esperimento mentale:
1) Nascosto alla vista v'è una certa distribuzione delle cariche elettriche che si sente una forza da e si misura il campo potenziale che creano. Dimmi esattamente le posizioni di tutte le accuse.
2) Prendere alcune spese e organizzarle. Dimmi esattamente il potenziale campo che creano.
Solo la seconda domanda ha una risposta univoca. Questa è la non unicità di vector fields. Questa situazione potrebbe essere in analogia con alcuni algoritmi non deterministici che stai considerando. Ulteriore considerazione in math limits che non esistono perché hanno risposte diverse a seconda di quale direzione si avvicina a una discontinuità.
Se si consente il backtracking, si consente il loop infinito nel programma che lo rende non deterministico poiché il percorso effettivo può sempre includere un altro ciclo.
-1, cosa ha a che fare il ciclo infinito con il determinismo ?? – hasen
Le macchine di turing non deterministiche (NDTM) possono eseguire più rami in un unico passaggio. D'altra parte, i DTM seguono un processo trial-and-error.
Si può pensare ai DTM come normali computer. Al contrario, i computer quantici sono simili ai NDTM e possono risolvere problemi non deterministici molto più facilmente (ad esempio vedere la loro applicazione in violazione della crittografia). Quindi il backtracking sarebbe in realtà un processo lineare per loro.
Il tempo di esecuzione del backtracking su un computer deterministico è fattoriale, cioè è in O (n!).
Dove un computer non deterministico può immediatamente indovinare correttamente in ogni passaggio, un computer deterministico deve provare tutte le possibili combinazioni di scelte.
Dal momento che è impossibile costruire un computer non-deterministico, che cosa il vostro professore, probabilmente voleva dire è la seguente:
Un provenly hard problema nella classe di complessità NP (tutti i problemi che un computer non-deterministico in grado di risolvere in modo efficiente sempre indovinando correttamente) non può essere risolto in modo più efficiente su computer reali che con il backtracking.
L'affermazione precedente è vera, se le classi di complessità P (tutti i problemi che un computer deterministico può risolvere efficientemente) e NP non sono gli stessi. Questo è il famoso problema P vs. NP. Il Clay Mathematics Institute ha offerto un premio di $ 1 milione per la sua soluzione, ma il problema ha resistito alla prova per molti anni. Tuttavia, la maggior parte dei ricercatori ritiene che P non sia uguale a NP.
Un modo semplice per riassumere sarebbe: Problemi più interessanti di un computer non-deterministico potrebbe risolvere in modo efficiente da sempre indovinare correttamente, sono così forte che un computer deterministico sarebbe probabilmente necessario provare tutte le possibili combinazioni di scelte, vale a dire l'uso backtracking.
Modificato per notare che gli algoritmi sono fattoriali anziché esponenziali. –
In termini di classi di complessità sono esponenziali (ad esempio EXPTIME). Inoltre, la maggior parte dei problemi di O (n!) Può essere risolta in O (N^2 * 2^N) usando la programmazione dinamica. Ma se trovi più facile capire, allora va bene per me. – mdm
Ho scritto un labirinto che utilizza il backtracking (ovviamente), che userò come esempio.
Cammini attraverso il labirinto. Quando raggiungi un incrocio, lancia una moneta per decidere quale rotta seguire. Se hai scelto un vicolo cieco, risalire verso l'incrocio e prendere un'altra strada. Se li hai provati tutti, torna allo svincolo precedente. Questo algoritmo non è deterministico, non a causa del backtracking, ma a causa del lancio della moneta.
Ora modifica l'algoritmo: quando raggiungi un incrocio, prova sempre il percorso più a sinistra che non hai ancora provato. Se questo porta a un vicolo cieco, torna al bivio e prova ancora il percorso più a sinistra che non hai ancora provato. Questo algoritmo è deterministico. Non c'è nessuna possibilità, è prevedibile: seguirai sempre la stessa strada nello stesso labirinto.
Mi piace l'analogia del labirinto. Pensiamo al labirinto, per semplicità, come a un albero binario, in cui c'è solo un percorso.
Ora si desidera provare prima una ricerca di profondità per trovare l'uscita corretta dal labirinto.
Un computer non deterministico, in ogni punto di diramazione, duplica/clona se stesso ed esegue ogni ulteriore calcolo in parallelo.È come se la persona nel labirinto duplicasse/cloni se stesso (come nel film Prestige) ad ogni punto di ramificazione e mandi una copia di se stesso nel sottobosco sinistro dell'albero e l'altra copia di se stesso nel sottosuolo destro di l'albero.
I computer/le persone che finiscono in un vicolo cieco muoiono (terminano senza risposta).
Solo un computer sopravviverà (terminare con una risposta), quello che esce dal labirinto.
La differenza tra backtracking e non determinismo è la seguente.
In caso di backtracking c'è un solo computer vivo in un dato momento, fa il tradizionale trucco di labirinto, segna semplicemente il suo percorso con un gesso e quando finisce in un vicolo cieco semplicemente si dirige indietro verso una ramificazione punto le cui sottoflussi non ha ancora esplorato completamente, proprio come in una prima ricerca approfondita.
IN CONTRASTO:
un computer non deteministic può clonare se stesso in ogni punto ramificazione e controllare la via d'uscita eseguendo ricerche paralell nei rami secondari.
Quindi l'algoritmo di backtracking simula/emula la capacità di clonazione del computer non deterministico su un computer sequenziale/non parallelo/deterministico.
Il backtracking non rende un algoritmo non deterministico; per favore cambia la tua domanda. – ShreevatsaR
Buona domanda, mi stavo ponendo la stessa domanda quando guardavo questa video-conferenza: http://youtu.be/UBVcV3LIBeU – jhegedus