不带列表遍历的haskell中的n-queens

一般来说,你可能会被困在支付 O(log n) 功能性非破坏性实现的复杂性税,或者您必须关联并使用 (IO|ST|STM)UArray .

严格的纯语言可能要付出 O(log n) 对一种不纯的语言征税,这种语言可以通过类似地图的结构实现引用来写入引用;懒惰的语言有时可以逃避这种税,尽管没有任何证据证明懒惰提供的额外权力是否足以总是逃避这种税——即使人们强烈怀疑懒惰不是力量。够了。

在这种情况下,很难看到一种机制可以利用懒惰来避免参考税。毕竟这就是为什么我们 ST 一开始是蒙娜德。;)

也就是说,您可以研究是否可以使用某种板对角线拉链来利用更新的位置——利用拉链中的位置是尝试删除对数项的常用方法。

可能最简单的方法是使用 UArray (Int, Int) Bool 记录安全/不安全位。尽管复制这是O(n ^二 ,对于较小的n值,这是可用的最快方法。

对于较大的n值,有三个主要选项:

• Data.DiffArray 删除复制开销 只要修改后不再使用旧值 . 也就是说,如果在对数组进行赋值之后总是丢弃它的旧值,那么修改是O(1)。但是,如果以后访问数组的旧值(即使只用于读取),则 ^二 )全部付清。
• Data.Map 和 Data.Set 允许O(lg n)修改和查找。这改变了算法的复杂性,但通常足够快。
• 数据数组 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 它的运行时与问题中的版本大致相同。

还值得尝试使用标准库中的其他数组类型,看看使用它们是否可以进一步提高性能。

我开始怀疑 the claim 纯函数通常是O(log n)。另请参见爱德华·凯密特的答案,这是他的说法。虽然从理论上讲,这可能适用于随机可变数组访问,但当对可重复结构(即非随机结构)进行适当研究时,随机可变数组访问可能不是大多数算法所要求的。我认为爱德华·凯密特在写“利用更新的位置”时提到了这一点。

我认为在N-Queens算法的纯函数版本中,通过为DiffArray添加一个撤消方法,O(1)在理论上是可能的,该方法要求对差异进行回首,以删除重复项并避免重放它们。

如果我对回溯N-Queens算法的运行方式的理解是正确的,那么diffarray导致的速度减慢是因为保留了不必要的差异。

在摘要中,“diffarray”(不一定是haskell的)具有(或可能具有)set element方法,该方法返回数组的新副本,并存储与原始副本的差异记录,包括指向新更改副本的指针。当原始副本需要访问元素时,必须反向重放此差异列表,以撤消对当前副本的更改。注意,在重播这个单链表之前,甚至还有一些开销需要遍历到最后。

想象一下,它们被存储为一个双链接列表,有一个如下的撤消操作。

从抽象的概念层次来看,回溯N-Queens算法所做的是递归地操作一些布尔数组,在每个递归层次上以增量方式向前移动这些数组中的皇后位置。见 this animation .

我只在脑子里想了想,diffarray之所以这么慢,是因为当皇后从一个位置移动到另一个位置时,原始位置的布尔标志被设置回“假”,新位置被设置为“真”,并且这些差异被记录下来,但是它们是不必要的,因为当反向重放时,数组以重播开始前的值结束。因此,不使用set操作将其设置回false,而是需要一个undo方法调用,也可以使用一个输入参数告诉diffarray要在上述差异的双链接列表中搜索什么“undo to”值。如果在双链接列表中的差异记录中找到“撤消到”值,则在返回列表搜索时,在同一数组元素上找不到冲突的中间更改,并且当前值等于该差异记录中的“撤消到”值,则可以删除该记录,并且可以将旧副本重新指向T他在双链表中的下一个记录。

这样做的目的是在回溯时删除整个数组不必要的复制。与强制版本的算法相比,在添加和撤消添加差异记录方面仍然存在一些额外的开销,但这可能更接近于恒定时间,即O(1)。

如果我正确地理解了n-queen算法,那么对undo操作的回首只有一个,因此没有walk。因此,在移动皇后位置时甚至不需要存储集合元素的差异,因为在访问旧副本之前,它将被撤消。我们只需要一种安全地表达这种类型的方法,这很容易做到,但是我将把它作为练习留给读者,因为这篇文章已经太长了。

更新:我还没有为整个算法编写代码,但是在我的头脑中,N-Queens可以在每个迭代行上实现,在下面的对角线数组上进行折叠,其中每个元素是:(所占行的索引或无)、与左右对角线相交的行索引数组、与之相交的行索引数组右-左对角线)。行可以使用递归或行索引数组的折叠进行迭代(折叠执行递归)。

下面是我设想的数据结构的接口。下面的语法是copute,但我认为它离scala足够近,您可以理解它的意图。

注意,如果DiffArray是多线程的,那么它的任何实现都会非常缓慢,但是N-Queens回溯算法不需要DiffArray是多线程的。感谢爱德华·凯密特在对这个答案的评论中指出了这一点。

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 implementation ,这有一个改进 interface 与我上面的建议相比。我还解释了对折叠的优化如何达到与可变数组相同的常量开销。

我有一个解决办法。然而,常数可能很大,所以我不希望打败任何东西。

以下是我的数据结构:

-- | 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%】

注意,相对于我的参考解几乎是线性减速的,显示出渐进复杂性的差异。

我的解决方案在严格性和类似的方面可能很糟糕,必须反馈给一些非常好的优化编译器(例如DonStewart),以获得更好的结果。

无论如何,我认为在这个问题中,O(1)和O(n)无论如何都是不可区分的,因为日志(8)只是3,像这样的常量是微观优化的主题,而不是算法。