Profondeur d'Abord de recherche en Python

Je suis en train de faire une Profondeur d'Abord de recherche en Python, mais il ne fonctionne pas.

Fondamentalement, nous avons un peg solitaire conseil:

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

1 représente une cible, et 0 est un endroit ouvert. Vous devez déplacer un pion, un à un, DEUX FENTES vers l'arrière ou vers l'avant qu'à un endroit vide. Si vous sautez sur l'autre cheville dans le processus, il devient un logement vide. Vous faites cela jusqu'à ce qu'un peg 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:

Est-ce la bonne façon de faire de la Profondeur d'Abord rechercher ce?
Mon algorithme ne fonctionne pas!!! Ça coince. J'ai eu du mal sur ce pendant des jours avant de demander ici, donc s'il vous plaît aider.
On dirait que je ne suis pas suite à SEC, des suggestions?
omg m'aider?

OriginalL'auteur y2k | 2010-01-26

depth-first-search python

9

La voie normale de l'œuvre DFS dans une situation où chaque étape est un "déplacement" d'un "conseil d'administration" à une possible prochaine, jusqu'à ce qu'un objectif est atteint, est comme suit (pseudo-code)
```
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 avez sans doute aussi envie de garder les liens en arrière pour être en mesure d'émettre, à la fin, la série de mouvements, conduisant à la solution trouvée (le cas échéant), mais c'est un accessoire du problème.

Je ne reconnais pas une trace de cette structure générale (ou raisonnable variante de celui-ci) dans votre code. Pourquoi ne pas essayer de l'enregistrer de cette façon? Vous avez seulement besoin de code possiblesuccessors et isending (si vous insistez sur le maintien d'une position de la liste, vous aurez à tourner dans un tuple de vérifier l'adhésion et d'ajouter à l'ensemble, mais c'est assez mineur;-).

Ça a l'air bon. Mais alors vous êtes plus qu'à une étape de l'algorithme A* qui converger plus rapidement. Tous vous avez besoin est une heuristique sur la "distance" de gauche " (c'est à dire. nombre de mouvements) de l'objectif. On dirait que cette heuristique peut être tout simplement le nombre de broches de gauche à renverser.
Ne devrait pas p être ajouté à seenpositions après l'ajout de p's successeurs de currentpositions?
yep, j'avais en effet oublié de mettre à jour seenpositions: tx pour le spotting -- édition maintenant pour corriger.

OriginalL'auteur Alex Martelli
1

Il n'apparaît pas que vous êtes en train de créer de nouveaux nœuds, tout simplement ré-utiliser celles existantes. DFS nécessite un certain type de pile (la pile d'appel, ou votre propre pile). Où est-ce?

oui il suppose l'utilisation d'un "rendement" de générateur ou de quelque chose, mais j'ai eu du mal avec cela, alors j'ai été en utilisant les rendements. Pouvez-vous l'aider à se diriger dans la bonne direction, puis, je suis tellement désespérément confus.

OriginalL'auteur Justin W
0

Bien, tout d'abord profondeur d'abord de recherche suppose un arbre. Maintenant, qui fait sens ici que vous disposez de plusieurs coups possibles dans la plupart des cas. Un parcours en profondeur d'abord de recherche serait tout simplement essayer de le premier mouvement possible, et puis le premier mouvement possible dans la nouvelle situation, et le premier mouvement possible dans cette nouvelle situation, jusqu'à ce que le succès ou pas plus de coups possibles, auquel cas il serait de retour jusqu'à ce qu'il détecte un mouvement, il n'a pas essayé, et descend de nouveau.

La "bonne" façon de le faire est avec la récursivité. Vous n'avez pas de récursivité dans votre système d'aussi loin que je peux voir.

Quelque chose de ce genre (pythonic pseudo 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
```
OriginalL'auteur Lennart Regebro
0

La base algorithmique problème est que le succ fonction ne produit que juste un mouvement possible pour un conseil d'état. Même si il n'y aurait plus d'un coups possibles, le succ fonction retourne le premier, il peut se trouver. Un parcours en profondeur d'abord de recherche a besoin pour traiter tous les mouvements possibles dans chaque état.

D'autres problèmes pourraient alors venir du fait que create_new_node, malgré son nom, n'a pas vraiment de créer un nouveau nœud, mais modifie l'existant. Pour la profondeur de recherche est l'endroit où vous voulez garder le nœud précédent autour, il serait mieux si cette fonction a effectivement créé une copie de la liste, il est comme un paramètre.

Aussi, lors de la vérification de la possibilité de retourner en arrière succ, vous essayez seulement de le faire si pos > 2. C'est trop restrictive, pos > 1 serait aussi ok.

OriginalL'auteur sth

Vous devez vous connecter pour publier un commentaire.