N-regine in Haskell senza lista attraversamento

StackOverflow https://stackoverflow.com/questions/1255018

Domanda

ho cercato nel web per le diverse soluzioni al problema n-queens in Haskell ma non ho trovato nessuno che la potesse verificare la presenza di posizioni non sicuri nel tempo O (1) tempo, come quello di mantenere un allineamento per le diagonali e / uno per i \ diagonali.

La maggior parte delle soluzioni che ho trovato appena controllato ogni nuova regina contro tutti i precedenti. Qualcosa come questo: 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)

Quale sarebbe il modo migliore per attuare un tale "O (1) approccio" in Haskell? Non sto cercando nulla "super-ottimizzato". Solo un modo per produrre la "è questo diagonale già utilizzato?" array in maniera funzionale.

UPDATE:

Grazie per tutte le risposte, gente! Il motivo per cui in origine posto la domanda è perché volevo risolvere un problema più difficile backtracking. Sapevo come risolverlo in un linguaggio imperativo, ma non poteva facilmente pensare ad una struttura di dati puramente funzionale per fare il lavoro. Ho pensato che il problema regine sarebbe un buon modello (essendo il backtracking problema :)) per il problema generale struttura di dati, ma non è il mio reale problema però .

Io in realtà voglio trovare una struttura dati che consente O (1) ad accesso casuale e detiene i valori che sono o in uno stato "iniziale" (linea libera / diagonale, nel caso n-queens) o in un "finale" stato (occupato linea / diagonale), con transizioni (libero di occupato) essendo O (1). Questo può essere implementato usando gli array mutabili in un linguaggio imperativo, ma sento che la limitazione dei valori di aggiornamento consente solo per una bella struttura di dati puramente funzionale (al contrario di Quicksort, per esempio, che davvero vuole array mutabili ).

Ho capito che la soluzione di qc è buono come si può ottenere usando array immutabili a Haskell e la funzione "principale" si presenta come quello che volevo essere: 

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

Il problema principale sembra essere trovare una migliore struttura di dati anche se, come Haskell array hanno O (n) l'aggiornamento. Altri suggerimenti belle inferiori della mitica O (1) Santo Graal:

  • DiffArrays venuto vicino, ma rovinare nel backtracking. Essi in realtà ottengono Super :( lento.
  • STUArrays conflitto con l'approccio backtracking abbastanza funzionale, in modo che vengono scartati.
  • Mappe e set sono solo O (log n) l'aggiornamento.

Non sono davvero sicuro che ci sia una soluzione globale, ma sembra promettente.

UPDATE:

La struttura dei dati più promettente ho trovato dove gli array rimorchio. Fondamentalmente un Haskell DiffArray ma muta indietro quando si marcia indietro.

È stato utile?

Soluzione

In generale, si sono probabilmente andando ad essere bloccato pagamento dell'imposta complessità O(log n) per un'implementazione funzionale non distruttivo o dovrete cedere e utilizzare un (IO|ST|STM)UArray.

rigorosi lingue puri potrebbero dover pagare una tassa O(log n) su una lingua impura in grado di scrivere i riferimenti con i riferimenti attraverso una mappa-come la struttura di attuazione; lingue pigri a volte può schivare questa tassa, anche se non v'è alcuna prova in entrambi i casi se la potenza in più offerto dalla pigrizia è sufficiente per schivare sempre questa imposta -. anche se è forte sospetto che la pigrizia non è abbastanza potente

In questo caso è difficile vedere un meccanismo mediante il quale pigrizia può essere sfruttata per evitare la tassa riferimento. E, dopo tutto quello che è il motivo per cui abbiamo la monade ST in primo luogo. ;)

Detto questo, si potrebbe verificare se o meno una sorta di cerniera bordo diagonale potrebbe essere utilizzato per sfruttare località di aggiornamenti -. Sfruttando località in una cerniera è un modo comune per cercare di eliminare un termine logaritmico

Altri suggerimenti

Probabilmente il modo più semplice sarebbe quella di utilizzare un UArray (Int, Int) Bool per registrare i bit sicuri / non sicuri. Anche se la copia di questo è O (n 2 ), per piccoli valori di N questo è il metodo più veloce disponibile.

Per i più grandi valori di N, ci sono tre opzioni principali:

  • Data.DiffArray rimuove copia in testa finché non si utilizza mai i vecchi valori di nuovo dopo modificandoli . Cioè, se si lancia sempre via il vecchio valore della matrice dopo mutare essa, la modifica è O (1). Se, invece, si accede al vecchio valore della matrice in seguito (anche solo per una lettura), la O (N 2 ) è pagato quindi per intero.
  • Data.Map e Data.Set consentire O (lg n) modifiche e ricerche. Questo cambia la complessità algoritmica, ma spesso è abbastanza veloce.
  • di Data.Array.ST STUArray s (Int, Int) Bool vi darà array imperativi, che consente di implementare l'algoritmo nella classica maniera (non funzionante).

Il problema potenziale base di questo approccio è che gli array per le diagonali devono essere modificate ogni volta una regina è collocato. Il piccolo miglioramento del tempo di ricerca costante per le diagonali potrebbe non essere necessariamente vale il lavoro supplementare di creare continuamente nuovi array modificati.

Ma il modo migliore per conoscere la vera risposta è quella di provare, così ho giocato un po 'intorno e si avvicinò con il seguente: 

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

Questo funziona ed è per n = 14 circa il 25% più veloce rispetto alla versione che lei ha citato. L'aumento di velocità principale viene dal usando gli array disimballati bdonian raccomandato. Con la Data.Array normale ha circa lo stesso tempo di esecuzione della versione in questione.

Potrebbe anche essere la pena di provare gli altri tipi di matrice dalla libreria standard, per vedere se il loro utilizzo può migliorare ulteriormente le prestazioni.

sto diventando scettico su l'affermazione che pura funzionale è generalmente O ( log n). Si veda anche la risposta di Edward Kmett che rende tale affermazione. Anche se questo può applicarsi a Random Access matrice mutevole in senso teorico, ma casuale accesso matrice mutevole probabilmente non è quello più qualsiasi algoritmo richiede, quando è appositamente studiato per la struttura ripetibile, cioè non casuale. Credo che Edward Kmett si riferisce a questo quando scrive, "sfruttare località di aggiornamenti".

Sto pensando O (1) è teoricamente possibile in una versione funzionale puro dell'algoritmo n-queens, con l'aggiunta di un metodo di annullamento per il DiffArray, che richiede uno sguardo indietro a differenze per rimuovere i duplicati ed evitare loro riproduzione.

Se ho ragione nella mia comprensione del modo in cui il backtracking n-regine algoritmo opera, quindi il rallentamento causato dalla DiffArray è perché le differenze non necessarie vengono mantenuti.

In astratto, un "DiffArray" (non necessariamente di Haskell) ha (o potrebbe avere) un metodo elemento insieme che restituisce una nuova copia della matrice e memorizza un record differenza con la copia originale, tra cui un puntatore alla nuova copia mutata. Quando la copia originale deve accedere a un elemento, allora questo elenco di differenze deve essere riprodotto al contrario per annullare le modifiche su una copia della copia corrente. Nota c'è anche l'overhead che questa lista unica legata deve essere percorsa fino alla fine, prima che possa essere riprodotto.

Immaginate invece questi sono stati memorizzati come un elenco doppio-linked, e c'era un'operazione di annullamento come segue.

Da un livello concettuale astratto, quale l'algoritmo backtracking n-regine fa è ricorsivamente operare su alcuni array di booleani, spostare la posizione della regina incrementale avanti in tali matrici su ogni livello ricorsivo. Vedere questa animazione .

Lavorare questo fuori in solo la mia testa, io visualizzo che la ragione DiffArray è così lento, è perché quando la regina viene spostato da una posizione all'altra, quindi il flag booleano per la posizione originale è arretrato su false e il nuovo posizione viene impostata su true, e queste differenze sono registrati, tuttavia sono necessari perché quando riprodotto in senso inverso, la matrice finisce con gli stessi valori che ha prima dell'inizio della riproduzione. Così, invece di utilizzare un'operazione di impostazione per impostare di nuovo a falso, ciò che è necessario è un metodo chiamata annullamento, eventualmente con un parametro di ingresso dicendo DiffArray cosa "annulla a" valore da ricercare nella citata lista doppio-linked delle differenze. Se quel "undo a" valore si trova in un record differenza nella lista doppia-linked, non ci sono cambiamenti intermedi contrastanti su quello stesso elemento dell'array trovato quando si cammina di nuovo nella ricerca lista, e il valore corrente è uguale al "undo da" valore in quella record di differenza, allora il record può essere rimosso e che la vecchia copia può essere ri-puntato al record successivo nella lista doppia-linked.

Che cosa questo compie è quello di rimuovere la copia inutile dell'intero array sul backtracking. C'è ancora un certo overhead in più rispetto alla versione imperativo dell'algoritmo, per l'aggiunta e disfare l'aggiunta dei record di differenza, ma questo può essere più vicino a costante di tempo, vale a dire O (1).

Se ho capito bene l'algoritmo di n-regina, il lookback per l'operazione di annullamento è una sola, quindi non c'è cammino. Così, non è neppure necessario memorizzare la differenza dell'elemento impostata quando si sposta la posizione di regina, poiché sarà annullata prima della vecchia copia sarà accessibile. Abbiamo solo bisogno di un modo per esprimere questo tipo di sicurezza, che è abbastanza facile da fare, ma lascerò come esercizio per il lettore, come questo post è già troppo lungo.

UPDATE: non ho scritto il codice for l'intero algoritmo, ma nella testa delle n-regine può essere implementato con a ciascuna riga iterata, una piega sulla seguente matrice di diagonali, in cui ogni elemento è il tupla tripletta di: (indice di riga è occupato o None, array di indici riga intersecanti sinistra-destra diagonale, array di indici riga intersecano destra-sinistra diagonale). Le righe possono essere iterati con ricorsione o una piega di una serie di indici di riga (la piega fa il ricorsione).

Di seguito le interfacce per la struttura dati mi immagino. La sintassi di seguito è Copute, ma penso che sia abbastanza vicino alla Scala, che si può capire cosa si intende.

Si noti che qualsiasi implementazione di DiffArray sarà irragionevolmente lento se si è multithreaded, ma le n-regine backtracking algoritmo non richiede DiffArray da multithread. Grazie a Edward Kmett per la segnalazione nei commenti per questa risposta. 

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: Sto lavorando sulla Scala implementazione , che ha un rispetto a quello che avevo suggerito sopra. Ho anche spiegato come un'ottimizzazione per le pieghe si avvicina lo stesso sovraccarico costante come una matrice mutevole.

Ho una soluzione. Tuttavia, la costante può essere grande, quindi non mi auguro davvero battere nulla.

Ecco la mia struttura dati: 

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

Consente tutte le operazioni che devono essere eseguite in O (1).

Il codice può essere trovato qui: http://hpaste.org/50707

La velocità è male - è più lento rispetto alla soluzione di riferimento registrato nella domanda su maggior parte degli ingressi. Li ho confrontata con l'altro sugli ingressi [1,3 .. 15] ed ho ottenuto i rapporti seguenti orari ((riferimento temporale soluzione / il mio tempo solution) in%):

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

Avviso quasi lineare rallentamento della soluzione di riferimento relativo al mio, che mostra la differenza di complessità asintotica.

La mia soluzione è probabilmente orribile in termini di rigore e cose del genere, e deve essere alimentato per alcuni molto buono compilatore ottimizzato (come Don Stewart, per esempio) per ottenere risultati migliori.

In ogni caso, penso che in questo problema O (1) e O (log (n)) sono indistinguibili comunque perché log (8) è a soli 3 e costanti come questo sono oggetto di micro-ottimizzazioni piuttosto che di algoritmo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top