N-damas em Haskell sem lista travessia

https://stackoverflow.com/questions/1255018

12-09-2019
|

Pergunta

Eu procurei na web para diferentes soluções para o problema n-rainhas em Haskell, mas não conseguiu encontrar nenhum que poderiam verificar se há posições inseguras em O (1) tempo, como aquele que você mantenha uma matriz para os / diagonais e um para os \ diagonais.

A maioria das soluções que eu encontrei apenas verificado cada nova rainha contra todos os anteriores. Algo assim: 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)

Qual seria a melhor maneira de implementar uma "abordagem O (1)" como em Haskell? Eu não estou procurando nada "super-otimizado". Apenas alguma forma para produzir o "é este diagonal já utilizado?" matriz de uma maneira funcional.

UPDATE:

Obrigado por todas as respostas, pessoal! A razão que eu originalmente feito a pergunta é porque eu queria resolver um problema retrocesso mais difícil. Eu sabia como resolvê-lo em uma linguagem imperativa, mas não poderia facilmente pensar em uma estrutura de dados puramente funcional para fazer o trabalho. Eu percebi que as rainhas problema seria um bom modelo (sendo o retrocesso problema :)) para o problema geral-estrutura de dados, mas não é o meu real problema embora .

Na verdade, eu quero encontrar uma estrutura de dados que permite (1) de acesso aleatório O e contém valores que são ou em um estado "inicial" (linha livre / diagonal, no n-rainhas caso) ou em um "final" estado (ocupada linha / diagonal), com transições (livre para ocupada) sendo o (1). Isso pode ser implementado usando matrizes mutáveis ??em uma linguagem imperativa, mas eu sinto que a restrição de valores de atualização permite que apenas para uma boa estrutura de dados puramente funcional (em oposição a Quicksort, por exemplo, que realmente quer matrizes mutáveis ).

Eu acho solução que do sth é tão bom quanto você pode obter usando matrizes imutáveis ??em Haskell e os "principais" de função se parece com o que eu queria que fosse:

-- 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))

O principal problema parece ser encontrar uma melhor estrutura de dados, porém, como Haskell Arrays tem O (n) a actualização. Outras sugestões agradáveis ??aquém do O mítico (1) Santo Graal:

DiffArrays chegar perto, mas atrapalhar no retrocesso. Eles realmente obter Super lento :(.
STUArrays conflito com a abordagem retrocesso muito funcional para que eles são descartados.
Mapas e conjuntos têm apenas O (log n) atualização.

Eu não estou realmente certo que há uma solução global, mas parece prometendo.

UPDATE:

A estrutura de dados mais promissores I encontrado onde Arrays reboque. Basicamente um Haskell DiffArray mas ele sofre mutações de volta quando você voltar atrás.

Solução

Em geral, você provavelmente vai ser preso pagando o imposto complexidade O(log n) para uma implementação não destrutivo funcional ou você vai ter que ceder e usar um (IO|ST|STM)UArray.

línguas puras rígidas pode ter que pagar um imposto O(log n) mais de uma linguagem impura que pode escrever para referências através da implementação de referências através de uma estrutura de mapa-like; línguas preguiçosos às vezes pode evitar este imposto, embora não haja nenhuma prova de qualquer forma ou não o poder extra oferecido pela preguiça é suficiente para sempre esquivar este imposto -. mesmo que é fortemente suspeita que a preguiça não é suficiente poderoso

Neste caso, é difícil ver um mecanismo pelo qual a preguiça pode ser explorada para evitar o imposto de referência. E, depois de tudo o que é por isso que temos a Mônada ST em primeiro lugar. ;)

Dito isso, você pode investigar ou não algum tipo de zipper placa-diagonal poderia ser usada para explorar localidade de atualizações -. Explorando localidade em um zíper é uma forma comum de tentar soltar um termo logarítmica

Outras dicas

