[GO] Recherche de priorité de profondeur (type non récursif) et méthode d'élagage de limite inférieure (édition Python)

Dans la continuité de Dernière fois, la recherche de priorité de profondeur de l'algorithme de base est implémentée en utilisant la méthode d'élagage de limite inférieure en utilisant 8 puzzles comme thème.

procédure

1. Générez un puzzle de départ
2. Stockez le puzzle de départ dans la pile
3. Récupérez le puzzle du haut de la pile
4. Terminez si la disposition des panneaux du puzzle est l'objectif
5. Créez un nouveau puzzle en déplaçant le puzzle vers le haut / le bas / la gauche / la droite sauf pour le but
6. Vérifiez si la "distance Manhattan + effort historique" dans la disposition du panneau du puzzle est dans la limite inférieure de 31
7. S'il est au-dessus de la limite inférieure, répétez à partir de 5 dans la direction suivante
8. Vérifiez si la disposition du panneau du puzzle est déjà apparue et l'historique
9. S'il est apparu et que l'histoire du puzzle est plus grande, répétez à partir de 5 avec un puzzle dans une autre direction.
10. Stockez le puzzle dans la pile et stockez l'historique dans la liste d'historique
11. Répétez les étapes 5 à 10 pour les puzzles dans chaque direction
12. Continuez de 3 à 11 jusqu'à ce que la pile soit vide

point

--Utiliser la pile

• Accélérez en élaguant la distance de Manhattan

class Stack:

    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)

    def push(self, puzzle):
        self.puzzle_list.insert(0, puzzle)

    def pop(self):
        return self.puzzle_list.pop(0)

    def is_empty(self):
        return len(self.puzzle_list) == 0

class Puzzle():

    def __init__(self, panel_list, state_list, size):
        self.panel_list = panel_list
        self.state_list = state_list
        self.state_list.append(panel_list)
        self.size = size
        self.distance = 0

        def manhattan():
            for d, panel in enumerate(self.panel_list):

                if panel > 0:
                    self.distance += abs((panel - 1) // 3 - d // 3 + (panel - 1) % 3 - d % 3)

        manhattan()

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

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

        def get_next_panel():
            panel_list = self.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            #Calculez la différence de distance parcourue
            self.distance += zero_pos // 3 - next_pos // 3 + zero_pos % 3 - next_pos % 3
            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 depth_first(panel_list, goal, size):
    puzzle = Puzzle(panel_list, [], size)
    stack = Stack(puzzle)
    checked_dict = {}
    cnt = 0

    while stack.is_empty() is False:
        next_puzzle = stack.pop()

        if next_panel.panel_list == goal:
            return next_puzzle

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

            #Utilisez la distance Manhattan pour une méthode de taille inférieure
            #Vérifiez si le total de la disposition actuelle du panneau et des étapes de l'historique se situe dans le nombre maximal d'étapes 31
            # -2 est l'état de la disposition du panneau de départ et d'objectif_Soustraire car il est inclus dans la liste
            if new_puzzle.distance + len(new_puzzle.state_list) - 2 >= 31:
                continue

            #Pour les agencements de panneaux apparus dans le passé, comparez le nombre d'énigmes contenant l'arrangement avec l'énigme en cours de vérification.
            if new_panel in checked_dict and len(new_puzzle.state_list) > checked_dict[new_panel]:
                continue

            checked_dict[new_panel] = len(new_puzzle.state_list)
            stack.push(new_puzzle)

    return False


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

    puzzle = depth_first(panel_list, goal, size)

    if puzzle is not False:
        puzzle.result_print()

référence

Algorithmes avec recherche de priorité de largeur Python et approfondissement itératif