Depth-first search (non-recursive type) and lower limit pruning method (Python edition)

Continuing from previous, we implemented a depth-first search of the basic algorithm using the lower limit pruning method, using 8 puzzles as the theme.

procedure

  1. Generate a start puzzle
  2. Store the start puzzle on the stack
  3. Get the puzzle from the top of the stack
  4. Finish if the puzzle panel layout is the goal
  5. Create a new puzzle when you move the puzzle up / down / left / right except for the goal
  6. Check if the "Manhattan distance + history effort" in the panel layout of the puzzle is within the lower limit of 31
  7. If it is above the lower limit, repeat from 5 in the next direction.
  8. Check if the panel layout of the puzzle has already appeared and the history
  9. If it has appeared and the history of the puzzle is larger, repeat from 5 with a puzzle in another direction.
  10. Store the puzzle on the stack and store the history in the history list
  11. Repeat steps 5 to 10 for puzzles in each direction
  12. Continue from 3 to 11 until the stack is empty

point

--Use the stack --Speed up by pruning Manhattan distance

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
            #Calculate the difference in travel distance
            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)

            #Use Manhattan distance for lower pruning method
            #Check if the total of the current panel layout and history steps is within the maximum number of steps 31
            # -2 is the state of the start and goal panel layout_Subtract because it is included in list
            if new_puzzle.distance + len(new_puzzle.state_list) - 2 >= 31:
                continue

            #For panel arrangements that appeared in the past, compare the number of puzzles that hold the arrangement with the puzzle that is being checked.
            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()

reference

Algorithms with Python breadth-first search and iterative deepening

Recommended Posts

Depth-first search (non-recursive type) and lower limit pruning method (Python edition)
[Python] Depth-first search and breadth-first search
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Python 2 series and 3 series (Anaconda edition)
[Python] DFS (Depth-first Search) ATC001A
[Python] DFS (Depth-first Search) ABC157D
Tower of Hanoi-Recursive / Non-recursive (Python edition)
[python] week1-3: Number type and operation
Algorithm in Python (depth-first search, dfs)
Write a depth-first search in Python
[Python] Difference between function and method
Depth-first search using stack in Python
Python 2-minute search and its derivation