N-reinas en Haskell sin recorrido de lista

https://stackoverflow.com/questions/1255018

12-09-2019
|

Pregunta

He buscado en la web para diferentes soluciones al problema de las n-reinas en Haskell, pero no pude encontrar ninguna que pudiera comprobar si hay posiciones inseguras en O (1) tiempo, al igual que uno que mantenga una matriz para las diagonales y / una para los \ diagonales.

La mayoría de las soluciones que encontré acaba de comprobar cada nueva reina en contra de todas las anteriores. Algo como esto: http://www.reddit.com/r/programming/comments/62j4m / nqueens_in_haskell /

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

¿Cuál sería la mejor manera de implementar un tal "O (1) enfoque" en Haskell? Yo no busco nada "super-optimizado". Sólo un poco de manera de producir el "es esta diagonal ya utilizado?" matriz de una manera funcional.

ACTUALIZACIÓN:

Gracias por todas las respuestas, la gente! La razón originalmente hice la pregunta es porque quería resolver un problema más difícil dar marcha atrás. Yo sabía cómo resolverlo en un lenguaje imperativo, pero no podía pensar fácilmente de una estructura de datos puramente funcional para hacer el trabajo. Me di cuenta que el problema reinas sería un buen modelo (siendo la backtracking problema :)) para el problema global de estructuras de datos, pero no es mi real problema, sin embargo .

I realmente quiero encontrar una estructura de datos que permite a O (1) de acceso aleatorio y tiene valores que son ya sea en un estado "inicial" (línea libre / diagonal, en el caso n-reinas) o en un "final" estado (ocupado de línea / diagonal), con transiciones (libre de ocupado) es O (1). Esto se puede implementar utilizando matrices mutables en un lenguaje imperativo, pero siento que la restricción de los valores de actualización sólo permite una buena estructura de datos puramente funcional (en oposición a la ordenación rápida, por ejemplo, que realmente quiere matrices mutables ).

Me imagino que la solución de algo es tan bueno como se puede conseguir utilizando matrices inmutables en Haskell y la función "principal" se parece a lo que quería que fuera:

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

El problema principal parece ser la búsqueda de una mejor estructura de datos, aunque, como Haskell matrices tienen O (n) la actualización. Otras sugerencias agradables están a la altura de la mítica O (1) Santo Grial:

DiffArrays se acercan pero se pierde en la vuelta hacia atrás. Consiguen realmente Super :( lento.
STUArrays conflicto con el enfoque de retroceso bastante funcional por lo que se descartan.
Mapas y conjuntos tienen solamente O (log n) la actualización.

No estoy realmente seguro de que hay una solución global, pero parece prometedor.

ACTUALIZACIÓN:

La estructura de datos más prometedor donde me encontré con matrices de remolque. Básicamente un DiffArray Haskell, pero muta hacia atrás cuando dar marcha atrás.

Solución

En general, usted está probablemente va a ser pegado pagar el impuesto complejidad O(log n) para una aplicación funcional no destructiva o que tendrá que ceder y utilizar un (IO|ST|STM)UArray.

lenguas puras estrictas pueden tener que pagar un impuesto sobre O(log n) una lengua impura que se pueden escribir en referencias mediante la implementación de referencias a través de una estructura en forma de mapa; idiomas perezosos a veces puede esquivar este impuesto, aunque no hay ninguna prueba de cualquier manera si la energía adicional ofrecido por la pereza es siempre suficiente para esquivar este impuesto -. incluso si se sospecha fuertemente que la pereza no es lo suficientemente potente

En este caso, es difícil ver un mecanismo por el cual la pereza podría ser explotada para evitar el impuesto de referencia. Y, después de todo lo que es por eso que tenemos la mónada ST en el primer lugar. ;)

Una vez dicho esto, es posible que investigar si o no algún tipo de cremallera bordo de la diagonal se podría utilizar para explotar localidad de cambios -. Explotando localidad en una cremallera es una forma común de tratar de soltar un término logarítmico

Otros consejos

Probablemente la forma más sencilla sería utilizar un UArray (Int, Int) Bool para grabar bits de seguros / inseguros. Aunque la copia de esto es O (n ²), para valores pequeños de N este es el método más rápido disponible.

Para valores grandes de N, hay tres opciones principales:

Data.DiffArray elimina la copia de arriba todo el tiempo que nunca utiliza los valores antiguos de nuevo después de su modificación . Es decir, si siempre tirar el antiguo valor de la matriz después de que la mutación, la modificación es O (1). Sin embargo, si se accede al valor antiguo de la matriz después (aunque sea por una lectura), el O (N ²) se paga en su totalidad a continuación.
Data.Map y Data.Set permitir O (lg n) modificaciones y operaciones de búsqueda. Esto cambia la complejidad algorítmica, pero a menudo es lo suficientemente rápido.
de Data.Array.ST STUArray s (Int, Int) Bool le dará matrices imperativas, que le permite implementar el algoritmo de la manera clásica (no funcional).

El problema básico con potencial de este enfoque es que las matrices de las diagonales deben ser modificados cada vez que se coloca una reina. La pequeña mejora del tiempo de búsqueda constante para las diagonales podría no ser necesariamente la pena el trabajo adicional de crear constantemente nuevos arreglos modificados.

Sin embargo, la mejor manera de conocer la verdadera respuesta es probarlo, así que jugó un poco y se le ocurrió la siguiente:

import Data.Array.IArray (array, (//), (!))
import Data.Array.Unboxed (UArray)
import Data.Set (Set, fromList, toList, delete)

-- contains sets of unoccupied columns and lookup arrays for both diagonals
data BoardState = BoardState (Set Int) (UArray Int Bool) (UArray Int Bool)

-- an empty board
board :: Int -> BoardState
board n
   = BoardState (fromList [0..n-1]) (truearr 0 (2*(n-1))) (truearr (1-n) (n-1))
   where truearr a b = array (a,b) [(i,True) | i <- [a..b]]

-- modify board state if queen gets placed
occupy :: BoardState -> (Int, Int) -> BoardState
occupy (BoardState c s d) (a,b)
   = BoardState (delete b c) (tofalse s (a+b)) (tofalse d (a-b))
   where tofalse arr i = arr // [(i, False)]

-- get free fields in a row
freefields :: BoardState -> Int -> [(Int, Int)]
freefields (BoardState c s d) a = filter freediag candidates
   where candidates = [(a,b) | b <- toList c]
         freediag (a,b) = (s ! (a+b)) && (d ! (a-b))

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

-- all possibilities to place n queens on a n*n board
queens :: Int -> [[(Int, Int)]]
queens n = place (board n) n

Esto funciona y es para n = 14 aproximadamente el 25% más rápido que la versión que usted ha mencionado. El aumento de velocidad principal proviene del uso de las matrices sin embalaje bdonian recomendado. Con la Data.Array normal, que tiene aproximadamente el mismo tiempo de ejecución como la versión en la pregunta.

También podría valer la pena probar los otros tipos de matriz de la librería estándar para ver si su uso puede mejorar aún más el rendimiento.

Me estoy convirtiendo en escépticos sobre la afirmación de que pura funcional es generalmente O ( log n). Véase también la respuesta de Edward Kmett lo que hace que la reclamación. A pesar de que se aplique al azar acceso a matriz mutable en el sentido teórico, pero al azar de acceso a matriz mutable no es probablemente lo que requiere la mayoría de cualquier algoritmo, cuando se estudia adecuadamente para la estructura repetible, es decir, no al azar. Creo que Edward Kmett se refiere a esto cuando escribe, "explotar localidad de cambios".

Me refiero O (1) es teóricamente posible en una versión puramente funcional del algoritmo n-reinas, mediante la adición de un método de deshacer para el DiffArray, que solicita una mirada hacia atrás en diferencias para eliminar duplicados y evitar reproducir ellos.

Si estoy en lo correcto en mi comprensión de la forma en que el retroceso n-reinas algoritmo funciona, entonces la desaceleración causada por la DiffArray se debe a las diferencias innecesarias están siendo retenidos.

En el resumen, un "DiffArray" (no necesariamente de Haskell) tiene (o podría tener) un método de elemento fijo que devuelve una nueva copia de la matriz y almacena un registro diferencia con la copia original, incluyendo un puntero a la nueva cambiada copia. Cuando la copia original necesita tener acceso a un elemento, entonces esta lista de diferencias tiene que ser jugado de nuevo en sentido inverso para deshacer los cambios en una copia de la copia actual. Como nota, no es ni siquiera la sobrecarga que esta lista simplemente enlazada tiene que ser caminado hasta el final, antes de que pueda volver a reproducirse.

Imagínese en vez éstos se almacenan como una lista de doble ligado, y había una operación de deshacer como sigue.

Desde un punto de vista conceptual abstracta, lo que hace el algoritmo de rastreo n-reinas se forma recursiva operar en algunas matrices de booleanos, moviendo la posición de la reina de forma incremental hacia adelante en esas matrices en cada nivel recursivo. Ver esta animación .

Trabajar esto sólo en mi cabeza, visualizo que la razón DiffArray es tan lento, se debe a que cuando la reina se mueve de una posición a otra, entonces la bandera booleana para la posición original se vuelve a establecer en falso y el nuevo posición se establece en true, y estas diferencias se registran, sin embargo, son innecesarias porque cuando reproducido a la inversa, la matriz termina con los mismos valores que tiene antes de que comenzara la repetición. Así, en lugar de utilizar una operación de set para establecer de nuevo a falso, lo que se necesita es una llamada a un método de deshacer, opcionalmente con un parámetro de entrada diciendo DiffArray lo "deshacer al" valor para buscar en la mencionada lista de doble ligado de las diferencias. Si eso "deshacer a" valor se encuentra en un registro diferencia en la lista de doble ligado, no hay cambios intermedios contradictorias sobre el mismo elemento de la matriz se encuentra al caminar hacia atrás en la búsqueda lista, y el valor actual es igual al "deshacer de" valor en ese registro diferencia, entonces el registro se puede quitar y que copia de edad puede ser re-señaló al siguiente registro en la lista de doble vinculado.

Lo que esto logra es eliminar la copia innecesaria de toda la matriz de dar marcha atrás. Todavía hay cierta sobrecarga adicional en comparación con la versión imperativo del algoritmo, para añadir y deshacer el complemento de los registros de diferencia, pero esto puede estar más cerca de constante de tiempo, es decir, O (1).

Si he entendido bien el algoritmo n-reina, la vista al pasado de la operación de deshacer es una sola, por lo que no es un paseo. Por lo tanto, ni siquiera es necesario almacenar la diferencia del elemento de juego al mover la posición de reina, ya que se puede deshacer antes se tendrá acceso a la copia de edad. Sólo necesitamos una manera de expresar este tipo de forma segura, lo que es bastante fácil de hacer, pero lo dejo como ejercicio para el lector, ya que este post es demasiado tiempo.

ACTUALIZACIÓN: No he escrito el código for todo el algoritmo, pero en mi cabeza las n-reinas puede ser implementado con en cada fila iterado, un pliegue en la siguiente matriz de diagonales, donde cada elemento es la tupla triplete de: (índice de la fila que está ocupado o Ninguno, gama de índices de fila de intersección izquierda-derecha diagonal, gama de índices de fila de intersección derecha-izquierda diagonal). Las filas pueden repetirse con recursión o un pliegue de una serie de índices de fila (el pliegue hace la recursión).

A continuación, sigue las interfaces para la estructura de datos que imagino. La siguiente sintaxis es Copute, pero creo que es lo suficientemente cerca de Scala, que pueda comprender lo que se pretende.

Tenga en cuenta que cualquier implementación de DiffArray será excesivamente lento si es multiproceso, pero las n-reinas retrodetección algoritmo no requiere DiffArray a ser multiproceso. Gracias a Edward Kmett por señalarlo en los comentarios de esta respuesta.

interface Array[T]
{
   setElement  : Int -> T -> Array[T]     // Return copy with changed element.
   setElement  : Int -> Maybe[T] -> Array[T]
   array       : () -> Maybe[DiffArray[T]]// Return copy with the DiffArray interface, or None if first called setElement() before array().
}
// An immutable array, typically constructed with Array().
//
// If first called setElement() before array(), setElement doesn't store differences,
// array will return None, and thus setElement is as fast as a mutable imperative array.
//
// Else setElement stores differences, thus setElement is O(1) but with a constant extra overhead.
// And if setElement has been called, getElement incurs an up to O(n) sequential time complexity,
// because a copy must be made and the differences must be applied to the copy.
// The algorithm is described here:
//    http://stackoverflow.com/questions/1255018/n-queens-in-haskell-without-list-traversal/7194832#7194832
// Similar to Haskell's implementation:
//    http://www.haskell.org/haskellwiki/Arrays#DiffArray_.28module_Data.Array.Diff.29
//    http://www.haskell.org/pipermail/glasgow-haskell-users/2003-November/005939.html
//
// If a multithreaded implementation is used, it can be extremely slow,
// because there is a race condition on every method, which requires internal critical sections.

interface DiffArray[T] inherits Array[T]
{
   unset       : () -> Array[T]        // Return copy with the previous setElement() undone, and its difference removed.
   getElement  : Int -> Maybe[T]       // Return the the element, or None if element is not set.
}
// An immutable array, typically constructed with Array( ... ) or Array().array.

ACTUALIZACIÓN: Estoy trabajando en la Scala aplicación , que tiene una en comparación con lo que había sugerido anteriormente. También he explicado cómo una optimización de pliegues se aproxima a la misma sobrecarga constante como una matriz mutable.

Tengo una solución. Sin embargo, la constante puede ser grande, así que realmente no esperamos vencer a nada.

Aquí está mi estructura de datos:

-- | Zipper over a list of integers
type Zipper = (Bool,  -- does the zipper point to an item?
               [Int], -- previous items
                      -- (positive numbers representing
                      --   negative offsets relative to the previous list item)
               [Int]  -- next items (positive relative offsets)
               )

type State =
  (Zipper, -- Free columns zipper
   Zipper, -- Free diagonal1 zipper
   Zipper  -- Free diagonal2 zipper
   )

Se permite que todas las operaciones necesarias para llevar a cabo en O (1).

El código se puede encontrar aquí: http://hpaste.org/50707

La velocidad es mala - es más lenta que la solución de referencia publicado en la pregunta en la mayoría de los insumos. Los he Benchmarked uno contra el otro en las entradas [1,3 .. 15] y tengo las proporciones siguientes de tiempo ((referencia de tiempo de solución / mi tiempo de solución) en%):

[24,66%, 19,89%, 23,74%, 41,22%, 42,54%, 66,19%, 84,13%, 106,30%]

Aviso casi lineal lento hacia abajo de la solución de referencia en relación con la mina, que muestra la diferencia en complejidad asintótica.

Mi solución es probablemente horrible en términos de rigidez y cosas por el estilo, y se debe alimentar a un muy buen compilador de optimización (como Don Stewart, por ejemplo) para obtener mejores resultados.

De todos modos, creo que en este problema O (1) y O (log (n)) son indistinguibles de todos modos porque log (8) es sólo 3 y las constantes de este tipo son objeto de micro-optimizaciones más que de algoritmo.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow