algorithm - Lazily Atar el nudo para la programación dinámica en 1 dimensión

haskell dynamic-programming

Question

Hace varios años, tomé un curso de algoritmos en el que estábamos dando el siguiente problema (o uno similar):

Hay un edificio de n pisos con un ascensor que solo puede subir 2 pisos a la vez y bajar 3 pisos a la vez. Usando la programación dinámica, escriba una función que calcule la cantidad de pasos que toma el elevador para ir del piso i al piso j .

Obviamente, esto es fácil utilizando un enfoque con estado, crea una matriz y elementos de largo y lo llena con los valores. Incluso se podría utilizar un enfoque técnicamente sin estado que implique acumular un resultado de forma recursiva. Mi pregunta es cómo hacer esto de una manera no estatal mediante el uso de la evaluación perezosa y atar el nudo.

Creo que he ideado la fórmula matemática correcta:

donde i+2 y i-3 están dentro de los valores permitidos.

Lamentablemente no puedo hacer que termine. Si pongo el caso i+2 primero y luego elijo un piso uniforme, puedo obtenerlo para evaluar los pisos pares por debajo del nivel objetivo, pero eso es todo. Sospecho que se dispara directamente al piso más alto para todo lo demás, baja 3 niveles, luego se repite, oscilando para siempre entre los pocos pisos superiores.

Por lo tanto, es probable que esté explorando el espacio infinito (o finito pero con bucles) de una manera profunda. No puedo pensar en cómo explorar el espacio de una manera amplia sin utilizar una gran cantidad de estructuras de datos intermedias que imitan efectivamente un enfoque de estado.

Aunque este simple problema es decepcionantemente difícil, sospecho que al haber visto una solución en 1 dimensión, podría hacer que funcione para una variación bidimensional del problema.

EDITAR: Muchas de las respuestas intentaron resolver el problema de una manera diferente. El problema en sí no me interesa, la pregunta es sobre el método utilizado. El enfoque de Chaosmatter de crear una función minimal que pueda comparar números potencialmente infinitos es posiblemente un paso en la dirección correcta. Desafortunadamente, si trato de crear una lista que represente un edificio con 100 pisos, el resultado demora demasiado en calcularse, ya que las soluciones a los problemas secundarios no se reutilizan.

Hice un intento de usar una estructura de datos de autorreferencia, pero no termina, hay una especie de bucle infinito en marcha. Voy a publicar mi código para que pueda entender a qué me dirijo. Cambiaré la respuesta aceptada si alguien puede realmente resolver el problema utilizando la programación dinámica en una estructura de datos autorreferenciales utilizando la pereza para evitar calcular las cosas más de una vez.

levels = go [0..10]
  where
    go [] = []
    go (x:xs) = minimum
      [ if i == 7
          then 0
          else 1 + levels !! i
        | i <- filter (/n -> n >= 0 && n <= 10) [x+2,x-3] ]
      : go xs

Puedes ver como 1 + levels !! i Intento hacer referencia al resultado calculado anteriormente y cómo el filter (/n -> n >= 0 && n <= 10) [x+2,x-3] intenta limitar los valores de i a valores válidos. Como dije, esto no funciona en realidad, simplemente demuestra el método por el cual quiero que se resuelva este problema. Otras formas de resolverlo no me interesan.

Answer 1

El problema es que min necesita evaluar completamente ambas llamadas a f , por lo que si una de ellas repite infinitamente, nunca volverá. Así que tienes que crear un nuevo tipo, codificando que el número devuelto por f es cero o un sucesor de cero.

data Natural = Next Natural 
             | Zero

toNum :: Num n => Natural -> n
toNum Zero     = 0
toNum (Next n) = 1 + (toNum n)

minimal :: Natural -> Natural -> Natural
minimal Zero _            = Zero
minimal _ Zero            = Zero
minimal (Next a) (Next b) = Next $ minimal a b

f i j | i == j = Zero
      | otherwise = Next $ minimal (f l j) (f r j)
      where l = i + 2
            r = i - 3

Este código realmente funciona.

Answer 2

Otros han respondido a su pregunta directa sobre la programación dinámica. Sin embargo, para este tipo de problema, creo que el enfoque codicioso funciona mejor. Su implementación es muy sencilla.

f i j :: Int -> Int -> Int
f i j = snd $ until (/(i,_) -> i == j) 
                    (/(i,x) -> (i + if i < j then 2 else (-3),x+1))
                    (i,0)

Answer 3

Ya que está tratando de resolver esto en dos dimensiones, y para otros problemas que el descrito, exploremos algunas soluciones más generales. Estamos tratando de resolver el problema de la ruta más corta en los gráficos dirigidos.

Nuestra representación de una gráfica es actualmente algo como a -> [a] , donde la función devuelve los vértices accesibles desde la entrada. Cualquier implementación adicional requerirá que podamos comparar para ver si dos vértices son iguales, por lo que necesitaremos la Eq a .

