[GO] Suche nach Breitenpriorität / bidirektionale Suche (Python Edition)

Implementierung der Breitenprioritätssuche und bidirektionalen Suche des Basisalgorithmus basierend auf 8 Rätseln

Suche nach Breitenpriorität

Verfahren

1. Generieren Sie ein Starträtsel
2. Stellen Sie das Starträtsel in die Warteschlange
3. Holen Sie sich das Puzzle vom Anfang der Warteschlange
4. Erstellen Sie ein neues Puzzle, wenn Sie das Puzzle nach oben, unten, links und rechts bewegen
5. Wenn das Panel-Layout des Puzzles das Ziel ist, endet es
6. Überprüfen Sie, ob das Panel-Layout des Puzzles angezeigt wurde
7. Wenn es bereits erschienen ist, wiederholen Sie ab 5 für das Rätsel in die nächste Richtung
8. Speichern Sie das Puzzle in der Warteschlange, falls es noch nicht angezeigt wurde
9. Wiederholen Sie die Schritte 5 bis 8 für Rätsel in jede Richtung
10. Fahren Sie von 3 bis 9 fort, bis die Warteschlange leer ist

Punkt

• Zeichnen Sie das bereits angezeigte Bedienfeldlayout auf
• Behalten Sie das Panel-Layout bei, das Sie im Puzzle-Objekt durchlaufen haben

class Queue:
    '''
Warteschlangenklasse zum Speichern von Puzzleobjekten
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)
    
    #Puzzle am Ende der Liste hinzufügen
    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    #Holen Sie sich das Puzzle von der Spitze der Liste
    def dequeue(self):
        return self.puzzle_list.pop(0)

    #Überprüfen Sie, ob die Puzzle-Liste leer ist
    def is_empty(self):
        return len(self.puzzle_list) == 0


class Puzzle:
    '''
Eine Puzzle-Klasse mit dem aktuellen Panel-Layout, einer Liste der aktivierten Panel-Layouts und der Größe des Puzzles.
    '''
    def __init__(self, panel_list, state_list, size):
        self.panel_list = panel_list

        #Eine Liste, die den Status der Panel-Anordnung enthält, die Sie durchlaufen haben
        self.state_list = state_list
        self.state_list.append(panel_list)

        self.size = size

    #Generator, der das Panel-Layout zurückgibt, wenn 0 auf dem Panel nach links, rechts, oben und unten verschoben wird
    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

            #Notieren Sie das bereits angezeigte Bedienfeldlayout
            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()

Bidirektionale Suche

Verfahren

1. Generieren Sie ein Starträtsel
2. Stellen Sie das Starträtsel in die Warteschlange
3. Generieren Sie ein Zielpuzzle
4. Das Zielpuzzle in die Warteschlange stellen
5. Holen Sie sich das Puzzle vom Anfang der Warteschlange
6. Erstellen Sie ein Bedienfeldlayout, wenn Sie das Puzzle nach oben, unten, links und rechts bewegen
7. Überprüfen Sie, ob das Bedienfeldlayout angezeigt wurde
8. Wenn es bereits angezeigt wurde, überprüfen Sie die Ausrichtung des Puzzles, das in der Vergangenheit das Bedienfeldlayout enthielt, und das zu überprüfende Puzzle.
9. Ziel, wenn die Rätsel nicht übereinstimmen
10. Speichern Sie das Puzzle in einem Bestätigungswörterbuch und in einer Warteschlange, falls es noch nicht angezeigt wurde
11. Führen Sie die Schritte 5 bis 8 für das generierte Bedienfeldlayout in jeder Richtung aus. 12.5 Fahren Sie von 5 bis 10 fort, bis die Warteschlange leer ist

Punkt

• Speichern Sie das Puzzle-Objekt im Bestätigungswörterbuch --Wenn in der Vergangenheit dasselbe Bedienfeldlayout angezeigt wurde, können Sie den Durchgangsdatensatz des Puzzleobjekts überprüfen, das dieses Bedienfeldlayout besaß.

class Queue:
    '''
Warteschlangenklasse zum Speichern von Puzzleobjekten
    '''
    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)
    
    #Puzzle am Ende der Liste hinzufügen
    def enqueue(self, puzzle):
        self.puzzle_list.append(puzzle)

    #Holen Sie sich das Puzzle von der Spitze der Liste
    def dequeue(self):
        return self.puzzle_list.pop(0)

    #Überprüfen Sie, ob die Puzzle-Liste leer ist
    def is_empty(self):
        return len(self.puzzle_list) == 0


class Puzzle:
    '''
Eine Puzzle-Klasse mit dem aktuellen Panel-Layout, einer Liste der aktivierten Panel-Layouts und der Größe des Puzzles.
    '''
    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)
                #Speichern Sie Rätsel in einem Bestätigungswörterbuch
                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()

Referenz

• Algorithmen mit Python / Breitenprioritätssuche und iterativer Vertiefung