چگونه برج‌های هانوی را جابه‌جا کنیم؟

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

حال بگذارید مساله را قدری عامیانه و ساده مطرح و سپس آن را حل کنیم. فرض کنید مطابق شکل، سه میله A و B و C وجود دارد.

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

این بیان ساده‌ای بود از مساله برج هانوی، این راه حل برای سه قرص بود ما باید راهی را ارائه دهیم که علاوه بر این‌که بتواند قرص‌ها را به میله آخر منتقل کند این عمل را با کمترین حرکت انجام دهد.

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

بسیار خب طبق شرایط گفته شده در اولین مرحله باید قرص Nم به میله C منتقل شود. برای رسیدن به این مقصود باید n-1 قرص به کمک میله‌های B و C به میله B منتقل شوند. سپس بعد از انتقال قرص nم به میله سوم دوباره به میله اول برگردند و دوباره این عمل برای قرص n-1م تکرار می‌شود، همانطور که می‌بینید مساله را به چندین مساله کوچک‌تر تقسیم کرده‌ایم به‌طوری که از حل این مساله های کوچک می‌توان اصل مساله را حل کنیم، در ضمن این مساله‌های کوچک خود بسادگی حل می‌شوند، به این روش از حل مساله که معمولا به روش بازگشتی مسائل را حل می‌کنند روش Divide and Conquer معروف است، یعنی شکستن مساله به مسائل ساده‌تر و کوچک‌تر که حل آنها یک مساله بزرگ‌تر را حل می‌کند.

بسیار خب، کد این مساله را بررسی می‌کنیم.

ابتدا که این تابع فراخوانی می‌شود، مقدار diskNo برابر تعداد قرص‌هایی هست که در میله اول وجود دارد،‌ مقدار start کاراکتر A است (چون قرص‌ها در میله A قراردارند)، temp میله کمکی هست که از آن برای انتقال n قرص به میله C استفاده می‌شود، که در مساله ما B است و finish میله C است.

بعد از اجرا شدن تابع، تابع دوباره خود را به‌صورت بازگشتی با پارامتر‌های n-1‌ به عنوان diskNo (چون باید n-1 قرص به از میله A به B بروند) و مقادیر start و finish و temp را به ترتیب با مقادیر A,C,B فراخوانی می‌کند.

مرتبه اجرایی الگوریتم در مرحله اول (T(n-1 باید صرف شود تا n-1 مهره به میله ‌ B منتقل شود و سپس قرص n به میله C‌ منتقل می‌شود، سپس (T(n-1 باید صرف شود تا n-1 مهره به میله A‌ منتقل شوند در نتیجه بر ای مرحله اول داریم T(n) = 2T(n-1) + 1، با همین محاسبه برای مرحله دوم داریم:

T(n-1) = 2T(n-2) + 1 اگر در معادله اول قرار دهیم نتیجه می‌شود T(n) = 4T(n-1) + 3 که اگر این روابط را برای مراحل بعدی تعمیم دهیم نتیجه می‌شود T(n) = power(2,n) – 1 در نتیجه مرتبه این الگوریتم برابر ((O(power(2,n است.