17

Haskellのn-queens問題のさまざまな解決策をウェブで検索しましたが、O(1)時間で安全でない位置をチェックできるものは見つかりませんでした。たとえば、/対角線の配列と\対角線。

私が見つけたほとんどの解決策は、それぞれの新しい女王を以前のすべての女王と照合しました。このようなもの: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)

Haskellでそのような「O(1)アプローチ」を実装するための最良の方法は何でしょうか?私は「超最適化」されたものを探していません。「この対角線はすでに使用されていますか?」機能的な方法で配列。

アップデート:

皆さん、すべての答えをありがとう!私が最初に質問した理由は、より難しいバックトラックの問題を解決したかったからです。私はそれを命令型言語で解決する方法を知っていましたが、その仕事をするための純粋に機能的なデータ構造を簡単に考えることはできませんでした。クイーンズの問題は、全体的なデータ構造の問題の良いモデルになると思いましたが(バックトラッキングの問題です:))、それは私の本当の問題ではありません。

私は実際に、O(1)ランダムアクセスを許可し、「初期」状態(n-queensの場合はフリーライン/対角)または「最終」状態(占有)のいずれかの値を保持するデータ構造を見つけたいと思っています。線/対角)、遷移(自由から占有)はO(1)です。これは命令型言語の可変配列を使用して実装できますが、値の更新の制限により、純粋に機能的な優れたデータ構造しか可能にならないように感じます(たとえば、本当に可変配列が必要なQuicksortとは対照的です)。

sthのソリューションは、Haskellで不変の配列を使用するのと同じくらい優れていると思います。また、「main」関数は、私が望んでいたもののように見えます。

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

ただし、Haskell配列ではO(n)が更新されるため、主な問題はより良いデータ構造を見つけることであるようです。他の素晴らしい提案は、神話上のO(1)の聖杯には及ばない:

  • DiffArrayは接近しますが、バックトラックで混乱します。彼らは実際に遅くなります:(。
  • STUArrayは、かなり機能的なバックトラッキングアプローチと競合するため、破棄されます。
  • マップとセットの更新はO(log n)のみです。

全体的に解決策があるかどうかはわかりませんが、有望なようです。

アップデート:

TrailerArraysで見つけた最も有望なデータ構造。基本的にはHaskellDiffArrayですが、バックトラックすると元に戻ります。

4

5 に答える 5

6

おそらく最も簡単な方法は、 a を使用しUArray (Int, Int) Boolて安全/安全でないビットを記録することです。これをコピーすると O(n 2 ) になりますが、N の値が小さい場合、これが利用可能な最速の方法です。

N の値が大きい場合、次の 3 つの主要なオプションがあります。

  • Data.DiffArrayは、変更後に古い値を使用しない限り、コピーのオーバーヘッドを取り除きます。つまり、変更後に配列の古い値を常に破棄すると、変更は O(1) になります。ただし、後で配列の古い値にアクセスすると (読み取りのみの場合でも)、O(N 2 ) が全額支払われます。
  • Data.MapData.Set では、O(lg n) の変更と検索が可能です。これにより、アルゴリズムの複雑さが変わりますが、多くの場合、十分に高速です。
  • Data.Array.STSTUArray s (Int, Int) Boolは命令型配列を提供し、従来の (非機能的な) 方法でアルゴリズムを実装できるようにします。
于 2009-08-10T14:03:03.263 に答える
5

O(log n)一般に、おそらく、機能的で非破壊的な実装のために複雑さの税金を支払うことになるでしょう(IO|ST|STM)UArray

厳密な純粋言語はO(log n)、マップのような構造を介して参照を実装することによって参照に書き込むことができる非純粋な言語に対して税金を支払わなければならない場合があります。怠惰な言語は時々この税金をかわすことができますが、怠惰が十分に強力ではないことが強く疑われているとしても、怠惰によって提供される余分な力が常にこの税金をかわすのに十分であるかどうかの証拠はありません.

この場合、参照税を回避するために怠惰を悪用できるメカニズムを確認するのは困難です。そして、STそもそもモナドがあるのはそのためです。;)

とはいえ、ある種のボード対角ジッパーを使用して更新の局所性を利用できるかどうかを調査することもできます。ジッパーで局所性を利用することは、対数項を削除しようとする一般的な方法です。

于 2009-08-12T19:43:17.480 に答える
3

このアプローチの基本的な潜在的な問題は、クイーンが配置されるたびに対角線の配列を変更する必要があることです。対角線の一定のルックアップ時間のわずかな改善は、新しい変更された配列を常に作成するという追加の作業に必ずしも価値があるとは限りません。

しかし、本当の答えを知る最善の方法は試してみることです。

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

これは機能し、n=14 の場合、言及したバージョンよりも約 25% 高速です。主な高速化は、bdonianが推奨するボックス化されていない配列を使用することによるものです。通常のData.Array場合、問題のバージョンとほぼ同じランタイムです。

標準ライブラリの他の配列型を試して、それらを使用するとパフォーマンスがさらに向上するかどうかを確認することも価値があるかもしれません。

于 2009-08-10T19:03:01.627 に答える
3

