Mise en œuvre de la recherche de priorité de largeur et de la recherche bidirectionnelle de l'algorithme de base basé sur 8 puzzles
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()
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()
Recommended Posts