Provavelmente a maneira mais simples seria usar um UArray (Int, Int) Bool para gravar os bits seguras / inseguras. Embora copiar este é O (n ²), para pequenos valores de N este é o método mais rápido disponível.

Para valores maiores de N, existem três grandes opções:

Data.DiffArray remove copiar sobrecarga , desde que você nunca usa os valores antigos novamente depois de modificá-los . Ou seja, se você sempre jogar fora o antigo valor da matriz após mutação isso, a modificação é O (1). Se, entretanto, você acessar o valor antigo da matriz mais tarde (mesmo para apenas uma leitura), o O (N ²) é pago, em seguida, na íntegra.
Data.Map e Data.Set permitir ó (lg n) modificações e pesquisas. Isso muda a complexidade algorítmica, mas muitas vezes é rápido o suficiente.
O Data.Array.ST STUArray s (Int, Int) Bool lhe dará matrizes imperativas, o que lhe permite implementar o algoritmo da maneira clássica (não funcional).

O potencial problema básico com esta abordagem é que as matrizes para as diagonais precisa ser modificado cada vez que uma rainha é colocada. A pequena melhoria de tempo de pesquisa constante para as diagonais pode não ser necessariamente a pena o trabalho adicional de constantemente criando matrizes nova modificados.

Mas a melhor maneira de saber a verdadeira resposta é a experimentá-lo, então eu brinquei um pouco e veio com o seguinte:

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

Este obras e é para n = 14 cerca de 25% mais rápido do que a versão que você mencionou. A principal aceleração vem de usar as matrizes desembalados bdonian recomendado. Com a Data.Array normal, ele tem aproximadamente o mesmo tempo de execução como a versão em questão.

Ele também pode valer a pena para tentar outros tipos de matrizes da biblioteca padrão para ver se usá-los pode melhorar ainda mais o desempenho.

Estou me tornando cético sobre a alegação que pura funcional é geralmente O ( log n). Ver também a resposta de Edward Kmett que faz essa reivindicação. Embora isso possa aplicar-se a acesso aleatório mutável matriz no sentido teórico, mas o acesso matriz mutável aleatório provavelmente não é o que mais qualquer algoritmo exige, quando for devidamente estudada para a estrutura repetível, ou seja, não aleatória. Eu acho que Edward Kmett refere-se a isso quando ele escreve, "explorar localidade de atualizações".

Estou pensando O (1) é teoricamente possível em uma versão funcional pura da n-rainhas algoritmo, adicionando um método de desfazer para o DiffArray, que solicita uma volta olhar nas diferenças para remover duplicatas e evitar repetindo-los.

Se eu estou correto em meu entendimento da forma como o retrocesso n-rainhas algoritmo funciona, então a desaceleração causada pela DiffArray é porque as diferenças desnecessárias estão sendo retidos.

Em resumo, um "DiffArray" (não necessariamente de Haskell) tem (ou pode ter) um método de elementos conjunto que retorna uma nova cópia da matriz e armazena um registro diferença com a cópia original, incluindo um ponteiro para o novo cópia alterada. Quando a cópia original precisa acessar um elemento, então esta lista de diferenças tem que ser repetido na ordem inversa para desfazer as alterações em uma cópia da cópia atual. Nota há ainda a sobrecarga que esta lista única ligada tem de ser percorrida até o fim, antes que possa ser repetido.

Imagine que em vez estes foram armazenados como uma lista duplamente ligada, e houve uma operação de anulação da seguinte forma.

A partir de um nível conceitual abstrato, o que o retrocesso n-rainhas algoritmo faz é de forma recursiva operar em algumas matrizes de booleanos, movendo-se a posição da rainha de forma incremental para a frente nessas matrizes em cada nível recursiva. Consulte esta animação .

Trabalhar isso em apenas minha cabeça, eu visualizo que a razão DiffArray é tão lento, porque, quando a rainha é movido de uma posição para outra, então o sinalizador booleano para a posição original é conjunto de volta para falso e o novo posição é definida como verdadeiro, e essas diferenças são registados, no entanto, são desnecessários porque quando repetido em sentido inverso, a matriz termina-se com os mesmos valores que tem antes da repetição começou. Assim, em vez de usar uma operação de conjunto para trás conjunto para false, o que é necessário é uma chamada de método de desfazer, opcionalmente com um parâmetro de entrada dizendo DiffArray o "desfazer para" valor a procurar na lista duas vezes ligada acima mencionada das diferenças. Se isso "desfazer para" valor é encontrado em um registro diferença na lista duas vezes ligada, não há conflito alterações intermediárias nesse mesmo elemento de matriz encontrada quando andar para trás na busca lista, eo valor atual é igual a "desfazer a partir de" valor em que o registro diferença, então o registro pode ser removido e que cópia antiga pode ser re-apontou para o próximo registro na lista duas vezes ligada.

O que isto consegue é para remover a cópia desnecessária de toda a matriz em retrocesso. Há ainda alguma sobrecarga extra em comparação com a versão imperativo do algoritmo, para adicionar e desfazendo o suplemento de registros de diferença, mas isso pode ser mais perto de tempo constante, ou seja, O (1).

Se bem entendi o algoritmo n-rainha, o lookback para a operação de desfazer é apenas um, então não há nenhuma caminhada. Assim, não é mesmo necessário para armazenar a diferença do elemento set ao mover a posição de rainha, uma vez que será desfeita antes da cópia antiga será acessado. Nós só precisamos de uma maneira de expressar esse tipo de forma segura, o que é bastante fácil de fazer, mas vou deixá-lo como um exercício para o leitor, como este post é muito longo já.

UPDATE: Eu não escrevi o código for todo o algoritmo, mas na cabeça os n-damas pode ser implementado com em cada fileira iterado, uma dobra sobre a seguinte matriz de diagonais, onde cada elemento é o tuplo tripleto de: (índice de linha que é ocupado ou não disponível, gama de índices de linha intersectam esquerda-direita diagonal, gama de índices de linha que intersecta direita-esquerda diagonal). As linhas pode ser repetido com a recursividade ou uma dobra de uma variedade de índices de linha (da dobra faz a recursividade).

Aqui segue as interfaces para a I envision estrutura de dados. A sintaxe a seguir é Copute, mas eu acho que é perto o suficiente para Scala, que você possa entender o que se pretende.

Note que qualquer implementação de DiffArray será excessivamente lento se for multithreaded, mas não os n-queens backtracking algoritmo não requer DiffArray para ser multithread. Graças a Edward Kmett para apontar isso nos comentários para esta resposta.

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.

UPDATE: Eu estou trabalhando na Scala implementação , que tem uma melhorada interface de em comparação com o que eu tinha sugerido acima. Eu também explicou como uma otimização para dobras aproxima a mesma constante sobrecarga como uma matriz mutável.

Eu tenho uma solução. No entanto, a constante pode ser grande, então eu realmente não espero bater nada.

Aqui está minha estrutura de dados:

-- | 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
   )

Ele permite que todas as operações necessárias para ser executada em O (1).

O código pode ser encontrado aqui: http://hpaste.org/50707

A velocidade é ruim - é mais lento do que a solução de referência postou a pergunta sobre a maioria das entradas. Eu aferido-los uns contra os outros em entradas [1,3 .. 15] e tem os seguintes índices de tempo ((tempo de solução de referência / meu tempo de solução) em%):

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

Observe quase linear slow-down da solução de referência em relação ao meu, mostrando diferença em complexidade assintótica.

A minha solução é provavelmente horrível em termos de rigor e coisas assim, e deve ser alimentado para alguns muito bom compilador otimizado (como Don Stewart, por exemplo) para obter melhores resultados.

De qualquer forma, acho que este problema O (1) e O (log (n)) são assim mesmo indistinguíveis porque log (8) está apenas a 3 e constantes como este são objecto de micro-otimizações e não do algoritmo.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow