ملكات n في haskell دون قائمة اجتياز

Question

لقد بحثت على شبكة الإنترنت لحلول مختلفة لمشكلة ملكات 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-Queens) أو في حالة "نهائية" (مشغولة خط / قطري)، مع التحولات (مجانا إلى المحتلة) يجري O (1). يمكن تنفيذ ذلك باستخدام صفيفات قابلة للتغيير في لغة حتمية، لكنني أشعر أن تقييد القيم يسمح فقط بهيكل بيانات وظيفي بحت سوى (بدلا من QuickSort، على سبيل المثال، ذلك حقا يريد صفائف متغيرة).

أنا الرقم أن حل 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). اقتراحات لطيفة أخرى تسقط من الجراد المقدس الأسطوري (1)

• diffarrays تأتي قريبة ولكن الفوضى في التراجع. انهم في الواقع تحصل ممتاز بطيء :( .
• تعارض Stubarays مع نهج التراجع الوظيفي الجميل حتى يتم التخلص منها.
• الخرائط والمجموعات لديها فقط o (سجل n) تحديث.

أنا لست متأكدا حقا وجود حل عموما، لكنه يبدو واعد.

تحديث:

بنية البيانات الأكثر واعدة وجدت حيث صفائف مقطورة. أساسا haskell diffarray لكنه يتنوح مرة أخرى عند التراجع.

Answer 1

بشكل عام، من المحتمل أن تكون عالقة دفع O(log n) ضريبة التعقيد لتنفيذ وظيفي غير مدمر أو عليك أن تتصل واستخدام (IO|ST|STM)UArray.

لغات نقية صارمة قد تضطر لدفع O(log n) ضريبة على لغة نجاة يمكنها الكتابة إلى المراجع عن طريق تنفيذ المراجع من خلال هيكل يشبه الخرائط؛ يمكن أن تتحول اللغات الكسولة في بعض الأحيان إلى هذه الضريبة، على الرغم من عدم وجود أي دليل في أي حال من الأحوال سواء كانت القوة الإضافية التي تقدمها الكسل كافية لدود هذه الضريبة دائما - حتى لو كان يشتبه بشدة أن الكسل ليسوا أقوياء.

في هذه الحالة، من الصعب رؤية آلية يمكن من خلالها استغلال الكسل لتجنب الضريبة المرجعية. وبعد كل هذا هو السبب في أن لدينا ST مناد في المقام الأول. ؛)

ومع ذلك، يمكنك التحقيق في ما إذا كان يمكن استخدام نوع من سحاب المخرج أو لا يمكن استخدامه لاستغلال محلية التحديثات - استغلال المنطقة في سستة هو وسيلة شائعة لمحاولة إسقاط مصطلح لوغاريتمي.

Answer 2

ربما الطريقة الأكثر وضوحا هي استخدام UArray (Int, Int) Bool لتسجيل أجزاء آمنة / غير آمنة. على الرغم من أن نسخ هذا هو O (ن²)، بالنسبة للقيم الصغيرة من n هذه هي أسرع طريقة متاحة.

بالنسبة لقيم أكبر من N، هناك ثلاثة خيارات رئيسية:

• data.diffarray. يزيل نسخة النفقات العامة طالما أنك لا تستخدم أبدا القيم القديمة مرة أخرى بعد تعديلها. وبعد وهذا هو، إذا كنت دائما ترميم القيمة القديمة للمجموعة بعد التصاد، فإن التعديل هو O (1). ومع ذلك، إذا كنت تستطيع الوصول إلى القيمة القديمة للمجموعة لاحقا (حتى فقط للقراءة فقط)، فإن O (N²) دفعت ثم بالكامل.
• بيانات و بيانات السماح ب (LG N) التعديلات والبحث. هذا يغير تعقيد الخوارزميات، ولكن في كثير من الأحيان بسرعة كافية.
• data.array.st. STUArray s (Int, Int) Bool سوف تعطيك صفائف حتمية، مما يسمح لك بتنفيذ الخوارزمية بطريقة كلاسيكية (غير وظيفية).

Answer 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

هذا يعمل وما هو = 14 تقريبا 25٪ أسرع من الإصدار الذي ذكرته. السرعة الرئيسية تأتي من استخدام صفائف Unboxed BDonian. مستحسن. مع الطبيعي Data.Array لديها تقريبا نفس وقت التشغيل كإصدار في السؤال.

قد يستحق كل هذا العناء أيضا لتجربة أنواع الصفيف الأخرى من المكتبة القياسية لمعرفة ما إذا كان قد يؤدي استخدامها إلى تحسين الأداء.

Answer 4

أنا أشعر بالتشكك المطالبة هذا الوظيفية الخالصة عموما (سجل N). انظر أيضا إجابة إدوارد كميت التي تجعل هذا المطالبة. على الرغم من أن هذا قد ينطبق على الوصول إلى صفيف Random Randiable بالمعنى النظري، إلا أنه من المحتمل ألا يتطلب الوصول إلى صفيف Random Randable ما هو أكثر من أي خوارزمية، عندما تتم دراستها بشكل صحيح بنية قابلة للتكرار، أي غير عشوائي. أعتقد أن إدوارد كميت يشير إلى ذلك عندما يكتب، "استغلال محلية التحديثات".

أنا أفكر (1) ممكن من الناحية النظرية في إصدار وظيفي نقي من خوارزمية N-Queens، عن طريق إضافة طريقة تراجع عن Diffarray، والتي تطلب نظرة مرة أخرى في الاختلافات لإزالة التكرارات وتجنب إعادة التشغيل لهم.

