Depth-Première recherche en Python

Question

J'essaie de faire une recherche en profondeur Python mais ça ne marche pas.

Fondamentalement, nous avons une carte de solitaire cheville:

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

1 Représentons une cheville, et 0 est un endroit ouvert. Vous devez déplacer une cheville une à la fois DEUX FENTES vers l'arrière ou vers l'avant UNIQUEMENT vers un endroit vide. Si vous sautez sur une autre cheville dans le processus, il devient un emplacement vide. Vous faites cela jusqu'à ce qu'une cheville reste. Donc, en gros, un jeu va comme:

[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 

Voici ce que j'ai:

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) 

Donc, maintenant mes questions:

1. Est-ce la bonne façon de faire de profondeur d'abord chercher ceci?
2. Mon algorithme ne fonctionne pas !!! Ça reste coincé. J'ai lutté sur cela pendant des jours avant de demander ici alors s'il vous plaît aider.
3. On dirait que je ne suis pas en train de suivre DRY, des suggestions?
4. omg m'aider?

Answer 1

La façon normale de mettre en œuvre DFS dans une situation où chaque étape est un « mouvement » d'une « position du conseil d'administration » une certaine possible prochaine un, jusqu'à ce qu'un but soit atteint, est la suivante (pseudocode)

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() 

Vous voulez sans doute aussi de garder les liens en arrière pour être en mesure d'émettre, à la fin, la série de mouvements menant à la solution trouvée (si any), mais c'est un problème accessoire.

Je ne reconnais pas une trace de cette structure générale (ou une variante raisonnable de celle-ci) dans votre code. Pourquoi ne pas essayer de l'enregistrer de cette façon? Vous n'avez besoin de coder que et isending (si vous insistez pour garder une position en tant que liste, vous devrez la convertir en un tuple pour vérifier l'appartenance à set et l'ajouter au set, mais c'est plutôt mineur ;-).

Answer 2

Il ne semble pas que vous créez de nouveaux nœuds, mais réutilisez simplement ceux qui existent déjà. DFS requiert une sorte de pile (soit la pile d'appel, soit votre propre pile). Où est-ce?

Answer 3

Eh bien, tout d'abord, une recherche en profondeur suppose un arbre. Maintenant, cela a du sens ici car vous avez plusieurs mouvements possibles dans la plupart des cas. Une première recherche de profondeur tenterait simplement le premier mouvement possible, puis le premier mouvement possible dans la nouvelle situation, et le premier mouvement possible dans cette nouvelle situation, jusqu'au succès ou pas plus de mouvements possibles, dans ce cas, il serait sauvegarder jusqu'à il trouve un mouvement qu'il n'a pas essayé, et redescend.

La façon "correcte" de le faire est avec la récursivité. Vous n'avez pas de récursion dans votre système pour autant que je puisse voir.

Quelque chose comme ça fonctionnerait (pythonique psuedo codeish anglais):

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

Le problème algorithmique de base est que la fonction succ ne produit toujours qu'un seul mouvement possible pour un état de carte donné. Même s'il y a plus d'un mouvement possible, la fonction succ renvoie juste la première qu'elle peut trouver.Une première recherche en profondeur doit traiter tous les mouvements possibles dans chaque état.

D'autres problèmes pourraient alors provenir du fait que create_new_node, malgré son nom, ne crée pas vraiment un nouveau nœud, mais modifie celui existant. Pour la première recherche de profondeur où vous voulez garder le nœud précédent autour de ce serait mieux si cette fonction a effectivement créé une copie de la liste qu'il obtient en tant que paramètre.

En outre, en vérifiant la possibilité de revenir en arrière dans succ, vous essayez seulement de le faire si pos > 2. C'est trop restrictif, pos > 1 serait aussi bien.