목록 순회가 없는 Haskell의 N-queens

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

문제

나는 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-퀸의 경우 자유 라인/대각선) 또는 "최종" 상태(점유됨)에 있는 값을 보유하는 데이터 구조를 찾고 싶습니다. 선/대각선), 전환(자유에서 점유)은 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)만 업데이트합니다.

전체적으로 해결책이 있는지는 확실하지 않지만, 것 같다 유망하다.

업데이트:

내가 찾은 가장 유망한 데이터 구조는 Trailer Arrays입니다.기본적으로 Haskell DiffArray이지만 역추적하면 다시 돌연변이가 발생합니다.

도움이 되었습니까?

해결책

일반적으로 당신은 아마도 O(log n) 기능적 비파괴 구현에 대한 복잡성 세금 또는 (IO|ST|STM)UArray.

엄격한 순수 언어는 지불해야 할 수도 있습니다 O(log n) 지도와 같은 구조를 통해 참조를 구현하여 참조에 쓸 수있는 불순한 언어에 대한 세금; 게으른 언어는 때때로이 세금을 피할 수 있지만, 게으름이 제공하는 추가 권한이 항상이 세금을 피하기에 충분한 지 여부는 증거가 없지만, 게으름이 충분히 강력하지 않다고 의심 되더라도.

이 경우 참조 세를 피하기 위해 게으름을 악용 할 수있는 메커니즘을보기가 어렵습니다. 그리고 결국 우리가 ST 처음에 모나드. ;)

즉, 어떤 종류의 보드-다이어그 날 지퍼가 업데이트의 지역을 악용하는 데 사용될 수 있는지 여부를 조사 할 수 있습니다. 지퍼로 지역을 악용하는 것은 로그 용어를 삭제하는 일반적인 방법입니다.

다른 팁

아마도 가장 간단한 방법은 UArray (Int, Int) Bool 안전하고 안전하지 않은 비트를 기록합니다. 복사하지만 이것은 O (n2), N의 작은 값의 경우 이것은 가장 빠른 방법입니다.

N의 더 큰 값의 경우 세 가지 주요 옵션이 있습니다.

  • data.diffarray 복사 오버 헤드를 제거합니다 이전 값을 수정 한 후 다시는 사용하지 않는 한. 즉, 배열을 돌연변이 한 후에 항상 배열의 기존 값을 버리면 수정은 O (1)입니다. 그러나 나중에 배열의 이전 값에 액세스하는 경우 (읽기 만하면) O (N2) 그런 다음 전액 지불됩니다.
  • data.map 그리고 data.set O (LG N) 수정 및 조회를 허용합니다. 이것은 알고리즘 복잡성을 변화 시키지만 종종 충분히 빠릅니다.
  • data.array.st 's 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% 빠릅니다. 주요 속도는 Unboxed 어레이를 사용하는 것입니다 Bdonian 추천. 정상으로 Data.Array 질문에서 버전과 거의 같은 런타임이 있습니다.

표준 라이브러리에서 다른 배열 유형을 사용하여 사용하여 성능을 향상시킬 수 있는지 확인하는 것이 좋습니다.

나는 점점 회의적이 되어간다 주장 순수함수는 일반적으로 O(log n)입니다.해당 주장을 하는 Edward Kmett의 답변도 참조하세요.이론적 의미에서는 무작위 가변 배열 액세스에 적용될 수 있지만 무작위 가변 배열 액세스는 반복 가능한 구조에 대해 적절하게 연구될 때 대부분의 알고리즘에 필요한 것이 아닐 수 있습니다.무작위가 아닙니다.나는 Edward Kmett가 "업데이트의 지역성을 이용하라"라고 쓸 때 이것을 언급했다고 생각합니다.

중복을 제거하고 재생을 피하기 위해 차이점을 다시 살펴보도록 요청하는 DiffArray에 대한 실행 취소 메서드를 추가하여 n-queens 알고리즘의 순수 기능 버전에서 O(1)이 이론적으로 가능하다고 생각합니다.

역추적 n-queens 알고리즘이 작동하는 방식에 대한 나의 이해가 정확하다면 DiffArray로 인한 속도 저하는 불필요한 차이가 유지되기 때문입니다.