El siguiente gráfico es problemático e introduce casi toda la dificultad para resolver el problema en general:

problematic 1 = [2]
problematic 2 = [3]
problematic 3 = [2]
problematic 4 = []

Cuando se intenta alcanzar 4 de 1, hay un ciclo que incluye 2 y 3 que debe detectarse para determinar que no hay una ruta de 1 a 4.

Búsqueda en amplitud

El algoritmo presentado por Will tiene, si se aplica al problema general para gráficos finitos, el desempeño en el peor de los casos que no tiene límites en el tiempo y el espacio. Podemos modificar su solución para atacar el problema general de los gráficos que contienen solo rutas finitas y ciclos finitos agregando detección de ciclos. Tanto su solución original como esta modificación encontrarán caminos finitos incluso en gráficos infinitos, pero ninguno puede determinar de manera confiable que no haya un camino entre dos vértices en un gráfico infinito.

acyclicPaths :: (Eq a) => (a->[a]) -> a -> a -> [[a]]
acyclicPaths steps i j = map (tail . reverse) . filter ((== j).head) $ queue
  where
    queue = [[i]] ++ gen 1 queue
    gen d _ | d <= 0 = []
    gen d (visited:t) = let r = filter ((flip notElem) visited) . steps . head $ visited 
                        in map (:visited) r ++ gen (d+length r-1) t

shortestPath :: (Eq a) => (a->[a]) -> a -> a -> Maybe [a]
shortestPath succs i j = listToMaybe (acyclicPaths succs i j)

Reutilizando la función de step de la respuesta de Will como la definición de su problema de ejemplo, podríamos obtener la longitud del camino más corto del piso 4 al 5 de un edificio de 11 pisos por fmap length $ shortestPath (step 11) 4 5 . Esto devuelve Just 3 .

