موضوع مقاله: پیوندهای رقصنده | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پیوندهای رقصنده | مقدمه: الگوریتم X یک الگوریتم بازگشتی، غیرقطعی، اول‌عمق و الگوریتمی است که لیست را به طور معکوس می‌پیماید که همهٔ راه‌حل‌ها را برای پوشش دقیق مسئله پیدا می‌کند. | ## بخش 1: پیوندهای رقصنده | بعضی از پوشاننده‌های دقیق مسئله که شناخته‌شده‌تر اند شامل موزائیک‌کاری، مسئله چند وزیر و سودوکو. همان‌طور که تکرار الگوریتم باعث می‌شود که یک پیوند با پیوند کناری خود برقصد که آن را می‌توان به لطافت رقص باله تشبیه نمود. پیاده‌سازی در ادامهٔ این مقاله در مورد جزئیات تکنیک‌های پیاده‌سازی برای الگوریتم X صحبت می‌کنیم، خواننده به شدت تشویق می‌شود که ابتدا مقالهٔ الگوریتم X را مطالعه کند. ایده‌های اصلی ایدهٔ DLX بر پایهٔ مشاهدهٔ فهرست پیوندی دوطرفه حلقوی از ریشه‌ها شکل گرفت. دانلد کنوت مشاهده کرد که یک پیاده‌سازی ساده از الگوریتم X مقدار بی‌شماری از زمان را برای جستجوی ۱ صرف می‌کند. بعد از انتخاب یک ردیف، آن ردیف و تعداد ستون‌ها باید برای ۱ مورد جستجو قرار گیرند. برای بهبود دادن این زمان جستجو از پیچیدگی O(n) تا O(1)، دانلد کنوت یک ماتریس خلوت را پیاده‌سازی کرد جایی که فقط ۱ ذخیره شده است. در همهٔ اوقات، هر گره در ماتریس اشاره می‌کند به گره‌های مجاور در چپ و راست (۱ در همان ردیف)، در بالا و پایین (۱ در همان ستون)، و سر آن ستون (در پایین توضیح داده شده‌است). سر سر هر ستون یک گره خاص خواهد داشت که به عنوان سرستون شناخته شده‌است، آن که در ستون لیست شامل می‌شود، و یک ردیف مخصوص را شکل خواهدداد ("ردیف کنترل") شامل همهٔ ستون‌هایی می‌شود که هنوز در ماتریس وجود دارند. | ## بخش 2: پیوندهای رقصنده | در آخر، هر سرستون ممکن است به طور انتخابی تعداد گره‌ها در ستون خود را پیدا کند، بنابراین موقعیت یابی یک ستون با کمترین تعداد گره از پیچیدگی O(n) نسبت به O(n*m) است که n تعداد ستون‌ها و m تعداد سطرها می‌باشد. انتخاب کردن ستون با کم‌ترین شمار گره یک کار غیرمستدل است که کارایی را در همان مورد افزایش می‌دهد، ولی در الگوریتم ضروری نمی‌باشد. کاوش در الگوریتم X، ردیف‌ها و ستون‌ها مرتباً از ماتریس حذف و به آن بازگردانده می‌شوند. اگر یک ستون انتخاب شده هیچ ردیفی نداشت، ماتریس کنونی غیرقابل‌حل است و باید رد گم می‌کرد. وقتی عملیات حذف رخ می‌دهد، همهٔ ستون‌ها برای ردیف انتخاب شده که شامل ۱ است حذف شده‌اند، در طول همهٔ ردیف‌ها (شامل ردیف انتخاب شده) که شامل یک ۱ در همهٔ ستون‌های حذف‌شده است. ستون‌ها حذف شده‌اند زیرا پر شده‌اند، و ردیف‌ها حذف شده‌اند زیرا با ردیف انتخاب‌شده در تضادند. بعد، برای هر ردیف که ستون انتخاب شده شامل یک ۱ می‌باشد، در ردیف پیمایش کنید و از ستون دیگر حذف کنید (این ردیف‌های دیگر را غیرقابل‌دسترس می‌کند و این چگونگی جلوگیری از تضاد می‌باشد). این تفکیک ستون را برای هر ستون تکرار کنید جایی که ردیف انتخاب شده شامل یک ۱ باشد. این ترتیب انجام کار اطمینان می‌دهد که هر گرهٔ حذف شده دقیقاً یک‌بار حذف شده است و در یک حالت انجام کار قابل پیشبینی، بنابراین این می‌تواند به طور مناسب عمل پیمایش معکوس لیست را انجام دهد. | ## بخش 3: پیوندهای رقصنده | اگر ماتریس نتیجه هیچ ستونی نداشت، بنابراین همهٔ آن‌ها پر می‌شوند و ردیف انتخاب شده از راه‌حل. عمل پیمایش معکوس یک لیست برای پیمایش معکوس لیست، فرایند بالا باید معکوس شود و از توضیح الگوریتم دوم بالا استفاده کند. یکی از لازمه‌های استفاده از آن الگوریتم این است که عمل پیمایش معکوس باید به طور دقیق معکوس عمل حذف انجام شود. مقالهٔ دانلد کنوت یک تصویر واضح از این روابط و چگونگی عملکرد تفکیک گره می‌دهد و مقدار ناچیزی آسایش از این محدودیت را آماده می‌کند. محدودیت‌های اختیاری همچنین این نیز ممکن است که برای حل مسایل یک پوششی که محدودیت مشخصی به صورت اختیاری است؛ ولی می‌تواند متقاعد شود نه بیشتر از یک‌بار. پیوندهای رقصنده این‌ها را با ستون‌های اولی که باید پر شوند تطابق می‌دهند و ستون‌های ثانویه که اختیاری هستند. این تست راه‌حل الگوریتم را تغییر می‌دهد از یک ماتریسی که هیچ ستونی ندارد به ماتریسی که هیچ ستون اولیه‌ای ندارد و اگر کشف کنندهٔ مینیمم یکم در یک ستون مورد استفاده قرار گرفت سپس آن نیاز دارد که تنها در طول ستون ابتدایی چک شود. | ## جمع‌بندی | قطر صفحه شطرنجی محدودیت‌های اختیاری را نشان می‌دهد، همانند بعضی از قطرها ممکن است اشغال نشود.