algorithm - pseudocodigo - problema de las 4 reinas

N-reinas en Haskell sin recorrido de lista

Question

Busqué en la web diferentes soluciones para el problema de las n-reinas en Haskell, pero no pude encontrar ninguna que pudiera buscar posiciones inseguras en el tiempo O (1), como la que mantiene una matriz para las diagonales / y otra para / diagonales.

La mayoría de las soluciones que encontré acaban de comprobar cada nueva reina con 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 dicho "enfoque O (1)" en Haskell? No estoy buscando nada "super-optimizado". Solo una forma de producir "¿ya se usa esta diagonal?" Arreglo de manera funcional.

ACTUALIZAR:

Gracias por todas las respuestas, amigos! La razón por la que originalmente hice la pregunta es porque quería resolver un problema de retroceso más difícil. Sabía cómo resolverlo en un lenguaje imperativo, pero no podía pensar fácilmente en una estructura de datos puramente funcional para hacer el trabajo. Pensé que el problema de las reinas sería un buen modelo (siendo el problema de retroceso :)) para el problema general de la estructura de datos, pero no es mi problema real .

De hecho, quiero encontrar una estructura de datos que permita O (1) acceso aleatorio y que contenga valores que se encuentren en un estado "inicial" (línea libre / diagonal, en el caso de las n-reinas) o en un estado "final" (ocupado línea / diagonal), con transiciones (libres a ocupadas) siendo O (1). Esto se puede implementar utilizando arreglos mutables en un lenguaje imperativo, pero creo que la restricción de los valores de actualización solo permite una buena estructura de datos puramente funcional (a diferencia de Quicksort, por ejemplo, que realmente quiere arreglos mutables).

Me imagino que la solución de Sth es tan buena como la que puedes obtener utilizando arreglos inmutables en Haskell y la función "principal" se parece a lo que yo 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 encontrar una mejor estructura de datos, ya que los arreglos Haskell tienen O (n) actualización. Otras sugerencias agradables no llegan al mítico O (1) santo grial:

• Los DiffArrays se acercan pero se estropean en el retroceso. En realidad se vuelven súper lentos :(.
• STUArrays entra en conflicto con el enfoque de retroceso bastante funcional por lo que se descartan.
• Los mapas y los conjuntos solo tienen actualización O (log n).

No estoy realmente seguro de que haya una solución general, pero parece prometedora.

ACTUALIZAR:

La estructura de datos más prometedora que encontré donde Array Arreglos. Básicamente es un DiffArray de Haskell, pero se muta cuando retrocedes.

Answer 1

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

Pero la mejor manera de saber la respuesta real es probarlo, así que jugué un poco y encontré lo 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 un 25% más rápido que la versión que mencionó. La aceleración principal proviene del uso de matrices sin caja recomendadas por bdonian . Con el Data.Array normal, tiene aproximadamente el mismo tiempo de ejecución que la versión en la pregunta.

También puede valer la pena probar los otros tipos de matriz de la biblioteca estándar para ver si usarlos puede mejorar aún más el rendimiento.

Answer 2

En general, es probable que se quede atascado pagando el impuesto de complejidad O(log n) para una implementación no destructiva funcional o tendrá que ceder y usar un (IO|ST|STM)UArray .

Es posible que los lenguajes puros estrictos tengan que pagar un impuesto O(log n) sobre un lenguaje impuro que puede escribir referencias mediante la implementación de referencias a través de una estructura similar a un mapa; los lenguajes perezosos a veces pueden esquivar este impuesto, aunque no hay ninguna prueba de si el poder adicional ofrecido por la pereza es suficiente para esquivar este impuesto, incluso si se sospecha que la pereza no es lo suficientemente poderosa.

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

Dicho esto, podría investigar si algún tipo de cremallera diagonal de tablero podría usarse para explotar la localidad de las actualizaciones: explotar la localidad en una cremallera es una forma común de intentar eliminar un término logarítmico.

Answer 3

Me estoy volviendo escéptico acerca de la afirmación de que lo funcional puro es generalmente O (log n). Vea también la respuesta de Edward Kmett que hace esa afirmación. Si bien eso puede aplicarse al acceso aleatorio a una matriz mutable en el sentido teórico, el acceso aleatorio a una matriz mutable probablemente no sea lo que la mayoría de los algoritmos requieren, cuando se estudia adecuadamente para determinar la estructura repetible, es decir, no es aleatorio. Creo que Edward Kmett se refiere a esto cuando escribe "explotar la localidad de las actualizaciones".

Estoy pensando que O (1) es teóricamente posible en una versión puramente funcional del algoritmo n-queens, agregando un método de deshacer para el DiffArray, que solicita una revisión de las diferencias para eliminar los duplicados y evitar la reproducción.

Si estoy en lo cierto al entender la forma en que funciona el algoritmo de seguimiento de las n-reinas, la desaceleración causada por el DiffArray se debe a que se mantienen las diferencias innecesarias.

En el resumen, un "DiffArray" (no necesariamente de Haskell) tiene (o podría tener) un método de elementos establecidos que devuelve una nueva copia de la matriz y almacena un registro de diferencias con la copia original, incluido un puntero a la nueva copia modificada. Cuando la copia original necesita acceder a un elemento, entonces esta lista de diferencias debe reproducirse a la inversa para deshacer los cambios en una copia de la copia actual. Tenga en cuenta que incluso existe la sobrecarga de que esta lista de un solo enlace se debe recorrer hasta el final, antes de poder volver a jugar.

Imagínese, en cambio, estos se almacenaron como una lista de doble enlace, y hubo una operación de deshacer de la siguiente manera.

Desde un nivel conceptual abstracto, lo que hace el algoritmo de retroceso n-reinas es operar recursivamente en algunos arreglos de valores booleanos, moviendo la posición de la reina progresivamente hacia adelante en esos arreglos en cada nivel recursivo. Vea esta animación .

Trabajando esto solo en mi cabeza, visualizo que la razón por la que DiffArray es tan lento, es porque cuando la reina se mueve de una posición a otra, entonces la bandera booleana para la posición original vuelve a ser falsa y la nueva posición se establece es cierto, y estas diferencias se registran, pero no son necesarias porque cuando se reproducen a la inversa, la matriz termina con los mismos valores que tiene antes de que comenzara la reproducción. Por lo tanto, en lugar de usar una operación de configuración para establecer de nuevo en falso, lo que se necesita es una llamada al método de deshacer, opcionalmente con un parámetro de entrada que le dice a DiffArray qué valor de "deshacer para" buscar en la lista de diferencias de doble enlace mencionada anteriormente. Si ese valor de "deshacer para" se encuentra en un registro de diferencia en la lista de doble enlace, no hay cambios intermedios conflictivos en el mismo elemento de matriz encontrado al retroceder en la búsqueda de lista, y el valor actual es igual a "deshacer desde" valor en ese registro de diferencia, entonces el registro se puede eliminar y esa copia antigua se puede volver a apuntar al siguiente registro en la lista de doble enlace.

Lo que esto logra es eliminar la copia innecesaria de toda la matriz en el retroceso. Todavía hay una sobrecarga adicional en comparación con la versión imperativa del algoritmo, para agregar y deshacer la adición de registros de diferencia, pero esto puede ser más cercano al tiempo constante, es decir, O (1).

Si entiendo correctamente el algoritmo n-queen, el lookback para la operación de deshacer es solo uno, por lo que no hay caminata. Por lo tanto, ni siquiera es necesario almacenar la diferencia del elemento establecido al mover la posición de reina, ya que se deshará antes de que se acceda a la copia antigua. Solo necesitamos una forma de expresar este tipo de forma segura, lo que es bastante fácil de hacer, pero lo dejaré como un ejercicio para el lector, ya que esta publicación ya es demasiado larga.

ACTUALIZACIÓN: no he escrito el código para el algoritmo completo, pero en mi cabeza las n-reinas se pueden implementar con cada fila iterada, un pliegue en la siguiente serie de diagonales, donde cada elemento es la tupla triplete de: ( el índice de la fila está ocupado o Ninguno, matriz de índices de fila que se intersecan en diagonal izquierda-derecha, matriz de índices de fila que se intersecan en diagonal de derecha-izquierda). Las filas se pueden iterar con recursión o un pliegue de una matriz de índices de fila (el pliegue hace la recursión).

Aquí sigue las interfaces para la estructura de datos que imagino. La sintaxis a continuación es Copute, pero creo que está lo suficientemente cerca de Scala, que puedes entender lo que se pretende.

Tenga en cuenta que cualquier implementación de DiffArray será injustificadamente lenta si es de multiproceso, pero el algoritmo de seguimiento de n-reinas no requiere que DiffArray sea de multiproceso. Gracias a Edward Kmett por señalarlo en los comentarios para 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://.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 implementación de Scala , que tiene una interface mejorada interface comparación con lo que sugerí anteriormente. También he explicado cómo una optimización para los pliegues se acerca a la misma sobrecarga constante que una matriz mutable.

Answer 4

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

Para valores mayores de N, hay tres opciones principales:

• Data.DiffArray elimina la sobrecarga de la copia siempre que nunca vuelva a utilizar los valores antiguos después de modificarlos . Es decir, si siempre desecha el valor anterior de la matriz después de haberlo mutado, la modificación es O (1). Sin embargo, si accede al valor anterior de la matriz más tarde (incluso solo para una lectura), la O (N ² ) se paga en su totalidad.
• Data.Map y Data.Set permiten modificaciones y búsquedas en O (lg n). Esto cambia la complejidad algorítmica, pero a menudo es lo suficientemente rápido.
• El STUArray s (Int, Int) Bool le dará arreglos imperativos, lo que le permite implementar el algoritmo de la manera clásica (no funcional).

Answer 5

Tengo una solución. Sin embargo, la constante puede ser grande, así que realmente no espero 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
   )

Permite que todas las operaciones requeridas se realicen 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 publicada en la pregunta en la mayoría de las entradas. Los he comparado entre sí en entradas [1,3 .. 15] y obtuve los siguientes ratios de tiempo ((tiempo de solución de referencia / tiempo de solución) en%):

[24.66%, 19.89%, 23.74%, 41.22%, 42.54%, 66.19%, 84.13%, 106.30%]

Observe una ralentización casi lineal de la solución de referencia en relación con la mía, que muestra la diferencia en la complejidad asintótica.

Mi solución es probablemente horrible en términos de rigor y cosas por el estilo, y se debe enviar a un compilador de optimización muy bueno (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 solo 3 y constantes como esta están sujetas a microoptimizaciones en lugar de algoritmos.