私は、純粋汎関数が一般に O(log n) であるという主張に懐疑的になりつつあります。その主張をするEdward Kmettの回答も参照してください。それは理論的な意味でのランダムな可変配列アクセスに当てはまるかもしれませんが、反復可能な構造、つまりランダムではない構造について適切に研究されている場合、ランダムな可変配列アクセスはおそらくほとんどのアルゴリズムが必要とするものではありません。Edward Kmett は、「更新の局所性を悪用する」と書いているときにこれに言及していると思います。

O(1) は、n-queens アルゴリズムの純粋な関数型バージョンで理論的に可能であると考えています。DiffArray に元に戻すメソッドを追加することで、重複を削除し、それらの再生を回避するために差分を振り返ることを要求します。

バックトラッキング n-queens アルゴリズムの動作に関する私の理解が正しければ、DiffArray によって引き起こされる速度低下は、不要な差異が保持されているためです。

要約すると、「DiffArray」(必ずしも Haskell のものである必要はありません) には、配列の新しいコピーを返し、新しい変更されたコピーへのポインターを含む、元のコピーとの差分レコードを格納する set 要素メソッドがあります (または持つことができます)。元のコピーが要素にアクセスする必要がある場合、現在のコピーのコピーの変更を元に戻すために、この相違点のリストを逆に再生する必要があります。この単一リンクのリストは、再生する前に最後までたどらなければならないというオーバーヘッドさえあることに注意してください。

代わりに、これらが二重リンクされたリストとして保存され、次のように元に戻す操作があったと想像してください。

抽象的な概念レベルから、バックトラッキング n-queens アルゴリズムが行うことは、ブーリアンのいくつかの配列を再帰的に操作し、再帰レベルごとにそれらの配列内でクイーンの位置を段階的に前方に移動することです。このアニメーションを参照してください。

これを頭の中で考えてみると、DiffArray が非常に遅い理由は、クイーンがある位置から別の位置に移動すると、元の位置のブール値フラグが false に戻され、新しい位置が設定されるためだと思います。これらの違いは記録されますが、逆に再生すると、配列は再生開始前と同じ値になるため不要です。したがって、set 操作を使用して false に戻す代わりに、undo メソッドの呼び出しが必要です。必要に応じて、前述の二重リンクされた差分リストで検索する「元に戻す」値を DiffArray に指示する入力パラメーターを使用します。その「元に戻す」値が二重リンク リストの差分レコードにある場合、

これにより、バックトラッキングで配列全体の不要なコピーが削除されます。アルゴリズムの命令型バージョンと比較して、差分レコードの追加と追加の取り消しのためにまだ余分なオーバーヘッドがありますが、これは定数時間、つまり O(1) に近くなる可能性があります。

n-queen アルゴリズムを正しく理解していれば、元に戻す操作のルックバックは 1 つだけなので、ウォークはありません。したがって、古いコピーがアクセスされる前に元に戻されるため、クイーンの位置を移動するときにセット要素の違いを保存する必要さえありません。このタイプを安全に表現する方法が必要なだけで、これは簡単に実行できますが、この記事はすでに長すぎるため、読者の演習として残しておきます。


更新: アルゴリズム全体のコードを書いたわけではありませんが、頭の中で n-queens は、反復される各行で、次の対角線の配列の折り畳みで実装できます。ここで、各要素はのトリプレットタプルです: (占有されている行のインデックスまたは None、左右の対角線と交差する行インデックスの配列、左右の対角線と交差する行インデックスの配列)。行は、再帰または行インデックスの配列の折り畳みで反復できます (折り畳みは再帰を行います)。

以下は、私が思い描くデータ構造のインターフェースです。以下の構文は Copute ですが、Scala に十分近いので、意図が理解できると思います。

マルチスレッド化されている場合、DiffArray の実装は不当に遅くなることに注意してください。ただし、n-queens バックトラッキング アルゴリズムでは、DiffArray をマルチスレッド化する必要はありません。この回答のコメントで指摘してくれた Edward Kmett に感謝します。

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.

更新: 私はScala の実装に取り​​組んでいます。これは、上記で提案したものと比較してインターフェイスが改善されています。また、折り畳みの最適化が可変配列と同じ一定のオーバーヘッドにどのように近づくかについても説明しました。

于 2011-08-25T17:43:38.183 に答える
1

解決策があります。ただし、定数が大きい可能性があるため、何かを打ち負かすことはあまり望んでいません。

ここに私のデータ構造があります:

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

必要なすべての操作を O(1) で実行できます。

コードはここにあります: http://hpaste.org/50707

速度が悪いです。ほとんどの入力に関する質問に投稿された参照ソリューションよりも遅いです。入力に関してそれらを相互にベンチマークし[1,3 .. 15]、次の時間比率を得ました ((参照ソリューション時間 / 私のソリューション時間) %):

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

漸近的な複雑さの違いを示す、参照ソリューションの私のものに対するほぼ直線的な減速に注意してください。

私の解決策は、厳密性などの点でおそらく恐ろしいものであり、より良い結果を得るには、非常に優れた最適化コンパイラ (たとえば、Don Stewart など) にフィードする必要があります。

とにかく、この問題では O(1) と O(log(n)) はとにかく区別できないと思います。なぜなら、log(8) はちょうど 3 であり、このような定数はアルゴリズムではなくマイクロ最適化の対象だからです。

于 2011-08-27T10:11:43.643 に答える