إذا كنت صحيحا في فهمي للطريقة التي تعمل خوارزمية Tackracking N-Queens، فإن التباطؤ الناجم عن Diffarray هو أن الاختلافات غير الضرورية يتم الاحتفاظ بها.

في الملخص، يحتوي "Diffarray" (وليس بالضرورة Haskell's) (أو يمكن أن يكون لديك) طريقة عنصر محددة تقوم بإرجاع نسخة جديدة من الصفيف ويخزن سجل الفرق مع النسخة الأصلية، بما في ذلك مؤشر إلى نسخة تغيير جديدة. عندما تحتاج النسخة الأصلية إلى الوصول إلى عنصر، يجب إعادة تشغيل قائمة الاختلافات هذه في الاتجاه المعاكس للتراجع عن التغييرات في نسخة من النسخة الحالية. ملاحظة هناك حتى النفقات العامة التي يجب مشيت بها هذه القائمة المرتبطة واحدة حتى النهاية، قبل أن تتم إعادة التشغيل.

تخيل بدلا من ذلك تم تخزينها كقائمة مرتبطة مزدوجة، وكان هناك عملية تراجع على النحو التالي.

من مستوى مفاهيمي مجردة، ما يعمل خوارزمية التراجع N-Queens يعمل بشكل متكرر على بعض المصفوفات من المنطمنون، وتحريك موقف الملكة إلى الأمام بشكل تدريجي في تلك الصفائف على كل مستوى متكرر. يرى هذه الرسوم المتحركة.

العمل هذا في رأسي فقط، أتصور أن السبب diffarray بطيء للغاية، لأنه عندما يتم نقل الملكة من موقف إلى آخر، فإن العلم المنطقي للمركز الأصلي يتم تعيينه إلى FALSE ويتم تعيين الموضع الجديد إلى TRUE، يتم تسجيل هذه الاختلافات، ومع ذلك فهي غير ضرورية لأن عند إعادة التشغيل في الاتجاه المعاكس، ينتهي الصفيف مع نفس القيم التي لها قبل بدء التشغيل. وبالتالي، بدلا من استخدام عملية مجموعة لتعيينها إلى False، هناك حاجة هي مكالمة أسلوب التراجع، اختياريا مع معلمة الإدخال تخبر Diffarray ما "التراجع عن" القيمة للبحث عنها في قائمة الاختلافات المذكورة أعلاه من الاختلافات المذكورة أعلاه. إذا تم العثور على قيمة "التراجع إلى" في سجل اختلاف في القائمة ذات الصلة المزدوجة، فلا توجد تغييرات متضاربة متضاربة في نفس عنصر الصفيف الموجود عند المشي في البحث القائمة، والقيمة الحالية تساوي "التراجع عن" القيمة في سجل الاختلاف هذا، ثم يمكن إزالة السجل ويمكن إعادة توجيه هذه النسخة القديمة إلى السجل التالي في القائمة المرتبطة مزدوجة.

ما ينجزه هذا هو إزالة النسخ غير الضروري للمجموعة بأكملها على التراجع. لا يزال هناك بعض النواحي الإضافية مقارنة بالنسخة الحتمية من الخوارزمية، لإضافتها وتراجع عن إضافة سجلات الاختلافات، ولكن هذا يمكن أن يكون أقرب إلى وقت ثابت، أي O (1).

إذا فهمت بشكل صحيح خوارزمية N-Queen، فإن نشاؤها لعملية التراجع هي واحدة فقط، لذلك لا يوجد سير. وبالتالي، ليس من الضروري تخزين الفرق في عنصر المحدد عند نقل موضع الملكة، حيث سيتم التراجع عنه قبل الوصول إلى النسخة القديمة. نحتاج فقط إلى طريقة للتعبير عن هذا النوع بأمان، وهو سهل بما فيه الكفاية للقيام به، لكنني سأترك الأمر كممارسة لممارسة القارئ، لأن هذا المنصب طويل جدا بالفعل.

---

تحديث: لم أكتب التعليمات البرمجية للخوارزمية بأكملها، ولكن في رأسي يمكن تطبيق ملكات N مع كل صف متكرر، أضعاف على الصفيف التالي من الأقطار، حيث كل عنصر هو tuple الثلاثي من: ( مؤشر الصف الذي يشغله أو لا شيء، مجموعة من مؤشرات الصف تقاطع قطري الأيمن الأيسر، مجموعة من مؤشرات الصف تقاطع قطري الأيسر اليمنى). يمكن تكرار الصفوف مع العودية أو أضعاف من مجموعة من مؤشرات الصف (أضعاف لا تملك العودية).

فيما يلي واجهات بنية البيانات وأصورها. بناء الجملة أدناه كول، لكنني أعتقد أنه قريب بما فيه الكفاية من Scala، يمكنك فهم ما هو المقصود.

لاحظ أن أي تنفيذ Diffarriay سيكون بطيئا بشكل غير معقول إذا كان مؤلا، لكن خوارزمية التراجع 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., ، والتي تحسنت واجهه المستخدم مقارنة بما اقترحته أعلاه. لقد شرحت أيضا كيف يقترب الأمثل عن الطيات من نفس النماذج المستمرة كصفيف قابل للتغيير.

Answer 5

لدي حل. ومع ذلك، قد يكون الثابت كبيرا، لذلك لا أملك حقا الضرب بأي شيء.

هنا هي هيكل بياناتي:

-- | 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)) لا يمكن تمييزها على أي حال لأن السجل (8) هو فقط 3 وثابتات مثل هذه موضوعية للتحسينات الصغيرة بدلا من الخوارزمية.