موضوع مقاله: برج هانوی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # برج هانوی | مقدمه: تاریخچه و صورت مسئله در محوطه معبدی در آسیای دور سه میله الماسی قرار داشت که یکی از آن‌ها حاوی تعدادی قرص طلایی بود. | ## بخش 1: برج هانوی | کاهنان معبد در تلاش بودند تا قرص‌های طلایی را از آن میله به یکی دیگر از میله‌ها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرص‌ها عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌بودند. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است: در هر زمان فقط یک دیسک را می‌توان جابجا نمود. برای اینکه مسئله‌ای بتواند با روش بازگشتی حل شود باید یک ویژگی اساسی داشته باشد. مسئله اصلی (مسئله‌ای که به ما داده می‌شود) قابل خرد شدن به زیر مسئله‌هایی از همان نوع مسئله اصلی باشد، به شرطی که اندازه زیر مسئله‌های ایجاد شده کمتر باشد. ایده اصلی این است که توجهمان را به جای حرکت بالاترین دیسک، روی پایین‌ترین دیسک میله متمرکز کرده، و مراحل زیر را طی می‌کنیم: n - ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدأ به میله مقصد حرکت می‌دهیم.n - ۱ دیسک را که هم‌اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. در حالت کلی می‌خواهیم بدانیم اگر تعداد دیسک‌ها n باشد، کمترین تعداد حرکت برای جابجا نمودن دیسک‌ها چقدر است؟ در ابتدا باید بررسی کنیم که آیا تابع بازگشتی فوق کمترین تعداد حرکت را چاپ می‌کند؟ جواب مثبت است؛ زیرا واضح است که برای جابجا کردن بزرگترین دیسک از پایین میله A، بقیه دیسک‌ها باید در میله B باشند. همچنین توالی حرکت‌ها برای هر n منحصربه‌فرد است؛ یعنی برای یک n دو توالی متمایز از جابجایی‌ها وجود ندارد که تعداد جابجایی آن‌ها کمتر یا مساوی این حالت باشد. حال به مسئله مرتبه اجرایی مسئله می‌پردازیم: فرض کنیم (T(n تعداد حرکت‌های لازم جهت انتقال n دیسک به مقصد باشد. بر اساس توضیحات فوق (T(n - ۱ حرکت برای انتقال n - ۱ دیسک به میله کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله مقصد، و باز (T(n - ۱ حرکت برای انتقال n - ۱ دیسک موجود در میله کمکی به میله مقصد نیاز است. | ## بخش 2: برج هانوی | پس می‌توان نوشت: T(n) =2 T(n - ۱) + ۱ با حل این رابطه بازگشتی داریم: T(n) = 2n-۱ همان‌طور که مشاهده می‌کنیم مرتبه اجرایی این الگوریتم (O(2n است که هرچند مرتبه مناسبی نیست، این روش حداقل تعداد حرکتهای ممکن را می‌دهد. اگر فرض کنیم کاهنان با سرعت عمل زیاد توانسته باشند به صورت شبانه‌روزی و نسل به نسل در هر دو ثانیه یک قرص را جابجا کنند، برای انتقال تمامی ۶۴ قرص به میله مقصد، در حدود ۱٫۱۶۹ ترلیون (میلیون میلیون) سال زمان لازم دارند! اما چون در تقسیم مسئله اصلی به دو زیر مسئله، اندازه ورودی‌های زیر مسئله‌ها نزدیک به اندازه ورودی اصلی هستند، کارایی الگوریتم مطلوب نیست. حل مسئله برج هانوی به روش غیربازگشتی این مسئله علاوه بر روش تابع بازگشتی راه حلهای غیربازگشتی نیز دارد. در بالا به این نتیجه رسیدیم که بهترین راه حل برای جابجا کردن n دیسک ۲n - ۱ حرکت نیاز دارد. در نتیجه مرتبه راه حلهای آن در بهینه‌ترین حالت، چه بازگشتی و چه غیربازگشتی، از مرتبه (O(2n خواهد بود. اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند مرتبه فضای مصرفی آن است. تبدیل مرتبه مصرف فضا از (O(n به (O(1 زمانی که مرتبه اجرایی الگوریتم (O(2n است چندان قابل توجه نیست. دلیل دیگر می‌تواند این باشد که برخی زبانهای برنامه‌نویسی از فراخوانی بازگشتی توابع پشتیبانی نمی‌کنند و مجبور به استفاده ار روش‌های غیربازگشتی هستند. اما دلیل اصلی این است که با بررسی این روش‌ها تمرین کوچکی برای تبدیل الگوریتمهای بازگشتی به غیربازگشتی انجام می‌دهیم. تا کنون چندین روش مختلف جهت پیاده‌سازی غیربازگشتی حل مسئله برج هانوی ارائه شده‌است، که ما در اینجا دو روش را معرفی کرده، و تنها یکی از آن‌ها را به‌طور کامل بررسی می‌کنیم. توجه داشته باشید که همه جزئیات حل مسئله به صورت دقیق و مشروح مطرح نمی‌شود، و استدلال قسمتی از نتیجه‌گیری‌ها به عنوان تمرین به شما واگذار می‌شود. روش اول: حل مسئله برج هانوی را می‌توان معادل پاسخ دادن به این سؤال دانست که: در هر مرحله کدام دیسک به کدام میله منتقل می‌شود؟ فرض کنیم دیسکهایی به شعاع y ,x و z که رابطه x <y <z را با هم دارند، کوچکترین دیسک هر میله باشند. | ## بخش 3: برج هانوی | به عبارت دیگر این سه دیسک، بالاترین دیسکهای میله‌ها هستند که قابلیت جابجایی دارند. اگر میله‌ای شامل هیچ دیسکی نباشد، دیسکی با شعاع بی‌نهایت را برای آن در نظر می‌گیریم. اگر قرار باشد طی دو مرحله متوالی یک دیسک خاص را جابجا کنیم، می‌توانیم دو مرحله را با هم ادغام کرده و کل جابجایی را یکجا انجام دهیم. پس در مرحله بعدی دیسک y جابجا خواهد شد؛ و بالاخره حرکت بعدی باز هم با دیسک ۱ است (چرا؟). پس با بررسی منطقی خود به این نتیجه رسیدیم که دیسک ۱ و دیسکی که بزرگترین دیسک در آن مرحله نیست، به صورت متناوب جابجا می‌شوند. چرا که روی یکی از میله‌ها دیسک ۱ قرار دارد که دیسک y نمی‌تواند روی آن قرار بگیرد. در مورد مراحلی هم که دیسک ۱ قرار است جابجا شود، می‌توان اینطور استدلال کرد: فرض کنیم دیسک ۱ روی میله A قرار داشته باشد و آن را به میله C منتقل کنیم. حال اگر این دیسک را به میله A بازگردانیم، به نوعی کار اضافی و بازگشت به عقب انجام داده‌ایم. برای آشکار شدن این موضوع کافی است مسئله برج هانوی را با دو دیسک حل کنید، و در حرکت دوم دیسک ۱، آن را به میله‌ای بازگردانید که از آن آمده بود. پس می‌توان گفت در حرکتهای متوالی، دیسک شماره ۱ به میله‌ای حرکت می‌کند که از آن به میله فعلی خود نیامده است. این مسئله نه تنها در مورد دیسک ۱، که در مورد همه دیسکها صادق است؛ یعنی همه دیسکها در حرکتهای خود به سمت میله‌ای می‌روند که در حرکت قبلی خود از آن نیامده‌اند. زمانی که این دیسک اولین حرکت خود را انجام می‌دهد، نمی‌توان از استدلال فوق برای تشخیص میله مقصد استفاده کرد (چرا!؟). استدلال این قسمت را هم که چندان دشوار نیست به شما وا می‌گذاریم و تنها به بیان نتیجه می‌پردازیم: اگر n (تعداد دیسکها) زوج باشد، دیسک ۱ در اولین حرکت به میله کمکی (یعنی میله B)، و در غیراینصورت به میله مقصد (یعنی میله C) منتقل می‌کنیم. به این ترتیب حل مسئله برج هانوی به صورت غیربازگشتی به صورت کامل پیاده‌سازی می‌شود. | ## جمع‌بندی | پیاده‌سازی کد این الگوریتم را نیز به شما وا می‌گذاریم تا با کار روی آن به خوبی بر الگوریتم تشریح شده مسلط شوید.