Amplitud Primera búsqueda de un soldador de rompecabezas -- python campo con python-3.x campo con breadth-first-search campo con sliding-tile-puzzle camp codereview Relacionados El problema

Breadth First Search for a Slider Puzzle Solver


6
vote

problema

Español

Planeo implementar algunos otros solversos (profundidad de primera búsqueda, a *, etc.), por lo que estoy usando la clase de base abstracta (que es nueva para mí). Estoy usando Python 3.6, por lo que verás literales F-String. Apreciaría cualquier comentario positivo (¡YAY!) O, incluso más importante, las críticas constructivas (yay!).

  ?4  
Original en ingles

I plan to implement a few other solvers (depth first search, A*, etc), hence why I'm using the abstract base class (which is new to me). I'm using Python 3.6, so you'll see f-string literals. I would appreciate any positive feedback (yay!) or, even more importantly, constructive (yay!) criticism.

import abc from argparse import ArgumentParser from collections import deque from math import sqrt from resource import getrusage, RUSAGE_SELF from time import time  import numpy as np   class Board:     def __init__(self, tiles: str, hole: str = '0', sz: int = None):         board_ = tiles.split(',')         self._sz = sz or int(sqrt(len(board_)))         self._sorted_tokens = [str(x) for x in range(self._sz ** 2)]         self._goal = np.reshape(self._sorted_tokens, (self._sz, -1))         self._state = np.reshape(board_, (self._sz, -1))         self._hole = hole      def __repr__(self):         return str(self._state)      @property     def goal(self):         return ','.join(self._sorted_tokens)      @property     def string(self):         return self.stringify(self._state)      @property     def state(self):         return self._state      @staticmethod     def stringify(state):         return ','.join(state.flatten())      def hole_pos(self):         pos = np.where(self._state == self._hole)         return pos[0][0], pos[1][0]      def tile(self, pos):         if pos[0] < 0 or pos[1] < 0:             raise ValueError('Tile out of bounds!')         return self._state[pos]      def act(self, action):         hole = self.hole_pos()         lut = {             'Up': (hole[0] - 1, hole[1]),             'Down': (hole[0] + 1, hole[1]),             'Left': (hole[0], hole[1] - 1),             'Right': (hole[0], hole[1] + 1)         }         pos = lut[action]         board_ = self.swap(pos)         return board_      def actions(self):         """         find neighboring tiles to hole position         """         hole = self.hole_pos()         actions_ = []         if hole[0] - 1 >= 0:             actions_.append('Up')         if hole[0] + 1 < self._sz:             actions_.append('Down')         if hole[1] - 1 >= 0:             actions_.append('Left')         if hole[1] + 1 < self._sz:             actions_.append('Right')         return actions_      def swap(self, pos):         """         position is tuple (R,C) of neighboring tile to hole         """         try:             hole = self.hole_pos()             tile = self.tile(pos)             temp_state = self._state.copy()             temp_state[pos[0]][pos[1]] = self._hole             temp_state[hole[0]][hole[1]] = tile             return Board(self.stringify(temp_state),                          hole=self._hole,                          sz=self._sz)         except ValueError:             return None   class Node:     def __init__(self, state=None, action=None, path_cost=None, parent=None):         self._state = state         self._action = action         self._path_cost = path_cost         self._parent = parent      def __repr__(self):         return str({'state': self._state.state,                     'action': self._action,                     'path_cost': self._path_cost,                     'parent': self.parent})      def __iter__(self):         node = self         while node:             yield node             node = node._parent      @property     def state(self):         return self._state      @property     def action(self):         return self._action      @property     def path_cost(self):         return self._path_cost      @property     def parent(self):         return self._parent      @property     def depth(self):         return sum(1 for _ in self) - 1  # to account for 0 indexing   class Solver(metaclass=abc.ABCMeta):     def __init__(self, start_board: Board, depth: int = 4):         self._goal = start_board.goal         self._start_board = start_board         self._frontier = deque()         self._explored = set()         self._path_cost = 0         self._nodes_expanded = 0         self._fringe_sz = 0         self._max_fringe_sz = 0         self._search_depth = 0         self._max_search_depth = 0         self._running_time = 0         self._depth_limit = depth      @property     def nodes_expanded(self):         return self._nodes_expanded      @property     def fringe_size(self):         return self._fringe_sz      @property     def max_fringe_size(self):         return self._max_fringe_sz      @property     def search_depth(self):         return self._search_depth      @property     def max_search_depth(self):         return self._max_search_depth      @property     def running_time(self):         return self._running_time      def update_fringe_size(self):         self._fringe_sz = len(self._frontier)         if self._fringe_sz > self._max_fringe_sz:             self._max_fringe_sz = self._fringe_sz      @abc.abstractmethod     def solve(self):         """         To be implemented by detailed search strategies         """         return   class DFS(Solver):     def solve(self):         pass   class AST(Solver):     def solve(self):         pass   class IDA(Solver):     def solve(self):         pass   class BFS(Solver):     def solve(self):         start_time = time()         root = Node(state=self._start_board,                     path_cost=self._path_cost)         self._frontier.append(root)         if root.state.string == self._goal:             self._search_depth = root.depth             self._running_time = time() - start_time             return root         while True:             if len(self._frontier) == 0:                 self._running_time = time() - start_time                 raise ValueError('Goal not found.')             node = self._frontier.popleft()             if node.depth > self._depth_limit:                 raise RuntimeError             if node.state.string == self._goal:                 self.update_fringe_size()                 self._search_depth = node.depth                 self._running_time = time() - start_time                 return node             self._nodes_expanded += 1             self._explored.add(node.state.string)             actions = node.state.actions()             for action in actions:                 state = node.state.act(action)                 child = Node(state=state,                              action=action,                              path_cost=1,                              parent=node)                 if child.depth > self._max_search_depth:                     self._max_search_depth = child.depth                 if (child.state.string not in self._explored) and (child not in self._frontier):                     self._frontier.append(child)                     self.update_fringe_size()   class Summary:     def __init__(self, child: Node):         self._child = child      def path_cost(self):         return sum(n.path_cost for n in self._child)      def actions(self):         return list(reversed([n.action for n in self._child]))[1:]      def search_depth(self):         return self._child.depth   if __name__ == "__main__":     try:         parser = ArgumentParser()         parser.add_argument("solver", help="algorithm (bfs | dfs)")         parser.add_argument("board", help="board string (0,1,2,3...)")         args = parser.parse_args()         board = Board(tiles=args.board)         print("***STARTING STATE***")         print(board.state)         algorithms = {             'bfs': BFS(board, depth=100),             # 'dfs': DFS(board, depth=100),             # 'ast': BFS(board, depth=100),             # 'ida': BFS(board, depth=100)         }          search = algorithms[args.solver]         res = search.solve()         print("***SOLUTION STATE***")         print(res.state)         print(f"nodes expanded {search.nodes_expanded}")         summary = Summary(res)         print(f"path cost {summary.path_cost()}")         print(f"actions {summary.actions()}")         print(f"fringe size: {search.fringe_size}")         print(f"max_fringe_size: {search.max_fringe_size}")         print(f"search depth {search.search_depth}")         print(f"max search depth {search.max_search_depth}")         print(f"running time {search.running_time}")         print(f"memory usage {getrusage(RUSAGE_SELF)[2]}")     except TypeError as e:         print(e)         exit(1) 
           
 
 