추상적으로 "DiffArray"(반드시 하스켈의 것은 아님)에는 배열의 새 복사본을 반환하고 변경된 새 복사본에 대한 포인터를 포함하여 원본 복사본과의 차이 레코드를 저장하는 set 요소 메서드가 있습니다(또는 가질 수 있습니다).원본 복사본이 요소에 액세스해야 하는 경우 현재 복사본 복사본의 변경 사항을 취소하기 위해 이 차이점 목록을 역으로 재생해야 합니다.이 단일 연결 목록을 재생하기 전에 끝까지 이동해야 하는 오버헤드도 있습니다.

대신 이것들이 이중 연결 목록으로 저장되었고 다음과 같이 실행 취소 작업이 있었다고 상상해 보십시오.

추상적 개념 수준에서 역추적 n-queens 알고리즘이 수행하는 작업은 일부 부울 배열에서 재귀적으로 작동하여 각 재귀 수준의 해당 배열에서 여왕의 위치를 ​​점진적으로 앞으로 이동하는 것입니다.보다 이 애니메이션.

머릿속으로만 이 작업을 수행하면서 DiffArray가 너무 느린 이유는 여왕이 한 위치에서 다른 위치로 이동하면 원래 위치에 대한 부울 플래그가 다시 false로 설정되고 새 위치가 설정되기 때문이라는 것을 시각화합니다. true로 설정하고 이러한 차이점은 기록되지만 역방향으로 재생할 때 배열은 재생이 시작되기 전과 동일한 값으로 끝나기 때문에 불필요합니다.따라서 false로 다시 설정하기 위해 설정 작업을 사용하는 대신 실행 취소 메서드 호출이 필요합니다. 선택적으로 DiffArray에게 위에서 언급한 이중 연결 차이점 목록에서 검색할 "실행 취소" 값을 알려주는 입력 매개 변수가 필요합니다.해당 "실행 취소" 값이 이중 연결 목록의 차이 레코드에서 발견된 경우 목록 검색에서 다시 돌아갈 때 발견된 동일한 배열 요소에 충돌하는 중간 변경 사항이 없으며 현재 값은 "실행 취소" 값과 같습니다. 해당 차이 레코드에 값이 있으면 해당 레코드를 제거하고 해당 이전 복사본을 이중 연결 목록의 다음 레코드로 다시 지정할 수 있습니다.

이것이 달성하는 것은 역추적 시 전체 배열의 불필요한 복사를 제거하는 것입니다.차이 레코드 추가를 추가하고 실행 취소하기 위해 알고리즘의 명령형 버전에 비해 여전히 약간의 추가 오버헤드가 있지만 이는 상수 시간에 더 가까울 수 있습니다.오(1).

n-queen 알고리즘을 올바르게 이해했다면 실행 취소 작업에 대한 Lookback은 단 하나이므로 Walk가 없습니다.따라서 이전 복사본에 액세스하기 전에 퀸 위치를 이동할 때 설정 요소의 차이를 저장할 필요조차 없습니다.우리는 이 유형을 안전하게 표현하는 방법이 필요할 뿐이고, 충분히 쉽게 할 수 있지만, 이미 이 게시물이 너무 길기 때문에 독자들을 위한 연습으로 남겨두겠습니다.

업데이트:나는 전체 알고리즘에 대한 코드를 작성하지 않았지만 내 머리 속에서 n-queens는 각 반복 행에서 다음과 같은 대각선 배열의 접기로 구현될 수 있습니다. 여기서 각 요소는 다음의 삼중항 튜플입니다.(점유된 행의 인덱스 또는 없음, 왼쪽-오른쪽 대각선과 교차하는 행 인덱스 배열, 오른쪽-왼쪽 대각선과 교차하는 행 인덱스 배열).행은 재귀 또는 행 인덱스 배열의 접기로 반복될 수 있습니다(접기는 재귀를 수행함).

다음은 내가 구상하는 데이터 구조에 대한 인터페이스입니다.아래 구문은 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))은 어쨌든 구별 할 수 없다고 생각합니다. 로그 (8)는 3이기 때문에 이와 같은 상수는 알고리즘이 아닌 미세 최적화의 대상이기 때문입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top