Puzzle Beam Search

Min N‐Puzzle aplicado al Warehouse 
Problem 
 
Laura Florian Cruz 
Fredy Carranza Athó 
 
Tópicos Especiales en Informática Teórica 
Escuela Académico Profesional de Informática 
Universidad Nacional de Trujillo 
Trujillo Perú  
2007 
 
Resumen.  En  el  siguiente  trabajo  presentaremos  la  solución  al 
WareHouse  Problem  a  través  de  su  reducción  al  N  Puzzle  Problem. Debemos  probar  antes  de  ello  su  posible  reducción  a  través  de 
pruebas  de  complejidad  computacional.  Obtenemos  la  solución  a 
través  de  algoritmos  de  búsqueda  heurística  y  búqueda  informada. 
Concluimos  en  una  posible  solución  al  problema  dado  los  algoritmos 
que proponen soluciones muy aproximadas. 
 
Introducción 
 
En  el  siguiente  documento  se presenta  el  problema  denominado  Warehouse  problem,  o 
problema  del  almacén.  El  problema  es  uno  de  los  más  comunes  en  el  mundo  comercial  en  la 
actualidad  debido  a  la  gran  demanda  de  un  orden  en  los  espacios  que  se  tienen,  y  tiempo  que 
apremia en las operaciones.  
 Ordenar los productos dentro de un almacén es un problema realmente difícil, ya que el espacio 
no  es  siempre  el  deseado  y  la  forma  de  plantear  el  uso  de  tiempo  y  recursos  físicos  mínimos  es 
más  frustrante  aún.  Sin  embargo,  en  el  siguiente  estudio  planteamos  una  forma  de  resolver  el 
problema  utilizando  una  generalización  de  otro  problema.  El  problema  Min  N  Puzzle.  Por  lo 
tanto  si  logramos  resolver  el  problema  del  Min  N  Puzzle,  lograremos resolver  el  Warehouse 
problem. 
 
Sin  embargo,  la  solución  para  un  número  muy  grande  de  entradas,  podría  tomar  demasiado 
tiempo  y  hasta  resultar  intratable.  Por  ello  la  solución  presentada  es  un  búsqueda  heurística 
denominada  Beam  Search,  que  permitirá  resolver  el  problema  con  una  solución  aproximada 
pero en un tiempo muy reducido. 
 1. Descripción del problema 
 
El  problema  de  N  puzzle  se  basa  en  el  juego  de  puzzle  o  rompecabezas,  que  posee  fichas 
ordenadas en forma de una matriz en un tablero. Todos los espacios de la matriz contienen una 
ficha,  a  excepto  de  uno  de  ellos.  Gracias  a  este  espacio  en  blanco  es  que  se  puede  movilizar  las 
fichas  contiguas.  El  objetivo  del  juego  es  tratar  de  llegar  a una  cierta  posición  de  las  fichas  en  el 
puzzle, comenzando con una posición determinada. Aquí una figura de cómo es el puzzle. 
 

11 

 
 
El  problema  MIN  N‐PUZZLE  es  encontrar  la  cantidad  de  movimientos  mínima  para  lograr 
llegar a la configuración deseada a través de jugadas en el tablero. 
 
Para  llegar  a  aplicarlo  al  Warehouse  problem,  necesitaríamos conocer  como  este  funciona.  Este 
problema  trata  de  ordenar  los  productos  en  un  almacén  contando  para  ello  con  un  cierto 
espacio  donde  están  las  mercaderías  y  uno  donde  el  espacio  es  libre  para  el  movimiento  y 
transporte  de  las  mismas.  Sin  embargo  ordenarlo  dada  una  configuración  final,  o  un  cierto 
parámetro  no  será  tan  simple  y  rápido  de realizar  si  contamos  con  un  gran  volumen  de 
insumos.  No  solo  podemos  considerar  un  almacén,  sino  porque  no  un  estacionamiento  donde 
se  necesita  colocar  los  automóviles  en  ciertas  posiciones  arbitrarias  en  un  mínimo  de  tiempo,  y 
por ende de movimientos.  
 

 
 
Ahora  solo  nos  quedaría  establecer  una  relación  entre  los  dos  problemas planteados.  Para  ello 
recurrimos  al  N  puzzle,  de  donde  ampliamos  a  un  número  determinado  por  el  ancho  y  largo 
del  área  total  y  dividimos  dos  subáreas,  una  donde  estás  los  objetos  y  un  área  libre  donde  se 
realizan los movimientos. Veamos la formulación de nuestro problema para entenderlo mejor. 
 
2. Formulación del problema 
 
Formalmente ...