Profondità-prima ricerca in Python

Question

Sto cercando di fare una visita in profondità di ricerca in Python, ma non sta funzionando.

In sostanza abbiamo un piolo bordo-solitaire:

[1,1,1,1,1,0,1,1,1,1]

1 di rappresentare un piolo, e 0 è un posto aperto. È necessario spostare un piolo uno alla volta due slot indietro o solo in avanti ad un punto vuoto. Se si salta su un altro piolo nel processo diventa uno slot vuoto. A tale scopo, fino a quando uno piolo rimane. Quindi, fondamentalmente, un gioco va come:

[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left

Ecco quello che ho:

class MiniPeg():
    def start(self):
        ''' returns the starting board '''
        board = [1,1,1,1,1,0,1,1,1,1]
        return board

    def goal(self, node):
        pegs = 0

        for pos in node:
            if pos == 1:
                pegs += 1

        return (pegs == 1) # returns True if there is only 1 peg

    def succ(self, node):
        pos = 0
        for peg in node:
            if peg == 1:                
                if pos < (len(node) - 2):  # try to go forward
                    if node[pos+2] == 0 and node[pos+1] == 1:
                        return create_new_node(node, pos, pos+2)

                if pos > 2: # try to go backwards 
                    if node[pos-2] == 0 and node[pos-1] == 1:
                        return create_new_node(node, pos, pos-2)
        pos += 1

def create_new_node(node, fr, to):
    node[fr] = 0
    node[to] = 1
    if fr > to:
        node[fr-1] = 0
    else:
        node[fr+1] = 0
    return node

if __name__ == "__main__":
    s = MiniPeg()
    b = s.start()

    while not s.goal(b):
        print b
        b = s.succ(b)

Così, ora le mie domande:

1. E 'questo il modo giusto di fare una visita in profondità di ricerca per questo?
2. Il mio algoritmo non funziona !!! E si blocca. Ho lottato su questo per giorni prima di chiedere qui quindi per favore aiuto.
3. Sembra che io non sto seguendo SECCO, qualche suggerimento?
4. omg mi aiuta?

Answer 1

Il modo normale per implementare DFS in una situazione in cui ogni passo è una "mossa" da una "posizione di bordo" per qualche possibile successivo, fino al raggiungimento di un obiettivo, è il seguente (pseudocodice)

seenpositions = set()
currentpositions = set([startingposition])
while currentpositions:
  nextpositions = set()
  for p in currentpositions:
    seenpositions.add(p)
    succ = possiblesuccessors(p)
    for np in succ:
      if np in seenpositions: continue
      if isending(np): raise FoundSolution(np)
      nextpositions.add(np)
  currentpositions = nextpositions
raise NoSolutionExists()

Probabilmente anche desidera mantenere i collegamenti a rovescio per essere in grado di emettere, alla fine, la serie di mosse che portano alla soluzione trovata (se esiste), ma questo è un problema di accessorio.

Non riconosco una traccia di questa struttura generale (o variante ragionevole della stessa) nel codice. Perché non provare a registrare in questo modo? Hai solo bisogno di codificare possiblesuccessors e isending. (Se ti ostini a mantenere una posizione come una lista dovrete trasformarlo in una tupla per controllare l'appartenenza set e aggiungere per impostare, ma, questo è piuttosto minore; -)

Answer 2

Non sembra che si sta creando nuovi nodi, semplicemente riutilizzando quelli esistenti. DFS richiede un certo tipo di pila (o lo stack di chiamate, o il proprio stack). Dove si trova?

Answer 3

Bene, prima di tutto una ricerca in profondità assume un albero. Ora, che ha un senso qui come si dispone di diversi possibili mosse nella maggior parte dei casi. Una profondità di prima ricerca sarebbe semplicemente provare la prima mossa possibile, e poi la prima mossa possibile nella nuova situazione, e la prima mossa possibile in quella nuova situazione, fino a quando il successo o non più possibili mosse, nel qual caso sarebbe il backup fino trova una mossa che non ha provato, e scendere di nuovo.

Il modo "corretto" di fare che è con la ricorsione. Non hai la ricorsione nel vostro sistema, per quanto posso vedere.

Qualcosa di simile potrebbe funzionare (divinatorio pseudo codeish inglese):

def try_next_move(self, board):
    for each of the pegs in the board:
        if the peg can be moved:
            new_board = board with the peg moved
            if new_board is solved:
                return True
            if self.try_next_move(new_board):
                return True
            # That move didn't lead to a solution. Try the next.
    # No move  worked.
    return False

Answer 4

Il problema algoritmico di base è che la funzione succ sempre produce solo un unico movimento possibile per un dato stato bordo. Anche se ci sarebbe più di un possibili mosse, la funzione succ restituisce solo il primo che riesce a trovare. Una ricerca in profondità ha bisogno di elaborare tutte le possibili mosse in ogni stato.

Ulteriori problemi potrebbero poi venire dal fatto che create_new_node, nonostante il suo nome, in realtà non crea un nuovo nodo, ma modifica quello esistente. Per ricerca in profondità in cui si desidera mantenere il nodo precedente intorno sarebbe meglio se questa funzione in realtà creato una copia della lista che ottiene di come parametro.

Inoltre, quando si verifica la possibilità di andare a ritroso nel succ, si tenta solo di farlo se pos > 2. Questo è troppo restrittiva, pos > 1 sarebbe anche OK.