Encontrar la ruta más corta entre dos puntos en una cuadrícula, usando Haskell

Question

Este es un problema que puedo resolver fácilmente de una manera no funcional.

Pero solucionarlo en Haskell me está causando grandes problemas. Mi inexperiencia en lo que respecta a la programación funcional es seguramente una razón.

El problema:

que tiene un campo 2D dividido en rectángulos de igual tamaño. Una grilla simple Algunos rectángulos son espacios vacíos (y se pueden pasar) mientras que otros son intransitables. Dado un rectángulo inicial A y un rectángulo de destino B, ¿cómo calcularía la ruta más corta entre los dos? El movimiento es posible solo vertical y horizontalmente, en pasos un solo rectángulo grande.

¿Cómo podría lograr esto en Haskell? Los fragmentos de código ciertamente son bienvenidos, pero tampoco necesariamente necesarios. ¡Y los enlaces a otros recursos también son bienvenidos!

Gracias!

Answer 1

Representaría la grilla como una lista de listas, escriba [[Bool]]. Y me gustaría definir una función para saber si un elemento de rejilla es completa:

type Grid = [[Bool]] 
isFullAt :: Grid -> (Int, Int) -> Bool -- returns True for anything off-grid 

entonces me definir una función para encontrar vecinos:

neighbors :: (Int, Int) -> [(Int, Int)] 

Para encontrar vecinos no completos de point se puede filtrar con filter (not . isFullAt) $ neighbors point.

En este punto me gustaría definir dos estructuras de datos:

• mapa cada punto a Maybe Cost
• tienda todos los puntos con costo conocido en un montón

Inicializar con solamente la casilla de origen A en el montón, con costo cero.

Entonces bucle como sigue:

• Retire un cuadrado min costo del montón.
• Si aún no está en el mapa finito, agréguela y su costo c, y agregue todos los vecinos no completos al montón con costo c+1.

Cuando la pila está vacía, tendrá los costos de todos los puntos accesibles y pueden mirar hacia arriba B en el mapa finito.(Este algoritmo se puede llamar "algoritmo de Dijkstra"; lo he olvidado).

Puede encontrar mapas finitos en Data.Map. Supongo que hay un montón (también conocido como cola de prioridad) en algún lugar de la vasta biblioteca, pero no sé dónde.

Espero que esto sea suficiente para comenzar.

Answer 2

Bueno, sus tipos determinarán sus algoritmos.

¿Qué tipo de datos desea utilizar para representar la cuadrícula? ¿Una matriz bidimensional? Una lista de listas? ¿Un árbol? ¿Un gráfico?

Si solo desea la ruta más corta en un gráfico dirigido, usar algo del FGL (paquete de gráficos funcionales) sería lo mejor.