Ricerca in profondità Basics

Question

Sto cercando di migliorare la mia attuale algoritmo per il problema 8 Queens, e questa è la prima volta che mi sono davvero fare con algoritmo di progettazione / algoritmi. Voglio realizzare una ricerca in profondità in combinazione con una permutazione dei diversi valori Y qui descritte: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

Ho implementato la parte permutazione di risolvere il problema, ma sto avendo un po 'di problemi confezionamento mia mente intorno alla ricerca in profondità. È descritto come un modo di attraversare l'albero / grafico, ma non genera il grafico albero? Sembra che l'unico modo che questo metodo sarebbe più efficace solo se la ricerca in profondità genera la struttura ad albero ad essere attraversato, implementando una logica per generare solo alcune parti dell'albero.

Quindi, in sostanza, avrei dovuto creare un algoritmo che ha generato un albero potato di permutazioni lexigraphic. Io so come implementare la logica di eliminazione, ma solo che non sono sicuro di come legarlo con il generatore di permutazione da quando sono con next_permutation.

C'è tutte le risorse che mi potrebbero aiutare con i principi fondamentali di profondità prime ricerche o la creazione di permutazioni lexigraphic in forma di albero?

Answer 1

In generale, sì, l'idea della ricerca in profondità prima è che non sarà necessario generare (o "visita" o "espandere") ogni nodo.

Nel caso del problema otto regine, se si inserisce una regina tale da poter attaccare un'altra regina, si può interrompere quel ramo; essa non può portare a una soluzione.

Se si stesse risolvendo una variante di otto regine in modo tale che il vostro obiettivo era quello di trovare una soluzione, non tutti 92, allora si potrebbe uscire appena trovato uno.

Più in generale, se si stesse risolvendo un problema meno discreti, come trovare la sistemazione "migliore" delle regine secondo una certa misura, allora si potrebbe interrompere un ramo non appena si sapeva che non poteva portare ad uno stato finale migliore rispetto uno stato finale che ci si già trovato su un altro ramo. Questo è legato alla A * algoritmo di ricerca .

Ancora più in generale, se si sta attaccando davvero un grosso problema (come gli scacchi), si può essere soddisfatto con una soluzione che non è esatto, in modo da poter interrompere un ramo che probabilmente non posso portare a una soluzione che hai già trovato.

Answer 2

L'algoritmo DFS per sé non genera l'albero / grafico. Se si vuole costruire l'albero e grafico, è così semplice la costruzione di come si esegue la ricerca. Se si desidera solo per trovare una soution, una struttura dati LIFO piatta come una lista concatenata sarà sufficiente per questo: quando si visita un nuovo nodo, aggiungere alla lista. Quando si lascia un nodo di fare marcia indietro nella ricerca, pop il nodo off.

Answer 3

Un libro intitolato "Introduzione agli algoritmi" di anany Levitan ha una spiegazione adeguata per la vostra comprensione. Ha anche fornito la soluzione al problema 8 regine solo il modo in cui si desctribed esso. Sarà helpyou di sicuro.

Come la mia comprensione, per la ricerca di una soluzione che non hanno bisogno di ogni permutazione tutto ciò che serve è dfs.That sarà sufficiente solo nella ricerca di soluzione