リスト走査を行わない Haskell の N-Queen

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

質問

Haskell の n-queens 問題に対するさまざまな解決策を Web で検索しましたが、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 クイーンの場合) または「最終」状態 (占有) のいずれかの値を保持するデータ構造を見つけたいと考えています。線/対角線)、遷移 (自由から占有) は O(1) です。これは命令型言語で可変配列を使用して実装できますが、値の更新の制限により、純粋に機能的な優れたデータ構造しか許可されないように感じます（たとえば、クイックソートとは対照的に）。 本当に 可変配列が必要です)。

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) のみです。

全体的な解決策があるかどうかはわかりませんが、 らしい 有望な。

アップデート：

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

役に立ちましたか？

解決

一般的に、おそらく料金を支払うことになるでしょう。 O(log n) 機能的な非破壊実装には複雑性が課せられます。そうでない場合は、折れずに (IO|ST|STM)UArray.

厳密な純粋言語は料金を支払わなければならない場合があります O(log n) マップのような構造を通じて参照を実装することで参照に書き込むことができる不純な言語に対する課税。怠惰な言語はこの税金を回避できる場合がありますが、怠惰によってもたらされる追加の力が常にこの税金を回避するのに十分であるかどうかは、どちらにしても証拠はありません。たとえ怠惰が十分強力ではないことが強く疑われる場合でも。

この場合、怠惰を悪用して参照税を回避できるメカニズムを理解するのは困難です。そして結局のところ、それが私たちが持っている理由です ST そもそもモナド。;)

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

他のヒント

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

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

  • Data.DiffArray コピーのオーバーヘッドを削除します 変更後に古い値を再度使用しない限り、. 。つまり、配列を変更した後に常に配列の古い値を破棄する場合、変更は O(1) になります。ただし、後で配列の古い値にアクセスすると (読み取りのみの場合でも)、O(N2) 全額支払われます。
  • データ.マップ そして データセット O(lg n) の変更と検索を許可します。これによりアルゴリズムの複雑さが変わりますが、多くの場合、十分に高速になります。
  • Data.Array.ST STUArray s (Int, Int) Bool 命令型配列が提供されるため、従来の (非機能的な) 方法でアルゴリズムを実装できます。

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

しかし、本当の答えを知る最善の方法は試してみることです。そこで、少し試してみて次のことを思いつきました。

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% 高速です。主な高速化は、ボックス化されていないアレイを使用することによって実現されます。 ブードニアン 推奨。通常の Data.Array ランタイムは質問のバージョンとほぼ同じです。

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

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

O(1) は、DiffArray に undo メソッドを追加することで、n-queens アルゴリズムの純粋な関数バージョンで理論的に可能であると考えています。このメソッドは、重複を削除して再実行を避けるために相違点を遡ることを要求します。

バックトラッキング n-queen アルゴリズムの動作方法に関する私の理解が正しければ、DiffArray によって引き起こされる速度の低下は、不必要な差分が保持されていることが原因であることになります。

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

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

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

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

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

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

アップデート：アルゴリズム全体のコードは書いていませんが、私の頭の中で n クイーンは、反復される各行で、次の対角線の配列を折りたたんで実装できます。各要素は次の 3 つの要素のタプルです。(占有されている行のインデックス、またはなし、左右の対角線と交差する行インデックスの配列、左右の対角線と交差する行インデックスの配列)。行は、再帰または行インデックスの配列の折り畳み (折り畳みにより再帰が行われます) を使用して反復できます。

以下に、私が想定するデータ構造のインターフェイスを示します。以下の構文は 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.

アップデート：私が取り組んでいるのは、 スカラ実装, 、改良された インターフェース 上で提案したものと比較してください。また、フォールドの最適化が可変配列と同じ一定のオーバーヘッドにどのように近づくかについても説明しました。

解決策があります。ただし、定数が大きい可能性があるので、何かに勝つことはあまり期待できません。

私のデータ構造は次のとおりです。

-- | 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 であり、このような定数はアルゴリズムではなくマイクロ最適化の対象となるからです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top