N-reines dans Haskell sans liste traversal

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

Question

J'ai cherché sur le web pour des solutions différentes à n-reines problème dans Haskell mais n'a pas pu trouver qui pourrait vérifier les positions dangereuses en O (1) le temps, comme celui que vous gardez un tableau pour les / diagonales et une des diagonales \.

La plupart des solutions que je viens de vérifier chaque trouvé nouvelle reine contre toutes les précédentes. Quelque chose comme ça: 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)

Quelle serait la meilleure façon de mettre en œuvre une telle approche « O (1) » dans Haskell? Je ne cherche pas à quoi que ce soit « super-optimisé ». Juste une façon de produire le « est cette diagonale déjà utilisé? » réseau de manière fonctionnelle.

Mise à jour:

Merci pour toutes les réponses, les gens! La raison pour laquelle j'ai demandé à l'origine, la question est parce que je voulais résoudre un problème plus difficile retours en arrière. Je savais comment résoudre dans un langage impératif, mais ne pouvait pas penser facilement d'une structure de données purement fonctionnelle pour faire le travail. Je me suis dit que le problème des reines serait un bon modèle (être la problème retours en arrière :)) pour le problème global structure de données, mais ce n'est pas mon réel problème si .

Je veux vraiment trouver une structure de données qui permet à O (1) un accès aléatoire et contient des valeurs qui sont (dans le cas n-reines ligne libre / diagonale) soit sur un état « initial » ou dans une « finale » état (occupé ligne / diagonale), avec des transitions (gratuitement occupé) étant O (1). Cela peut être réalisé en utilisant des réseaux mutables dans un langage impératif, mais je pense que la restriction des valeurs de mise à jour permet seulement une belle structure de données purement fonctionnelle (par opposition à Quicksort, par exemple, que vraiment veut tableaux mutables ).

Je figure que la solution de STH est aussi bon que vous pouvez obtenir en utilisant des tableaux immuables dans Haskell et la fonction « principale » ressemble à ce que je voulais être: 

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

