N-ферзей в Haskell без обхода списка

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

Вопрос

Я искал в Интернете различные решения проблемы n-ферзей в Haskell, но не смог найти ни одного, которое могло бы проверять небезопасные позиции за время 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)

Как лучше всего реализовать такой подход «O (1)» в Haskell?Я не ищу ничего «супероптимизированного».Просто какой -то способ произвести «этот диагональ уже используется?» массив функционально.

ОБНОВЛЯТЬ:

Спасибо за все ответы, ребята!Причина, по которой я изначально задал этот вопрос, заключается в том, что я хотел решить более сложную проблему с возвратом.Я знал, как решить эту задачу на императивном языке, но не мог сразу придумать чисто функциональную структуру данных, которая могла бы выполнить эту работу.Я решил, что проблема ферзей будет хорошей моделью (поскольку тот проблема с возвратом :) ) общая проблема со структурой данных, но это не моя тема. настоящий проблема однако.

На самом деле я хочу найти структуру данных, которая допускает произвольный доступ O (1) и содержит значения, которые находятся либо в «начальном» состоянии (свободная линия/диагональ, в случае n-ферзей), либо в «конечном» состоянии (занятом линия/диагональ), причем переходы (от свободного к занятому) равны O(1).Это можно реализовать с использованием изменяемых массивов на императивном языке, но я считаю, что ограничение обновления значений позволяет создать только красивую чисто функциональную структуру данных (в отличие, например, от быстрой сортировки, которая Действительно хочет изменяемые массивы).

Я полагаю, что решение sth настолько хорошее, насколько это возможно, используя неизменяемые массивы в Haskell, а «основная» функция выглядит так, как я хотел:

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

  • DiffArrays приближается к этому, но ошибается при возврате.Они на самом деле получают супер медленный :( .
  • STUArrays конфликтуют с довольно функциональным подходом с возвратом, поэтому они отбрасываются.
  • Карты и наборы имеют только обновление 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) выплачивается тогда в полном объеме.
  • Данные.Карта и Данные.Набор разрешить модификации и поиск 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).См. также ответ Эдварда Кметта, в котором делается это утверждение.Хотя это может относиться к доступу к случайному изменяемому массиву в теоретическом смысле, но доступ к произвольному изменяемому массиву, вероятно, не является тем, что требуется большинству алгоритмов, если он должным образом изучен на предмет повторяемости структуры, т.е.не случайно.Я думаю, что Эдвард Кметт имеет в виду это, когда пишет: «Используйте локальность обновлений».

Я думаю, что O (1) теоретически возможно в чисто функциональной версии алгоритма n-ферзей путем добавления метода отмены для DiffArray, который запрашивает просмотр различий, чтобы удалить дубликаты и избежать их повторного воспроизведения.

Если я правильно понимаю, как работает алгоритм с обратным отслеживанием n-ферзей, то замедление, вызванное DiffArray, связано с сохранением ненужных различий.

Вкратце, "DiffArray" (не обязательно Haskell) имеет (или может иметь) метод set element, который возвращает новую копию массива и сохраняет запись различия с исходной копией, включая указатель на новую измененную копию.Когда исходной копии требуется доступ к элементу, этот список различий необходимо воспроизвести в обратном порядке, чтобы отменить изменения в копии текущей копии.Обратите внимание, что существуют даже издержки, связанные с тем, что этот односвязный список необходимо пройти до конца, прежде чем его можно будет воспроизвести.

Представьте себе, что вместо этого они были сохранены в виде двусвязного списка, и была выполнена следующая операция отмены.

На абстрактном концептуальном уровне алгоритм с обратным отслеживанием n ферзей рекурсивно работает с некоторыми массивами логических значений, постепенно перемещая позицию ферзя вперед в этих массивах на каждом рекурсивном уровне.Видеть эта анимация.

Размышляя об этом только в уме, я представляю, что причина, по которой DiffArray работает так медленно, заключается в том, что когда ферзь перемещается из одной позиции в другую, логический флаг для исходной позиции возвращается в значение false и устанавливается новая позиция. значение true, и эти различия записываются, но в них нет необходимости, поскольку при обратном воспроизведении массив оказывается с теми же значениями, которые были до начала воспроизведения.Таким образом, вместо того, чтобы использовать операцию установки для возврата к false, необходим вызов метода отмены, возможно, с входным параметром, сообщающим DiffArray, какое значение «отменить» нужно искать в вышеупомянутом двусвязном списке различий.Если это значение «отменить действие» обнаружено в разностной записи в двусвязном списке, то нет никаких конфликтующих промежуточных изменений в том же элементе массива, обнаруженном при возвращении в поиске по списку, и текущее значение равно значению «отменить действие из». значение в этой разностной записи, то запись можно удалить, а старую копию можно повторно указать на следующую запись в двусвязном списке.

Это позволяет удалить ненужное копирование всего массива при возврате.По сравнению с императивной версией алгоритма все еще существуют некоторые дополнительные накладные расходы на добавление и отмену добавления разностных записей, но это может быть ближе к постоянному времени, т.е.О(1).

Если я правильно понимаю алгоритм n-ферзей, обратный просмотр для операции отмены только один, поэтому обхода нет.Таким образом, даже нет необходимости сохранять разницу заданного элемента при перемещении позиции ферзя, поскольку оно будет отменено до того, как будет получен доступ к старой копии.Нам просто нужен способ безопасного выражения этого типа, и это достаточно легко сделать, но я оставлю это в качестве упражнения для читателя, поскольку этот пост уже слишком длинный.

ОБНОВЛЯТЬ:Я не писал код всего алгоритма, но в моей голове n-ферзей можно реализовать с помощью складки на каждой итерируемой строке следующего массива диагоналей, где каждый элемент представляет собой тройной кортеж:(индекс строки, в которой она занята или нет, массив индексов строк, пересекающих левую-правую диагональ, массив индексов строк, пересекающих правую-левую диагональ).Строки могут повторяться с помощью рекурсии или сгиба массива индексов строк (сгиб выполняет рекурсию).

Ниже приведены интерфейсы для структуры данных, которую я себе представляю.Синтаксис ниже — Copute, но я думаю, что он достаточно близок к Scala, чтобы вы могли понять, что задумано.

Обратите внимание, что любая реализация DiffArray будет неоправданно медленной, если она является многопоточной, но алгоритм возврата с n-ферзями не требует многопоточной работы 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, который имеет улучшенный интерфейс по сравнению с тем, что я предложил выше.Я также объяснил, как оптимизация сверток приближается к тем же постоянным накладным расходам, что и изменяемый массив.

У меня есть решение.Однако константа может быть большой, так что я не особо надеюсь что-то победить.

Вот моя структура данных:

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

Обратите внимание на почти линейное замедление эталонного решения по сравнению с моим, что показывает разницу в асимптотической сложности.

Мое решение, вероятно, ужасно с точки зрения строгости и тому подобного, и его нужно передать какому-нибудь очень хорошему оптимизирующему компилятору (например, Дону Стюарту), чтобы получить лучшие результаты.

В любом случае, я думаю, что в этой задаче O(1) и O(log(n)) в любом случае неотличимы, потому что log(8) равен всего 3, а подобные константы подлежат микрооптимизации, а не алгоритму.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top