Lista de respuestas

1
 
vote

Aquí hay una descripción general de alto nivel sin bucear en los detalles de la implementación:

  • El solve() de su clase no es legible y bastante larga: divídalo en múltiples métodos y / o agregue comentarios significativos
  • En general, el programa es largo: vea si puede dividirlo en múltiples módulos importables
  • También extrajo los "argumentos de lectura de la línea de comandos" y "Reportar los resultados" bloques de código en funciones separadas
  • El último conjunto de print() Las llamadas se pueden reemplazar con un solo 998877776665544333 Llamada y una cadena multi-líneas
  • El Solver se puede reescribir usando la attrs < / Código> Paquete Haciendo el código más legible Evitar las partes de la plantilla de la caldera
  • De acuerdo con la convencion de Docstring , debe iniciar su doctring con Una letra mayúscula y tiene un punto al final de las oraciones. Y, si un documento se adapta a una sola línea, definalo en una sola línea.
  • Perfil de memoria Su programa: podría ser que, cuando estés creando nuevas instancias , las instancias anteriores serán "colgantes" y no se recolectarán basura resultando en potenciales fugas de memoria
 

Here is a high-level overview without diving into the implementation details:

  • the solve() of your BFS class is not readable and quite lengthy - split it into multiple methods and/or add meaningful comments
  • overall the program is long - see if you can split it into multiple importable modules
  • I would also extract the "reading command-line arguments" and "reporting the results" code blocks into separate functions
  • the last set of print() calls can be replaced with a single print() call and a multi-line string
  • the Solver class may be rewritten using the attrs package making the code more readable avoiding the boilerplate parts
  • according to the Docstring Convention, you should start your docstring with a capital letter and have a dot at the end of sentences. And, if a docstring fits a single line, define it on a single line.
  • memory profile your program - it might be that, when you are creating new Board instances, the previous instances will be "hanging" and not garbage collected resulting into potential memory leaks
 
 