Le principal problème semble trouver une meilleure structure de données si, comme Haskell Les tableaux ont mise à jour O (n). D'autres belles suggestions sont loin de l'O mythique (1) Saint-Graal:

  • DiffArrays venir dans le désordre, mais près retours en arrière. Ils obtiennent en fait super :( lent.
  • STUArrays conflit avec l'approche de retours en arrière assez fonctionnelle de sorte qu'ils sont mis au rebut.
  • Cartes et ensembles ont seulement O (log n) mise à jour.

Je ne suis pas vraiment sûr qu'il ya une solution globale, mais semble prometteur.

Mise à jour:

La structure de données les plus prometteuses j'ai trouvé où des tableaux de remorque. Fondamentalement, une DiffArray Haskell, mais il mute quand vous faites marche arrière.

Était-ce utile?

La solution

En général, vous allez probablement être coincé payer la taxe sur la complexité de O(log n) pour une implémentation non destructive fonctionnelle ou vous devrez laisser fléchir et utiliser un (IO|ST|STM)UArray.

Strict langues pures peuvent avoir à payer une taxe O(log n) sur une langue impure qui peut écrire à des références en mettant en œuvre des références à travers une structure similaire à une carte; langues paresseux peuvent parfois esquiver cette taxe, bien qu'il n'y ait aucune preuve de toute façon que ce soit ou non la puissance supplémentaire offerte par la paresse est suffisante pour toujours esquiver cette taxe -. même si on soupçonne fortement que la paresse est pas assez puissant

Dans ce cas, il est difficile de voir un mécanisme par lequel la paresse pourrait être exploitée afin d'éviter la taxe de référence. Et, après tout ce qui est la raison pour laquelle nous avons la monade ST en premier lieu. ;)

Cela dit, vous pourriez étudier si oui ou non une sorte de fermeture à glissière carte diagonale pourrait être utilisée pour exploiter la localité des mises à jour -. Exploitation localité une fermeture à glissière est une façon courante d'essayer d'abandonner un terme logarithmique

Autres conseils

Probablement serait d'utiliser un UArray (Int, Int) Bool pour enregistrer / sécurité des bits dangereux. Bien que la copie de la présente est O (n 2 ) pour les petites valeurs de N tel est le procédé le plus rapide disponible.

Pour les plus grandes valeurs de N, il y a trois grandes options:

Je deviens sceptique sur la demande qui est généralement O fonctionnel pur ( log n). Voir aussi la réponse d'Edward Kmett qui fait cette demande. Bien que cela puisse demander à accès au tableau mutable aléatoire dans le sens théorique, mais un accès aléatoire est mutable gamme probablement pas ce que la plupart ne importe quel algorithme nécessite, lorsqu'il est correctement étudié pour la structure répétitive, à savoir pas aléatoire. Je pense Edward Kmett fait référence à cela quand il écrit: « exploiter la localité des mises à jour ».

Je pense O (1) est théoriquement possible dans une version fonctionnelle pure de l'algorithme n-reines, en ajoutant une méthode de retrait pour la DiffArray, qui demande un regard rétrospectif sur les différences pour éliminer les doublons et éviter de les rejouer.

Si je ne me trompe pas dans ma compréhension de la façon dont l'algorithme n-queens retours en arrière fonctionne, le ralentissement provoqué par la DiffArray est parce que les différences inutiles sont conservés.

Dans l'abstrait, un « DiffArray » (pas nécessairement de Haskell) a (ou pourrait avoir) une méthode d'élément de jeu qui renvoie une nouvelle copie du tableau et stocke un enregistrement de différence avec la copie originale, y compris un pointeur vers la nouvelle copie modifiée. Lorsque la copie originale doit accéder à un élément, cette liste des différences doit être rejoué dans le sens inverse pour annuler les modifications sur une copie de la copie en cours. Notez qu'il ya même les frais généraux que cette liste unique liée doit être piétinés jusqu'à la fin, avant de pouvoir être rejoué.

Imaginez plutôt ils ont été stockés sous forme d'une liste double liée, et il y avait une opération d'annulation comme suit.

D'un niveau conceptuel abstrait, ce que l'algorithme n-reines de retours en arrière ne fonctionne est récursive sur certains tableaux de booléens, déplacement incrémentiel en avant la position de la reine dans ces tableaux à chaque niveau récursive. Voir cette animation .

Travailler cela dans ma tête que je visualise que la raison DiffArray est si lent, parce que quand la reine est déplacé d'une position à une autre, alors le drapeau booléen pour la position d'origine est remis à faux et le nouveau position est définie sur true, et ces différences sont enregistrées, mais ils ne sont pas nécessaires parce que quand rejoué en sens inverse, le tableau se retrouve avec les mêmes valeurs qu'il a avant la reprise a commencé. Ainsi, au lieu d'utiliser une opération de réglage pour remettre à faux, ce qui est nécessaire est un appel de méthode undo, éventuellement avec un paramètre d'entrée indiquant DiffArray ce que « undo à » valeur à rechercher dans la liste double liée mentionnée ci-dessus des différences. Si ce « undo à la » valeur se trouve dans un dossier de différence dans la liste double liée, il n'y a pas de changements intermédiaires contradictoires sur le même élément de tableau trouvé lors de la marche arrière dans la recherche de la liste, et la valeur actuelle est égale à la « défaire de » valeur dans cet enregistrement de différence, l'enregistrement peut être retiré et cette vieille copie peut être à nouveau souligné l'enregistrement suivant dans la liste à double lien.

Ce que cela accomplit est de supprimer la copie inutile du tableau entier sur retours en arrière. Il y a encore des frais généraux supplémentaires par rapport à la version impérative de l'algorithme, pour ajouter et défaisant l'ajout d'enregistrements de différence, mais cela peut être plus proche de la constante de temps, à savoir O (1).

Si je comprends bien l'algorithme n-reine, le lookback pour l'opération d'annulation est seul, donc il n'y a pas de marche. Il est donc même pas nécessaire de stocker la différence de l'élément de jeu lors du déplacement de la position de la reine, car elle sera annulée avant que l'ancienne copie sera accessible. Nous avons juste besoin d'un moyen d'exprimer ce type en toute sécurité, ce qui est assez facile à faire, mais je vais laisser comme un exercice pour le lecteur, car ce poste est trop longtemps déjà.

Mise à jour: Je n'ai pas écrit le code for l'ensemble de l'algorithme, mais dans la tête les n-reines peut être mis en oeuvre avec, à chaque rangée itéré, un pli sur le tableau suivant des diagonales, où chaque élément est le tuple triplet: (indice de ligne est occupée ou None, tableau d'index de rangée croisant gauche-droite diagonale, matrice d'indices de lignes d'intersection droite-gauche en diagonale). Les rangées peuvent être réitérées avec récursion ou un pli d'un réseau d'indices de ligne (le pli fait la récursion).

Ici suit les interfaces pour la structure de données que je prévois. La syntaxe ci-dessous est Copute, mais je pense qu'il est assez proche de Scala, que vous pouvez comprendre ce qui est prévu.

Notez que toute mise en œuvre de DiffArray sera excessivement lent si elle est multithread, mais les n-reines algorithme backtracking ne nécessite pas DiffArray à multithread. Merci à Edward Kmett pour le signaler dans les commentaires pour cette réponse. 

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.

Mise à jour: Je travaille sur le mise en œuvre Scala , qui a une interface améliorée par rapport à ce que je l'avais suggéré plus haut. J'ai aussi expliqué comment une optimisation des plis se rapproche de la même charge constante comme un tableau mutable.

J'ai une solution. Cependant, la constante peut être grande, donc je n'espère pas vraiment battre quoi que ce soit.

Voici ma structure de données: 

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

Il permet d'effectuer dans O toutes les opérations nécessaires (1).

Le code peut être trouvé ici: http://hpaste.org/50707

La vitesse est mauvais - il est plus lent que la solution de référence affichée dans la question sur la plupart des intrants. Je les ai comparés les uns contre les autres sur les entrées [1,3 .. 15] et a obtenu les rapports de temps suivants ((temps de solution de référence / mon temps de solution) en%):

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

Avis de ralentissement presque linéaire de la solution de référence par rapport à la mienne, montrant la différence de complexité asymptotique.

Ma solution est probablement terrible en termes de rigueur et des choses comme ça, et doit être alimenté à un très bon compilateur d'optimisation (comme Don Stewart par exemple) pour obtenir de meilleurs résultats.

Quoi qu'il en soit, je pense à ce problème O (1) et O (log (n)) sont impossibles à distinguer de toute façon, car log (8) est à seulement 3 et constantes comme celui-ci font l'objet de micro-Optimisations plutôt que de l'algorithme.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top