الگوریتم خدا

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

تعریف و راه‌حل 
این نظریه، برای پازل‌هایی قابل اجرا است که تعداد وضعیت‌های متفاوتی که می‌تواند داشته باشد، محدود است، با مجموعه‌ای از حرکات نسبتاً کوچک و معلوم که ممکن است روی این وضعیت‌ها قابل اجرا باشند و منجر به یک وضعیت جدید شوند. حل کردن یک پازل یعنی دستیابی به یک وضعیت معین نهایی که ممکن است فقط و فقط یک تک وضعیت یا یک عضو از مجموعه‌ای از وضعیت‌ها باشد.

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

مثال‌ها

پازل‌های مکانیکی

پازل‌های n تایی 
پازل ۱۵ تایی، در بدترین حالت می‌تواند با ۸۰ حرکت تک خانه‌ای یا ۴۳ حرکت چند خانه‌ای حل شود. برای حالت کلی آن که پازل n تایی است، از آنجایی که مسئلهٔ پیدا کردن یک راه‌حل بهینه برای آن، ان‌پی سخت است، هنوز مشخص نیست که آیا یک الگوریتم خدای کاربردی برای آن وجود دارد یا خیر، اگرچه بعید به نظر می‌رسد.

برج‌های هانوی 
برای پازل برج‌های هانوی، برای هر تعداد دیسک داده شده، یک الگوریتم خدا وجود دارد، هرچند تعداد حرکات با افزایش تعداد دیسک‌ها به صورت نمایی زیاد می‌شود.

مکعب روبیک 
در سال ۱۹۹۷، ریچارد کُرف الگوریتمی برای پیدا کردن راه‌حل‌های بهینه برای حل پازل مکعب روبیک ارائه کرد. اگرچه در سال ۱۹۸۰، دیوید سینگ‌مستر حدس زده بود که کران بالای تعداد حرکات لازم برای حل مکعب روبیک ۲۰ است، ولی در سال ۱۹۹۵، کشف شد که کران پایین برای تعداد حرکات لازم برای حل یک مکعب روبیک ۲۰ است و در سال ۲۰۱۰ محاسباتی که توسط کامپیوترهای بزرگ انجام شد، ثابت کرد که برای حل هیچ وضعیتی به بیش از ۲۰ حرکت نیاز نیست. بنابراین، عدد خدا برای مکعب روبیک، ۲۰ است.

عدد خدا 
برای مکعب روبیک، عدد خدا، بیشینه تعداد حرکات لازم برای حل هر یک از ۴۳٬۲۵۲٬۰۰۳٬۲۷۴٬۴۸۹٬۸۵۶٬۰۰۰ ترکیب‌های روبیک است و ثابت شده‌است که این عدد، برابر ۲۰ است. این عدد ممکن است کوچک بنظر برسد، اما به صورت تئوریک، این عدد باید حتی کمتر باشد. تنها حدود ۴۹۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰٬۰۰۰ ترکیب نیاز به تمام ۲۰ حرکت برای حل شدن دارد. هرچند که ۴۹۰ میلیون هم عدد بزرگی است، اما نسبت آن به ۴۳ کوینتیلیون وضعیت ممکن، تنها حدود ۰٫۰۰۰۰۰۱۱۳۲۸۹۵۵٪ است. یعنی احتمال اینکه بتوان به صورت تصادفی، وضعیتی تولید کرد که فقط و فقط در ۲۰ حرکت حل شود، نه بیشتر و نه کمتر، حدود ۱ در بیلیون است. اگرچه، تعداد ترکیب‌هایی که در ۱۹ حرکت حل می‌شوند، تقریباً ۱٫۵ کوینتیلیون است. به عبارتی، عدد خدا برای روبیک بیشتر به ۱۹ نزدیک است تا ۲۰، ولی اگر غیرممکن باشد حتی یک ترکیب را با کمتر از ۲۰ حرکت حل کرد، عدد خدا ۲۰ خواهد بود.

جدول زیر، تعداد وضعیت‌ها را برای فاصله‌های مختلف نشان می‌دهد:

.

در سال ۲۰۰۹، هربرت کوکیمبا (Herbert Kociemba) از برنامه Cube Explorer و یک کامپیوتر با پردازنده Intel Core i7-920 (که اولین پردازنده Core i7 بود) و ۶ گیگابایت حافظه رم استفاده کرد تا ۱۰۰٬۰۰۰ وضعیت تصادفی را به صورت بهینه حل کند. به‌طور میانگین، برنامه هر روز ۷٬۰۰۰ مکعب را حل می‌کرد. در نهایت، میانگین طول حل بهینهٔ این مکعب‌ها، ۱۷٫۷ حرکت بود.

.

در ژانویه ۲۰۱۰ نیز توماس روکیکی (Tomas Rokicki) حتی ۱٬۰۰۰٬۰۰۰ مکعب را به صورت بهینه حل کرد.

همان‌طور که در نمودارها مشخص است، توزیع‌های به دست آمده توسط توماس روکیکی نیز مشابه هربرت کوکیمبا است.

تاریخچه عدد خدا 
تحقیقات روی عدد خدا در سال ۱۹۸۱ آغاز شد، هنگامی که مارون تیستلثویت، با استفاده از الگوریتم پیچیده‌ای که خودش ابداع کرده بود، ثابت کرد که برای حل هر ۴۳ کوینتیلیون ترکیب مختلف مکعب روبیک، ۵۲ حرکت کافی است. به مرور زمان، متدهای بهینه‌تر برای حل این تعداد عظیم از ترکیب‌های محتمل در حرکات کمتر ابداع شد.

جدول زیر، تغییرات کران بالا و پایین عدد خدا برای مکعب روبیک را در گذر زمان نشان می‌دهد:

در اوت ۲۰۱۴ نیز توماس روکیکی و مورلی دیویدسون، ثابت کردند عدد خدا برای حرکت‌های ربع چرخشی، ۲۶ است (حرکت ربع چرخشی، یعنی یکی از وجه‌های مکعب روبیک را ۹۰ درجه بچرخانیم، ۱۸۰ درجه چرخش خود شامل دو حرکت ربع چرخشی است و ۲۷۰ درجه چرخش نیز همان ۹۰ درجه چرخش از سوی دیگر است.).

جستارهای وابسته 
 ماشین اوراکل

منابع 

الگوریتم‌های جستجو
بازی‌های ریاضی
بازی‌های فکری
مکعب روبیک