Relacionados problema

4  Rompecabezas de bloques deslizantes, A *  ( Sliding block puzzle a ) 
Soy un programador para principiantes y espero que alguien esté dispuesto a echar un vistazo a mi código y decirme cómo mejorar mi enfoque de estilo y desarro...

3  EJERCICIO SIMPLE QUE REPRESENTA UNA STIPMIENTO  ( Simple exercice representing a slidepuzzle ) 
He estado ayudando a un estudiante con un ejercicio, lo escribió rápidamente y pensé que sería la oportunidad ideal para mejorar mi propio estilo y enfoque de...

1  Resolviendo el algoritmo de 15 rompecabezas utilizando IDA * o A *  ( Solving 15 puzzle algorithm using ida or a ) 
Actualmente estoy usando el álgoritmo BESTFIRST para resolver el rompecabezas 15. Funciona bien cuando tengo insumos simples y tarda aproximadamente 1-20 segu...

4  Manhattan Distancia + Función de puntuación de conflictos lineales para soldado de rompecabezas de azulejos deslizantes  ( Manhattan distance linear conflicts scoring function for sliding tile puzzle s ) 
He escrito otro solucionador de N-Puzzle. Utilicé el algoritmo A * para buscar con la heurística de la distancia de Manhattan. Funcionó muy bien para el 9-rom...

6  15 Puzzle juego JavaScript  ( 15 puzzle game javascript ) 
He creado un programa que le permite jugar al juego de quince rompecabezas. Tienes que poner los bloques en orden ascendente moviéndolos al espacio abierto. M...

3  N-Puzzle en Clojescript  ( N puzzle in clojurescript ) 
Estoy en el proceso de crear un solucionador de N-Puzzle en Clojurescript. Tengo el modelo básico en funcionamiento y puedo mover las baldosas en la pantalla....

6  Una función que mueve un azulejo en el juego de quince  ( A function that moves a tile in the game of fifteen ) 
He creado una función que moverá un azulejo que un usuario especifica dentro de la placa de juego. El tablero de juego puede ser de 3 * 3 de hasta 9 * 9 y e...

5  Búsqueda de espacio estatal para rompecabezas de azulejos deslizantes  ( State space search for sliding tile puzzle ) 
Estoy trabajando en Búsqueda de espacio estatal (8 rompecabezas) en Python y cuando ejecuto mi programa con python3 -m profile , descubro que la mayor part...

5  Comparando los solversadores de rompecabezas en Java  ( Comparing puzzle solvers in java ) 
Tengo este programa que resuelve un $ (n ^ 2 - 1) $ - rompecabezas para el general $ n $. Tengo tres solucionadores: BidirectionalBFSPathFinder AS...

5  Mi solucionador de 15 rompecabezas es demasiado lento  ( My 15 puzzle solver is too slow ) 
Toma mi código más de 700 segundos para resolver un rompecabezas simple: 2 7 11 5 13 0 9 4 14 1 8 6 10 3 12 15 MI FUNCIÓN findSolution(puzzle...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos