Recherche de priorité de largeur / recherche bidirectionnelle (édition Python)

Mise en œuvre de la recherche de priorité de largeur et de la recherche bidirectionnelle de l'algorithme de base basé sur 8 puzzles

Recherche de priorité de largeur

procédure

  1. Générez un puzzle de départ
  2. Mettez en file d'attente le puzzle de départ
  3. Récupérez le puzzle du début de la file d'attente
  4. Créez un nouveau puzzle en déplaçant le puzzle vers le haut, le bas, la gauche et la droite
  5. Si la disposition des panneaux du puzzle est l'objectif, il se termine
  6. Vérifiez si la disposition du panneau du puzzle est apparue
  7. S'il est déjà apparu, répétez à partir de 5 pour le mini-jeu dans la direction suivante
  8. Stockez le puzzle dans la file d'attente s'il n'est pas encore apparu
  9. Répétez les étapes 5 à 8 pour les puzzles dans chaque direction
  10. Continuez de 3 à 9 jusqu'à ce que la file d'attente soit vide

point

class Queue:
    '''
Classe de file d'attente pour stocker des objets de puzzle
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)
    
    #Ajouter un puzzle à la fin de la liste
    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    #Obtenez le puzzle du haut de la liste
    def dequeue(self):
        return self.puzzle_list.pop(0)

    #Vérifiez si la liste des puzzles est vide
    def is_empty(self):
        return len(self.puzzle_list) == 0


class Puzzle:
    '''
Une classe de puzzle avec la disposition actuelle du panneau, une liste des dispositions de panneau cochées et la taille du puzzle.
    '''
    def __init__(self, panel_list, state_list, size):
        self.panel_list = panel_list

        #Une liste qui contient l'état de la disposition des panneaux que vous avez traversée
        self.state_list = state_list
        self.state_list.append(panel_list)

        self.size = size

    #Générateur qui renvoie la disposition du panneau lorsque 0 sur le panneau est déplacé vers la gauche, la droite, le haut et le bas
    def gene_next_panel(self, puzzle):
        zero_pos = puzzle.panel_list.index(0)

        col = zero_pos // self.size
        raw = zero_pos % self.size

        def __get_next_panel():
            panel_list = puzzle.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            return panel_list

        if self.size > col + 1:
            next_pos = (col + 1) * self.size + raw
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if col - 1 >= 0:
            next_pos = (col - 1) * self.size + raw
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if self.size > raw + 1:
            next_pos = col * self.size + raw + 1
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if raw - 1 >= 0:
            next_pos = col * self.size + raw - 1
            panel_list = __get_next_panel()
            yield tuple(panel_list)

    def result_print(self):

        for s in self.state_list:
            print(s)

def breadth_first(size, goal, panel_list):
    puzzle = Puzzle(panel_list, [], size)
    queue = Queue(puzzle)
    checked_dict = {}

    while queue.is_empty() is False:
        puzzle = queue.dequeue()

        for next_panel in puzzle.gene_next_panel(puzzle):
            next_puzzle = Puzzle(list(next_panel), puzzle.state_list[:], size)

            if next_panel in checked_dict:
                continue

            if list(next_panel) == goal:
                return next_puzzle

            #Enregistrez la disposition du panneau qui est déjà apparue
            checked_dict[next_panel] = True
            queue.enqueue(next_puzzle)

if __name__ == '__main__':
    size = 3
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]

    puzzle = breadth_first(size, goal, panel_list)

    puzzle.result_print()

Recherche bidirectionnelle

procédure

  1. Générez un puzzle de départ
  2. Mettez en file d'attente le puzzle de départ
  3. Créez un puzzle d'objectifs
  4. Mettez en file d'attente le puzzle de l'objectif
  5. Récupérez le puzzle du début de la file d'attente
  6. Générer une disposition de panneau lors du déplacement du puzzle vers le haut, le bas, la gauche et la droite
  7. Vérifiez si la disposition du panneau est apparue
  8. S'il est déjà apparu, vérifiez l'orientation du puzzle qui contenait la disposition des panneaux dans le passé et le puzzle en cours de vérification.
  9. Objectif si les puzzles ne correspondent pas
  10. Stockez le puzzle dans un dictionnaire de confirmation et mettez-le en file d'attente s'il n'est pas encore apparu
  11. Exécutez les étapes 5 à 8 pour la disposition de panneau générée dans chaque direction. 12.5 Continuer de 5 à 10 jusqu'à ce que la file d'attente soit vide

point

class Queue:
    '''
Classe de file d'attente pour stocker des objets de puzzle
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)
    
    #Ajouter un puzzle à la fin de la liste
    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    #Obtenez le puzzle du haut de la liste
    def dequeue(self):
        return self.puzzle_list.pop(0)

    #Vérifiez si la liste des puzzles est vide
    def is_empty(self):
        return len(self.puzzle_list) == 0


class Puzzle:
    '''
Une classe de puzzle avec la disposition actuelle du panneau, une liste des dispositions de panneau cochées et la taille du puzzle.
    '''
    def __init__(self, panel_list, state_list, size, direction):
        self.panel_list = panel_list
        self.state_list = state_list
        self.state_list.append(panel_list)
        self.size = size
        self.direction = direction

    def gene_next_panel(self, puzzle):
        zero_pos = puzzle.panel_list.index(0)

        col = zero_pos // self.size
        raw = zero_pos % self.size

        def __get_next_panel():
            panel_list = puzzle.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            return panel_list

        if self.size > col + 1:
            next_pos = (col + 1) * self.size + raw
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if col - 1 >= 0:
            next_pos = (col - 1) * self.size + raw
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if self.size > raw + 1:
            next_pos = col * self.size + raw + 1
            panel_list = __get_next_panel()
            yield tuple(panel_list)

        if raw - 1 >= 0:
            next_pos = col * self.size + raw - 1
            panel_list = __get_next_panel()
            yield tuple(panel_list)

    def result_print(self):

        for s in self.state_list:
            print(s)

    def back_result_print(self):

        for s in self.state_list[::-1]:
            print(s)

def bidirectional_search(size, goal, panel_list):
    start_puzzle = Puzzle(panel_list, [], size, 'S')
    queue = Queue(start_puzzle)
    goal_puzzle = Puzzle(goal, [], size, 'G')
    queue.enqueue(goal_puzzle)

    checked_dict = {}
    checked_dict[tuple(panel_list)] = start_puzzle
    checked_dict[tuple(goal)] = goal_puzzle

    while queue.is_empty() is False:
        puzzle = queue.dequeue()

        for next_panel in puzzle.gene_next_panel(puzzle):

            if next_panel in checked_dict:
                checked_puzzle = checked_dict[next_panel]

                if checked_puzzle.direction != puzzle.direction:
                    return puzzle, checked_puzzle

            else:
                new_puzzle = Puzzle(list(next_panel), puzzle.state_list[:], size, puzzle.direction)
                #Stocker les puzzles dans un dictionnaire de confirmation
                checked_dict[next_panel] = new_puzzle
                queue.enqueue(new_puzzle)

if __name__ == '__main__':
    size = 3
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]

    front_puzzle, back_puzzle = bidirectional_search(size, goal, panel_list)

    front_puzzle.result_print()
    back_puzzle.back_result_print()

référence

Recommended Posts

Recherche de priorité de largeur / recherche bidirectionnelle (édition Python)
[Python] BFS (recherche de priorité de largeur) ABC168D
[Python] Recherche de priorité de profondeur et recherche de priorité de largeur
Algorithme en Python (recherche de priorité de largeur, bfs)
Recherche de priorité de largeur (BPF) Peut-être compris (python)
Maîtrisez la recherche linéaire! ~ Version d'implémentation Python ~
Version 64 bits de PYTHON2.7
Recherche séquentielle avec Python
[Python] Recherche (itertools) ABC167C
Dichotomie avec Python
[Python] Recherche (NumPy) ABC165C
Recherche de bisection (python2.7) mémo
[Python] Recherche de bisection ABC155D
recherche complète de bits python
Recherche linéaire en Python
Dichotomie avec python
Dichotomie avec Python 3
Rechercher sur Twitter avec Python
Recherche binaire en Python
Vérifier la version avec python
J'ai essayé d'implémenter la recherche de priorité de largeur avec python (file d'attente, dessin personnalisé)
Implémenter la recherche de priorité en profondeur (DFS) et la recherche de priorité de largeur (BFS) en python
Résolution avec Ruby et Python AtCoder ABC151 D Recherche de priorité de largeur
Algorithme de recherche utilisant word2vec [python]
Homebrew Python - Programme de recherche YouTube
[Python] DFS (recherche de priorité en profondeur) ATC001A
Changer la version de python à l'aide de pyenv
Mise à niveau de python Anaconda
Recherche binaire en Python / C ++
Algorithme en Python (dichotomie)
Recherche de bits complète avec Python
[Python] DFS (recherche de priorité en profondeur) ABC157D
la version de python ne change pas
Vérifiez la version OpenSSL de python 2.6
Introduction à Python (version Python APG4b)
Comment changer la version de Python
Trouver le diamètre du graphique par recherche de priorité de largeur (mémoire Python)
Les moteurs de recherche fonctionnent avec python
Rechercher des tweets Twitter avec Python
Spécifiez la version python avec virtualenv
Rationalisez la recherche Web avec Python
tesseract-OCR pour Python [version japonaise]
Vérification de la version de python de résolution d'erreur
[Python] Version Taple du menu déroulant de la préfecture
Résumé de la gestion des versions de l'environnement virtuel Python
Installez xgboost (version python) sur Windows
pyenv-changer la version python de virtualenv
Carte auto-organisée dans la version Python NumPy
Version Ideone> Python: 3.5 (au 29 août 2017)
Comment obtenir la version Python
Algorithme en Python (recherche de priorité en profondeur, dfs)
Écrire une recherche de priorité en profondeur en Python