مساله برج هانوي يکي از مسائل جذاب، قديمي و مشهور است که به يک مساله کلاسيک در علوم رايانه تبديل شده‌است.

[ويرايش] تاريخچه

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


نمونه‌اي از برج هانوي

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

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


[ويرايش] حل مساله

هدف ما ارائه الگوريتمي است که کمترين توالي حرکت‌ها را براي انتقال ديسک‌ها به ما بدهد. مثلا اگر n=? باشد، توالي حرکت به صورت زير است:
حل مساله برج هانوي

    * ديسک ? را به ميله B منتقل مي‌کنيم
    * ديسک ? را به ميله C منتقل مي‌کنيم
    * ديسک ? را به ميله C منتقل مي‌کنيم

حل مساله برج هانوي


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

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

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

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

براي مثال فراخواني تابع به شکل ('hanoi(?, ‘A’, ‘B’, ‘C مساله برج هانوي را با سه ديسک که در ميله A قرار دارند و با کمک ميله B به ميله C منتقل خواهد شد، حل مي‌کند.


درختي که ترتيب اجراي دستورها را نشان مي‌دهد

براي اين که به کاهنان کمک کنيم، بايد دستور ('hanoi(??, ‘A’, ‘B’, ‘C را اجرا کنيم. ولي چه زماني طول مي‌کشد تا اين دستور اجرا شود؟ در حالت کلي مي‌خواهيم بدانيم اگر تعداد ديسک‌ها n باشد، کمترين تعداد حرکت براي جابجا نمودن ديسک‌ها چقدر است؟

در ابتدا بايد بررسي کنيم که آيا تابع بازگشتي فوق کمترين تعداد حرکت را چاپ مي‌کند؟ جواب مثبت است. زيرا واضح است که براي جابجا کردن بزرگترين ديسک از پايين ميله A، بقيه ديسک‌ها بايد در ميله B باشند. فقط در اين صورت اين ديسک جابجا مي‌شود. در فراخوني‌هاي بعدي ديسک دوم از نظر بزرگي جابجا مي‌شود و الي آخر. پس در اين فراخواني‌ها جابجايي بيهوده‌اي صورت نمي‌گيرد. همچنين توالي حرکت‌ها براي هر n منحصر بفرد است. يعني براي يک n دو توالي متمايز از جابجايي‌ها وجود ندارد که تعداد جابجايي آن‌ها کمتر يا مساوي اين حالت باشد.

حال به مساله مرتبه اجرايي مساله مي‌پردازيم: فرض کنيم (T(n تعداد حرکت‌هاي لازم جهت انتقال n ديسک به مقصد باشد. بر اساس توضيحات فوق (T(n - ? حرکت براي انتقال n - ? ديسک به ميله کمکي، يک حرکت براي انتقال بزرگترين ديسک به ميله مقصد، و باز (T(n - ? حرکت براي انتقال n - ? ديسک موجود در ميله کمکي به ميله مقصد نياز است. پس مي‌توان نوشت:

T(n) = ? T(n - ?) + ?T(n) = ? T(n - ?) + ?