[GO] Suche nach Tiefenpriorität (nicht rekursiver Typ) und Bereinigungsmethode für die untere Grenze (Python Edition)

Ausgehend von Letztes Mal wird die Suche nach Tiefenpriorität des Basisalgorithmus unter Verwendung der Methode zum Beschneiden der unteren Grenze unter Verwendung von 8 Rätseln als Thema implementiert.

Verfahren

1. Generieren Sie ein Starträtsel
2. Speichern Sie das Starträtsel im Stapel
3. Holen Sie sich das Puzzle von der Oberseite des Stapels
4. Beenden Sie, wenn das Panel-Layout des Puzzles das Ziel ist
5. Erstellen Sie ein neues Puzzle, wenn Sie das Puzzle mit Ausnahme des Ziels nach oben / unten / links / rechts bewegen
6. Überprüfen Sie, ob der "Manhattan-Abstand + Verlaufsaufwand" im Panel-Layout des Puzzles innerhalb der Untergrenze von 31 liegt
7. Wenn es über der Untergrenze liegt, wiederholen Sie von 5 in die nächste Richtung
8. Überprüfen Sie, ob das Panel-Layout des Puzzles bereits angezeigt wurde und der Verlauf
9. Wenn es erschienen ist und die Geschichte des Puzzles größer ist, wiederholen Sie von 5 mit einem Puzzle in eine andere Richtung.
10. Speichern Sie das Puzzle im Stapel und speichern Sie den Verlauf in der Verlaufsliste
11. Wiederholen Sie die Schritte 5 bis 10 für Rätsel in jede Richtung
12. Fahren Sie von 3 bis 11 fort, bis der Stapel leer ist

Punkt

• Stapel verwenden
• Hohe Geschwindigkeit durch Beschneiden der Entfernung nach 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
            #Berechnen Sie den Unterschied in der Fahrstrecke
            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)

            #Verwenden Sie den Manhattan-Abstand für eine niedrigere Schnittmethode
            #Überprüfen Sie, ob die Summe der aktuellen Panel-Layout- und Verlaufsschritte innerhalb der maximalen Anzahl von Schritten 31 liegt
            # -2 ist der Status des Start- und Zielfeldlayouts_Subtrahieren, weil es in der Liste enthalten ist
            if new_puzzle.distance + len(new_puzzle.state_list) - 2 >= 31:
                continue

            #Vergleichen Sie bei einem Panel-Layout, das in der Vergangenheit angezeigt wurde, die Anzahl der Puzzles, die das Layout enthalten, mit dem Puzzle, das überprüft wird.
            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()

Referenz

Algorithmen mit Python-Breitenprioritätssuche und iterativer Vertiefung