پیوندهای رقصنده

در ادامهٔ این مقاله در مورد جزئیات تکنیک‌های پیاده‌سازی برای الگوریتم X صحبت می‌کنیم، خواننده به شدت تشویق می‌شود که ابتدا مقالهٔ الگوریتم X را مطالعه کند.

ایده‌های اصلی

ایدهٔ DLX بر پایهٔ مشاهدهٔ فهرست پیوندی دوطرفه حلقوی از ریشه‌ها شکل گرفت.

;x.left.right ← x.right
;x.right.left ← x.left

ریشهٔ X را از لیست حذف خواهد نمود، هنگامی که

;x.left.right ← x
;x.right.left ← x

موقعیت X در لیست را ذخیره‌سازی می‌کند، با فرض اینکه عنصر راست X و عنصر چپ X بدون تغییر باقی مانده‌اند. این کار صرف‌نظر از عدد عناصر در لیست می‌باشد، حتی اگر آن عدد ۱ باشد.

دانلد کنوت مشاهده کرد که یک پیاده‌سازی ساده از الگوریتم X مقدار بی‌شماری از زمان را برای جستجوی ۱ صرف می‌کند. وقتی که یک ستون را انتخاب می‌کنیم، کل ماتریس باید برای ۱ مورد جستجو قرار گیرد. وقتی که یک ردیف را انتخاب می‌کنیم، کل ستون باید برای ۱ مورد جستجو قرار گیرد. بعد از انتخاب یک ردیف، آن ردیف و تعداد ستون‌ها باید برای ۱ مورد جستجو قرار گیرند. برای بهبود دادن این زمان جستجو از پیچیدگی O(n) تا O(1)، دانلد کنوت یک ماتریس خلوت را پیاده‌سازی کرد جایی که فقط ۱ ذخیره شده است.

در همهٔ اوقات، هر گره در ماتریس اشاره می‌کند به گره‌های مجاور در چپ و راست (۱ در همان ردیف)، در بالا و پایین (۱ در همان ستون)، و سر آن ستون (در پایین توضیح داده شده‌است). هر ردیف و ستون در ماتریس شامل یک لیست پیوند دوتایی حلقوی از گره‌ها خواهندشد.

سر

سر هر ستون یک گره خاص خواهد داشت که به عنوان سرستون شناخته شده‌است، آن که در ستون لیست شامل می‌شود، و یک ردیف مخصوص را شکل خواهدداد ("ردیف کنترل") شامل همهٔ ستون‌هایی می‌شود که هنوز در ماتریس وجود دارند. در آخر، هر سرستون ممکن است به طور انتخابی تعداد گره‌ها در ستون خود را پیدا کند، بنابراین موقعیت یابی یک ستون با کمترین تعداد گره از پیچیدگی O(n) نسبت به O(n*m) است که n تعداد ستون‌ها و m تعداد سطرها می‌باشد. انتخاب کردن ستون با کم‌ترین شمار گره یک کار غیرمستدل است که کارایی را در همان مورد افزایش می‌دهد، ولی در الگوریتم ضروری نمی‌باشد.

کاوش

در الگوریتم X، ردیف‌ها و ستون‌ها مرتباً از ماتریس حذف و به آن بازگردانده می‌شوند. عملیات حذف توسط انتخاب کردن ستون و سطر در آن ستون تعیین شده‌است. اگر یک ستون انتخاب شده هیچ ردیفی نداشت، ماتریس کنونی غیرقابل‌حل است و باید رد گم می‌کرد. وقتی عملیات حذف رخ می‌دهد، همهٔ ستون‌ها برای ردیف انتخاب شده که شامل ۱ است حذف شده‌اند، در طول همهٔ ردیف‌ها (شامل ردیف انتخاب شده) که شامل یک ۱ در همهٔ ستون‌های حذف‌شده است. ستون‌ها حذف شده‌اند زیرا پر شده‌اند، و ردیف‌ها حذف شده‌اند زیرا با ردیف انتخاب‌شده در تضادند. برای حذف کردن یک ستون تنها، ابتدا سرستون انتخاب شده را حذف کنید. بعد، برای هر ردیف که ستون انتخاب شده شامل یک ۱ می‌باشد، در ردیف پیمایش کنید و از ستون دیگر حذف کنید (این ردیف‌های دیگر را غیرقابل‌دسترس می‌کند و این چگونگی جلوگیری از تضاد می‌باشد). این تفکیک ستون را برای هر ستون تکرار کنید جایی که ردیف انتخاب شده شامل یک ۱ باشد. این ترتیب انجام کار اطمینان می‌دهد که هر گرهٔ حذف شده دقیقاً یک‌بار حذف شده است و در یک حالت انجام کار قابل پیشبینی، بنابراین این می‌تواند به طور مناسب عمل پیمایش معکوس لیست را انجام دهد. اگر ماتریس نتیجه هیچ ستونی نداشت، بنابراین همهٔ آن‌ها پر می‌شوند و ردیف انتخاب شده از راه‌حل.

عمل پیمایش معکوس یک لیست

برای پیمایش معکوس لیست، فرایند بالا باید معکوس شود و از توضیح الگوریتم دوم بالا استفاده کند. یکی از لازمه‌های استفاده از آن الگوریتم این است که عمل پیمایش معکوس باید به طور دقیق معکوس عمل حذف انجام شود. مقالهٔ دانلد کنوت یک تصویر واضح از این روابط و چگونگی عملکرد تفکیک گره می‌دهد و مقدار ناچیزی آسایش از این محدودیت را آماده می‌کند.

محدودیت‌های اختیاری

همچنین این نیز ممکن است که برای حل مسایل یک پوششی که محدودیت مشخصی به صورت اختیاری است؛ ولی می‌تواند متقاعد شود نه بیشتر از یک‌بار. پیوندهای رقصنده این‌ها را با ستون‌های اولی که باید پر شوند تطابق می‌دهند و ستون‌های ثانویه که اختیاری هستند. این تست راه‌حل الگوریتم را تغییر می‌دهد از یک ماتریسی که هیچ ستونی ندارد به ماتریسی که هیچ ستون اولیه‌ای ندارد و اگر کشف کنندهٔ مینیمم یکم در یک ستون مورد استفاده قرار گرفت سپس آن نیاز دارد که تنها در طول ستون ابتدایی چک شود. دانلد کنوت در مورد محدودیت‌های اختیاری بحث می‌کند مانند کاربرد مسئله چند وزیر. قطر صفحه شطرنجی محدودیت‌های اختیاری را نشان می‌دهد، همانند بعضی از قطرها ممکن است اشغال نشود. اگر یک قطر اشغال شده‌است، آن تنها یک‌بار می‌توان اشغال شود.

دانلد کنوت(۲۰۰۰). پیوندهای رقصنده. منظر جشن هزار ساله در علوم کامپیوتر. P159 187. آرخیو: cs/0011047. بازیافته شده ۲۰۰۶-۰۷-۱۱.