ⓘ برج هانویْ از سه میله و تعدادی دیسک در اندازه‌های متفاوت تشکیل شده‌است که می‌توان آن‌ها را بر میله‌ها جای داد. ..

                                     

ⓘ برج هانوی

برج هانویْ از سه میله و تعدادی دیسک در اندازه‌های متفاوت تشکیل شده‌است که می‌توان آن‌ها را بر میله‌ها جای داد.

                                     

1. تاریخچه و صورت مسئله

در محوطه معبدی در آسیای دور سه میله الماسی قرار داشت که یکی از آن‌ها حاوی تعدادی قرص طلایی بود. کاهنان معبد در تلاش بودند تا قرص‌های طلایی را از آن میله به یکی دیگر از میله‌ها تحت شرایطی انتقال دهند، و باور داشتند که با تمام شدن انتقال قرص‌ها عمر جهان نیز به پایان خواهد رسید! میله اولیه ۶۴ قرص داشت، که بر روی هم به‌طور نزولی بر اساس اندازه‌شان چیده شده‌بودند.

همانند شکل سه میله داریم. یکی از میله‌ها میله مبدأ A، دیگری میله کمکی B و دیگری میله مقصد C است. هدف انتقال تمام دیسک‌ها از میله مبدأ به میله مقصد با رعایت شرایط زیر است:

در هر زمان فقط یک دیسک را می‌توان جابجا نمود. نباید در هیچ زمانی دیسکی بر روی دیسک با اندازه کوچکتر قرار بگیرد.

                                     

1.1. تاریخچه و صورت مسئله حل معادله

هدف ما ارائه الگوریتمی است که کمترین توالی حرکت‌ها را برای انتقال دیسک‌ها به ما بدهد؛ مثلاً اگر n=۲ باشد، توالی حرکت به صورت زیر است:

  • دیسک ۲ را به میله C منتقل می‌کنیم.
  • دیسک ۱ را به میله B منتقل می‌کنیم.
  • دیسک ۱ را به میله C منتقل می‌کنیم.

توجه داشته باشید که بر اساس قانون اول نمی‌توان به غیر از بالاترین دیسک هر میله، به دیسک دیگری از آن دسترسی پیدا کرد.

حال سؤال این است که آیا این مسئله به کمک تکنیک بازگشت قابل حل است؟ اصولاً چه مسائلی را می‌توان بازگشتی حل نمود؟

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

n - ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدأ به میله مقصد حرکت می‌دهیم.n - ۱ دیسک را که هم‌اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n - ۱ قرص راحتتر از جابجا نمودن n قرص است.

                                     

2.1. حل مسئله با زبان‌های برنامه‌نویسی کامپیوتری برج‌های هانوی به زبان پیتون

برنامهٔ زیر تابع راه حل بازگشتی را به زبان برنامه‌نویسی پیتون نشان می‌دهد:

                                     

3. حل مسئله برج هانوی به روش غیربازگشتی

این مسئله علاوه بر روش تابع بازگشتی راه حلهای غیربازگشتی نیز دارد. در بالا به این نتیجه رسیدیم که بهترین راه حل برای جابجا کردن n دیسک ۲n - ۱ حرکت نیاز دارد. در نتیجه مرتبه راه حلهای آن در بهینه‌ترین حالت، چه بازگشتی و چه غیربازگشتی، از مرتبه (O(2n خواهد بود. اما آنچه که راه حل بازگشتی و غیربازگشتی را از هم متمایز می‌کند مرتبه فضای مصرفی آن است. حل بازگشتی مسئله، فراخوانی‌های تو در تو و فضای پشته از مرتبه (O(n نیاز دارد. در حالی که می‌توان با استفاده از روش غیربازگشتی این مرتبه را به (O(1 کاهش داد. البته این مسئله تنها دلیل بررسی روش غیربازگشتی نیست. تبدیل مرتبه مصرف فضا از (O(n به (O(1 زمانی که مرتبه اجرایی الگوریتم (O(2n است چندان قابل توجه نیست. دلیل دیگر می‌تواند این باشد که برخی زبانهای برنامه‌نویسی از فراخوانی بازگشتی توابع پشتیبانی نمی‌کنند و مجبور به استفاده ار روش‌های غیربازگشتی هستند. اما دلیل اصلی این است که با بررسی این روش‌ها تمرین کوچکی برای تبدیل الگوریتمهای بازگشتی به غیربازگشتی انجام می‌دهیم.

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

  • روش اول

حل مسئله برج هانوی را می‌توان معادل پاسخ دادن به این سؤال دانست که: در هر مرحله کدام دیسک به کدام میله منتقل می‌شود؟

کدام دیسک؟

فرض کنیم دیسکهایی به شعاع y,x و z که رابطه x
                                     
  • Thăng Long مجموعه ای از بناهای تاریخی سلطنتی در مرکز شهر هانوی ویتنام است. این مجموعه دژ هانوی نیز نامیده می شود. محوطه سلطنتی اولین بار در زمان سلسله
  • از ژانویه جای خود را برج Keangnam هانوی داد. این برج عملکرد اداری مرکز خرید و رستوران را دارد. در بالای این برج یک سکو که همان پد بالگرد است
  • همچنین با نام مستعار N. Claus de Siam آناگرام لوکاس د آمینز معمای برج هانوی را طرح کرد و برای اولین بار برای توصیف نقطه بازی در سال آن را منتشر
  • مسئله جهان جارو مسئله چند وزیر دوز معمای کشیش ها و آدمخوارها شطرنج برج هانوی و دیگر چیزها. مسئله منشی Stuart J. Russell, Peter Norvig 2010 Artificial
  • بازگشتی راه حل روشنی نمی توان یافت اما برج های هانوی از این قاعده مستثنی است: راه حل مستقیم برای مسئله برج های هانوی در اصطلاح کامپیوتری ساختمان داده به
  • اسلام آباد استانبول فرانکفورت ابوظبی دوحه قاهره دهلی نو بانکوک کلمبو هانوی جاکارتا و لس آنجلس می باشد. دفتر مرکزی این شرکت در محله نیشی منطقه ویژه
  • جداول کلمات بازی های مهارتی حرکتی Game of Physical Skill مانند جنگا و برج هانوی کاپوچینو بازی های نقش آفرینی Role - playing game بازی است که در آن افراد
  • جزیره ماهه واقع شده است. جمعیت این شهر نفر می باشد. جیبوتی - جیبوتی هانوی - ویتنام World Weather Information Service - Victoria World Meteorological
  • پارامترهای چندریختی را معرفی کرد. از نسخه 6.0 زبان کاملا شیءگرا شد. در مثال برج هانوی موتور استنتاج پرولوگ دریافت که چگونه یک پشته شامل تعدادی از دیسک های