Consideremos un gráfico finito con v vértices y e aristas. Un gráfico con v vértices y e bordes se puede describir con una entrada de tamaño n ~ O (v + e). El peor gráfico de caso para este algoritmo es tener un vértice inalcanzable, j , y los vértices y bordes restantes dedicados a crear el mayor número de caminos acíclicos que comienzan en i . Probablemente sea algo así como una camarilla que contiene todos los vértices que no son i o j , con bordes de i a cualquier otro vértice que no sea j . El número de vértices en una camarilla con bordes e es O (e ^ (1/2)), por lo que este gráfico tiene e ~ O (n), v ~ O (n ^ (1/2)). Esta gráfica tendría O ((n ^ (1/2))! Rutas para explorar antes de determinar que j es inalcanzable.

La memoria requerida por esta función para este caso es O ((n ^ (1/2))!), Ya que solo requiere un aumento constante en la cola para cada ruta.

El tiempo requerido por esta función para este caso es O ((n ^ (1/2))! * N ^ (1/2)). Cada vez que expande una ruta, debe verificar que el nuevo nodo no esté ya en la ruta, lo que lleva tiempo O (v) ~ O (n ^ (1/2)). Esto podría mejorarse a O (log (n ^ (1/2))) si tuviéramos Ord a y Set a estructura Set a o similar para almacenar los vértices visitados.

Para los gráficos no finitos, esta función solo debería dejar de terminar exactamente cuando no existe un camino finito de i a j pero sí existe un camino no finito de i a j .

Programación dinámica

Una solución de programación dinámica no se generaliza de la misma manera; vamos a explorar por qué.

Para empezar, adaptaremos la solución de chaosmasttter para que tenga la misma interfaz que nuestra primera solución de búsqueda:

instance Show Natural where
    show = show . toNum 

infinity = Next infinity

shortestPath'' :: (Eq a) => (a->[a]) -> a -> a -> Natural
shortestPath'' steps i j = go i
    where
        go i | i == j = Zero
             | otherwise = Next . foldr minimal infinity . map go . steps $ i

Esto funciona bien para el problema del ascensor, la shortestPath'' (step 11) 4 5 es 3 . Desafortunadamente, para nuestro problema problemático, shortestPath'' problematic 1 4 desborda la pila. Si añadimos un poco más de código para números Natural :

fromInt :: Int -> Natural
fromInt x = (iterate Next Zero) !! x    

instance Eq Natural where
    Zero == Zero         = True
    (Next a) == (Next b) = a == b
    _ == _ = False

instance Ord Natural where
    compare Zero Zero         = EQ
    compare Zero _            = LT
    compare _ Zero            = GT
    compare (Next a) (Next b) = compare a b

podemos preguntar si el camino más corto es más corto que algún límite superior. En mi opinión, esto realmente muestra lo que está sucediendo con la evaluación perezosa. problematic 1 4 < fromInt 100 es False y problematic 1 4 > fromInt 100 es True .

A continuación, para explorar la programación dinámica, necesitaremos introducir algo de programación dinámica. Dado que construiremos una tabla de soluciones para todos los subproblemas, necesitaremos saber los posibles valores que pueden tomar los vértices. Esto nos da una interfaz ligeramente diferente:

shortestPath'''' :: (Ix a) => (a->[a]) -> (a, a) -> a -> a -> Natural
shortestPath'''' steps bounds i j = go i
    where
        go i = lookupTable ! i
        lookupTable = buildTable bounds go2
        go2 i | i == j = Zero
              | otherwise = Next . foldr minimal infinity . map go . steps $ i

-- A utility function that makes memoizing things easier
buildTable :: (Ix i) => (i, i) -> (i -> e) -> Array i e
buildTable bounds f = array bounds . map (/x -> (x, f x)) $ range bounds

Podemos usar esto como shortestPath'''' (step 11) (1,11) 4 5 o shortestPath'''' problematic (1,4) 1 4 < fromInt 100 . Esto todavía no puede detectar ciclos ...

Programación dinámica y detección de ciclos.

La detección de ciclos es problemática para la programación dinámica, porque los subproblemas no son los mismos cuando se los aborda desde diferentes caminos. Considere una variante de nuestro problematic problemático.

problematic'' 1 = [2, 3]
problematic'' 2 = [3]
problematic'' 3 = [2]
problematic'' 4 = []

Si intentamos obtener de 1 a 4 , tenemos dos opciones:

• ir a 2 y tomar el camino más corto de 2 a 4
• ir a 3 y tomar el camino más corto de 3 a 4

Si elegimos explorar 2 , nos enfrentaremos a la siguiente opción:

• ir a 3 y tomar el camino más corto de 3 a 4

Queremos combinar las dos exploraciones de la ruta más corta de 3 a 4 en la misma entrada en la tabla. Si queremos evitar los ciclos, esto es algo un poco más sutil. Los problemas que enfrentamos fueron realmente:

• ir a 2 y tomar el camino más corto de 2 a 4 que no visita 1
• vaya a 3 y tome el camino más corto de 3 a 4 que no visita 1

Después de elegir 2

• vaya a 3 y tome el camino más corto de 3 a 4 que no visita 1 o 2

Estas dos preguntas sobre cómo obtener de 3 a 4 tienen dos respuestas ligeramente diferentes. Son dos subproblemas diferentes que no caben en el mismo lugar en una tabla. Responder a la primera pregunta eventualmente requiere determinar que no puede llegar a 4 de 2 . Responder a la segunda pregunta es sencillo.

Podríamos hacer un montón de tablas para cada conjunto posible de vértices visitados anteriormente, pero eso no suena muy eficiente. Casi me convencí a mí mismo de que no podemos hacer la capacidad de alcance como un problema de programación dinámica utilizando solo la pereza.

Amplia búsqueda de redux

Mientras trabajaba en una solución de programación dinámica con capacidad de alcance o detección de ciclo, me di cuenta de que una vez que hemos visto un nodo en las opciones, ninguna ruta posterior que visite ese nodo puede ser óptima, ya sea que sigamos ese nodo o no. Si reconsideramos la problematic'' :

Si intentamos obtener de 1 a 4 , tenemos dos opciones:

• vaya a 2 y tome el camino más corto de 2 a 4 sin visitar 1 , 2 o 3
• vaya a 3 y tome el camino más corto de 3 a 4 sin visitar 1 , 2 o 3

Esto nos da un algoritmo para encontrar la longitud del camino más corto con bastante facilidad:

-- Vertices first reachable in each generation
generations :: (Ord a) => (a->[a]) -> a -> [Set.Set a]
generations steps i = takeWhile (not . Set.null) $ Set.singleton i: go (Set.singleton i) (Set.singleton i)
    where go seen previouslyNovel = let reachable = Set.fromList (Set.toList previouslyNovel >>= steps)
                                        novel = reachable `Set.difference` seen
                                        nowSeen = reachable `Set.union` seen
                                    in novel:go nowSeen novel

lengthShortestPath :: (Ord a) => (a->[a]) -> a -> a -> Maybe Int
lengthShortestPath steps i j = findIndex (Set.member j) $ generations steps i

Como era de esperar, lengthShortestPath (step 11) 4 5 es Just 3 y lengthShortestPath problematic 1 4 es Nothing .

En el peor de los casos, las generations requieren espacio que sea O (v * log v), y tiempo que sea O (v * e * log v).

Answer 4

de pie en el piso i del edificio de la historia n , encuentre el número mínimo de pasos necesarios para llegar al piso j , donde

step n i = [i-3 | i-3 > 0] ++ [i+2 | i+2 <= n]

Así tenemos un árbol. tenemos que buscarlo en la forma más amplia hasta que obtengamos un nodo que tenga el valor j . Su profundidad es el número de pasos. construimos una cola, llevando los niveles de profundidad,

solution n i j = case dropWhile ((/= j).snd) queue
                   of []        -> Nothing
                      ((k,_):_) -> Just k
  where
    queue = [(0,i)] ++ gen 1 queue

La función gen dp toma su entrada p desde d muescas desde su punto de producción a lo largo de la cola de salida:

    gen d _ | d <= 0 = []
    gen d ((k,i1):t) = let r = step n i1 
                       in map (k+1 ,) r ++ gen (d+length r-1) t

Utiliza TupleSections . Aquí no hay nudos, solo correcursión, es decir, producción avanzada (optimista) y exploración frugal. Funciona bien sin atar nudos porque solo buscamos la primera solución. Si estuviéramos buscando varios de ellos, tendríamos que eliminar los ciclos de alguna manera.

• vea también: en.wikipedia.org/wiki/Corecursion#Discussion

Con la detección del ciclo:

solutionCD1 n i j = case dropWhile ((/= j).snd) queue
                    of []        -> Nothing
                       ((k,_):_) -> Just k
  where
    step n i visited =    [i2 | let i2=i-3, not $ elem i2 visited, i2 > 0] 
                       ++ [i2 | let i2=i+2, not $ elem i2 visited, i2 <=n]
    queue = [(0,i)] ++ gen 1 queue [i]
    gen d _ _ | d <= 0 = []
    gen d ((k,i1):t) visited = let r = step n i1 visited
                               in map (k+1 ,) r ++ 
                                  gen (d+length r-1) t (r++visited)

Por ejemplo, la solution CD1 100 100 7 ejecuta instantáneamente, produciendo Just 31 . La lista visited es prácticamente una copia del prefijo instanciado de la propia cola. Se podría mantener como un Mapa, para mejorar la complejidad del tiempo (como es, sol 10000 10000 7 => Just 3331 toma 1.27 segundos en Ideone).

Algunas explicaciones parecen estar en orden.

Primero, no hay nada en 2D acerca de su problema, porque el piso objetivo j es fijo.

Lo que parece querer es la memorización , como indica su última edición. La memorización es útil para soluciones recursivas ; su función es de hecho recursiva: analiza su argumento en subcasos, sintetizando su resultado de llamarse a sí mismo en subcasos (aquí, i+2 y i-3 ) que están más cerca del caso base (aquí, i==j ).

Debido a que la aritmética es estricta , su fórmula es divergente en presencia de cualquier camino infinito en el árbol de pasos (que va de piso en piso). La respuesta de chaosmasttter , al usar aritmética perezosa , la convierte automáticamente en un algoritmo de búsqueda que es divergente solo si no hay rutas finitas en el árbol, exactamente como mi primera solución anterior (a excepción del hecho de que no se está comprobando) Índices fuera de límites). Pero todavía es recursivo , por lo que de hecho se requiere la memorización.

La forma habitual de abordarlo primero es introducir el intercambio "revisando una lista" (ineficiente, debido al acceso secuencial; para soluciones de memoria eficientes, ver hackeo ):

f n i j = g i
  where
    gs = map g [0..n]              -- floors 1,...,n  (0 is unused)
    g i | i == j = Zero
        | r > n  = Next (gs !! l)  -- assuming there''s enough floors in the building
        | l < 1  = Next (gs !! r)
        | otherwise = Next $ minimal (gs !! l) (gs !! r)
      where r = i + 2
            l = i - 3

no probado.

Mi solución es corecursiva . No necesita memoización (solo necesita ser cuidadoso con los duplicados), porque es generativo, como la programación dinámica también. Se aleja de su caso inicial, es decir, el piso inicial. Un accesorio externo elige el resultado generado apropiado.

Hace un nudo, define la queue mediante su uso, la queue está en ambos lados de la ecuación. Considero que es el caso más simple de atar nudos, ya que se trata de acceder a los valores generados previamente, disfrazados.

La vinculación de nudos del segundo tipo, la más complicada, generalmente consiste en colocar algún valor aún no definido en alguna estructura de datos y devolverlo para que se defina en una parte posterior del código (como, por ejemplo, un puntero de enlace inverso en doble) lista circular vinculada); De hecho, esto no es lo que hace mi código ¹ . Lo que hace es generar una cola , agregar en su extremo y "eliminar" de su frente; al final, es solo una técnica de la lista de diferencias de Prolog, la lista de final abierto con su puntero final mantenido y actualizado, la construcción de lista de arriba a abajo de la recursión de la cola en el módulo contras - todas las mismas cosas conceptualmente. Primero descrito (aunque no nombrado) en 1974 , AFAIK.

¹ basado enteramente en el código de en.wikipedia.org/wiki/Corecursion#Discussion .