مساله برج هانوی

[™Ali]

با سلام خدمت دوستان

یه مقاله رو از ویکی پدیا درباره مساله جذاب برج هانوی واستون میذارم و در ادامه اگر کمک کنید چند تا سورس کد واسه حلش بدیم بیرون ! :11():

===============================

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

مقدمه

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


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

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

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





حل مساله

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



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

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


برای اینکه مساله‌ای بتواند با روش بازگشتی حل شود باید یک ویژگی اساسی داشته باشد. مساله اصلی (مساله‌ای که به ما داده می‌شود) قابل خرد شدن به زیر مساله‌هایی از همان نوع مساله اصلی باشد، به شرطی که اندازه زیر مساله‌های ایجاد شده کمتر باشد. آنگاه می‌توان امیدوار بود که آن را به طور بازگشتی حل کرد! این ویژگی در مورد مساله برج هانوی صدق می‌کند. ایده اصلی این است که توجهمان را به جای حرکت بالاترین دیسک، روی پایین ترین دیسک میله متمرکز کرده، و مراحل زیر را طی می‌کنیم:
n - ۱ دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می‌کنیم. بزرگترین دیسک را از میله مبدا به میله مقصد حرکت می‌دهیم. n - ۱ دیسک را که هم اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می‌دهیم. می‌بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n - ۱ قرص راحتتر از جابجا نمودن n قرص است.



تابع بازگشتی زیر به زبان ++C ترتیب حرکت ها را چاپ می‌کند:



void hanoi ( int nDisk, char start, char temp, char finish )

{

if ( nDisk == 1 )

cout << start << " --> " << finish << endl;

else

{

hanoi ( nDisk - 1, start, finish, temp );

cout << start << " --> " << finish << endl;

hanoi ( nDisk - 1, temp, start, finish );

}

}






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


برای این که به کاهنان کمک کنیم، باید دستور ('hanoi(64, ‘A’, ‘B’, ‘C را اجرا کنیم. ولی چه زمانی طول می‌کشد تا این دستور اجرا شود؟ در حالت کلی می‌خواهیم بدانیم اگر تعداد دیسک‌ها n باشد، کمترین تعداد حرکت برای جابجا نمودن دیسک‌ها چقدر است؟
در ابتدا باید بررسی کنیم که آیا تابع بازگشتی فوق کمترین تعداد حرکت را چاپ می‌کند؟ جواب مثبت است. زیرا واضح است که برای جابجا کردن بزرگترین دیسک از پایین میله A، بقیه دیسک‌ها باید در میله B باشند. فقط در این صورت این دیسک جابجا می‌شود. در فراخونی‌های بعدی دیسک دوم از نظر بزرگی جابجا می‌شود و الی آخر. پس در این فراخوانی‌ها جابجایی بیهوده‌ای صورت نمی‌گیرد. همچنین توالی حرکت‌ها برای هر n منحصر بفرد است. یعنی برای یک n دو توالی متمایز از جابجایی‌ها وجود ندارد که تعداد جابجایی آن‌ها کمتر یا مساوی این حالت باشد.
حال به مساله مرتبه اجرایی مساله می‌پردازیم: فرض کنیم (T(n تعداد حرکت‌های لازم جهت انتقال n دیسک به مقصد باشد. بر اساس توضیحات فوق (T(n - ۱ حرکت برای انتقال n - ۱ دیسک به میله کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله مقصد، و باز (T(n - ۱ حرکت برای انتقال n - ۱ دیسک موجود در میله کمکی به میله مقصد نیاز است. پس می‌توان نوشت:
T(n) =2 T(n - ۱) + 1
با حل این رابطه بازگشتی داریم:
T( n ) = 2n-1
همانطور که مشاهده می‌کنیم مرتبه اجرایی این الگوریتم (O(2n است که هرچند مرتبه مناسبی نیست، این روش حداقل تعداد حرکتهای ممکن را می‌دهد.
اگر فرض کنیم کاهنان با سرعت عمل زیاد توانسته باشند به صورت شبانه روزی و نسل به نسل در هر دو ثانیه یک قرص را جابجا کنند، برای انتقال تمامی ۶۴ قرص به میله مقصد، در حدود ۱٫۱۶۹ ترلیون (میلیون میلیون) سال زمان لازم دارند!
در واقع ما از روش Divide and Conquer یا حل و تقسیم برای ارائه راه حل استفاده نموده‌ایم. اما چون در تقسیم مساله اصلی به دو زیر مساله، اندازه ورودی‌های زیر مساله‌ها نزدیک به اندازه ورودی اصلی هستند، کارایی الگوریتم مطلوب نیست.




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


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




روش اول:

حل مساله برج هانوی را می‌توان معادل پاسخ دادن به این سوال دانست که: در هر مرحله کدام دیسک به کدام میله منتقل می‌شود؟
+ کدام دیسک؟ فرض کنیم دیسکهایی به شعاع y ،x و z که رابطه x < y < z را با هم دارند، کوچکترین دیسک هر میله باشند. به عبارت دیگر این سه دیسک، بالاترین دیسکهای میله‌ها هستند که قابلیت جابجایی دارند. اگر میله‌ای شامل هیچ دیسکی نباشد، دیسکی با شعاع بی نهایت را برای آن در نظر می گیریم. حال به استدلالهای منطقی زیر توجه کنید:
استدلال 1: x برابر 1 است. چرا که بر اساس قوانین حاکم بر مساله، هیچ دیسکی نمی‌تواند روی دیسک 1 قرار بگیرد. در نتیجه این دیسک همیشه بالاترین دیسک موجود در یکی از میله‌ها است.
استدلال 2: در اولین مرحله دیسک 1 جابجا می‌شود. در آغاز همه دیسکها روی یک میله قرار دارند که دیسک ۱ بالاترین دیسک آن است.
استدلال 3: دیسکهایی که طی دو مرحله متوالی جابجا می‌شوند حتما متمایز هستند. این مساله از بهینه بودن راه حل ما ناشی می‌شود. اگر قرار باشد طی دو مرحله متوالی یک دیسک خاص را جابجا کنیم، می‌توانیم دو مرحله را با هم ادغام کرده و کل جابجایی را یکجا انجام دهیم.
استدلال 4: با توجه به قوانین حاکم بر مساله، دیسک z نمی‌تواند حرکت کند. چرا که دیسکهای x و y هر دو از آن کوچکتر هستند.
استدلال 2 می‌گوید که اولین حرکت همیشه با دیسک 1 است. استدلال 3 می‌گوید حرکت بعدی با دیسکی غیر از دیسک 1 است. استدلال 4 می‌گوید این دیسک نمی‌تواند بزرگترین دیسک موجود در بالای میله‌ها باشد. پس در مرحله بعدی دیسک y جابجا خواهد شد. و بالاخره حرکت بعدی باز هم با دیسک 1 است (چرا؟).
پس با بررسی منطقی خود به این نتیجه رسیدیم که دیسک 1 و دیسکی که بزرگترین دیسک در آن مرحله نیست، به صورت متناوب جابجا می‌شوند. مراحل با شماره فرد برای دیسک 1، و مراحل با شماره زوج برای دیسک y.
+ کدام میله؟ حال که می دانیم در هر مرحله کدام دیسک جابجا می‌شود، به سراغ میله مقصد می رویم. در مراحل زوج که دیسک y منتقل خواهد شد، تشخیص میله مقصد بسیار آسان است. چرا که روی یکی از میله‌ها دیسک 1 قرار دارد که دیسک y نمی‌تواند روی آن قرار بگیرد. در نتیجه به تنها میله باقی مانده (میله دیسک z) منتقل می‌شود. در مورد مراحلی هم که دیسک 1 قرار است جابجا شود، می‌توان اینطور استدلال کرد:
فرض کنیم دیسک 1 روی میله A قرار داشته باشد و آن را به میله C منتقل کنیم. در مرحله بعدی دیسک y جابجا می‌شود. و در مرحله بعد باز هم دیسک ۱ باید جابجا شود. حال اگر این دیسک را به میله A بازگردانیم، به نوعی کار اضافی و بازگشت به عقب انجام داده ایم. برای آشکار شدن این موضوع کافی است مساله برج هانوی را با دو دیسک حل کنید، و در حرکت دوم دیسک 1، آنرا به میله‌ای بازگردانید که از آن آمده بود. پس می‌توان گفت در حرکتهای متوالی، دیسک شماره 1 به میله‌ای حرکت می‌کند که از آن به میله فعلی خود نیامده است. این مساله نه تنها در مورد دیسک 1، که در مورد همه دیسکها صادق است. یعنی همه دیسکها در حرکتهای خود به سمت میله‌ای می‌روند که در حرکت قبلی خود از آن نیامده اند. اما لحاظ کردن این شرط برای این دیسکها لازم نیست. چرا که در هر مرحله، تنها یک انتخاب برای حرکت خود دارند.
تنها مساله باقی مانده، میله مقصد دیسک 1 در اولین حرکت خود است. زمانی که این دیسک اولین حرکت خود را انجام می‌دهد، نمی‌توان از استدلال فوق برای تشخیص میله مقصد استفاده کرد (چرا!؟). استدلال این قسمت را هم که چندان دشوار نیست به شما وا می گذاریم و تنها به بیان نتیجه می پردازیم: اگر n (تعداد دیسکها) زوج باشد، دیسک 1 در اولین حرکت به میله کمکی (یعنی میله B)، و در غیراینصورت به میله مقصد (یعنی میله C) منتقل می کنیم.
به این ترتیب حل مساله برج هانوی به صورت غیربازگشتی به صورت کامل پیاده سازی می‌شود. حال می دانیم که در هر مرحله کدام دیسک به کدام میله منتقل می‌شود. تعداد مراحل هم همواره برابر ۲n - ۱ است. پیاده سازی کد این الگوریتم را نیز به شما وا می گذاریم تا با کار روی آن به خوبی بر الگوریتم تشریح شده مسلط شوید.






روش دوم:

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


‎




void hanoi ( int nDisk, char start, char temp, char finish )
{
int max = nDisk;
char dest = finish;
int disk = max;
while( true )
{
while( disk > 0 )
{
if( moving disk succeeds )
{
if( disk == max )
{
max--;
if( max == 0 )
{
return;
}
}
dest = the final place of max;
}
else
{
dest = the alternative place between dest and the current place of disk;
}
disk--;
}
p and q = the places different of dest;
disk = the smaller of the disks on top of p and q;
dest = the place between p and q with greater disk on top;
}
}



در پایان توجه داشته باشید که دو روش ذکر شده، تنها روشهای پیاده سازی غیربازگشتی حل مساله نیستند. :1. (21):




اگر مقاله رو کامل خوندید متوجه زیبایی مسئله شدید :1. (38):

[™Ali]

سورس کد حل مسئله برج هانوی سی شارپ :




using System;
class TowerOfHanoi
{
int m_numdiscs;
public TowerOfHanoi()
{
numdiscs = 0;
}

public TowerOfHanoi(int newval)
{
numdiscs = newval;
}

public int numdiscs
{
get
{
return m_numdiscs;
}
set
{
if (value > 0 )
m_numdiscs = value;
}
}

public void movetower (int n, int from, int to, int use)
{
if (n > 0)
{
movetower (n-1, from, use, to);
Console.WriteLine("Move disk {0} from tower {1} to tower {2}",n,from,to);
movetower (n-1, use, to, from);
}
}

}
class TowersOfHanoiApp
{
public static int Main()
{
TowerOfHanoi T;
T = new TowerOfHanoi();
string cnumdiscs;
Console.Write("Enter the number of discs: ");
cnumdiscs = Console.ReadLine();
T.numdiscs = Convert.ToInt32(cnumdiscs);
T.movetower(T.numdiscs, 1, 3, 2);

Console.WriteLine("\n\nHit ENTER to continue....");
string str = Console.ReadLine();
return 0;
}

}


تگ ها : برج هانوی ، دانلود ، برنامه ، Application , سورس کد ، سی شارپ ، C# ، سی پلاس پلاس ، C++ ، ++C ، حل مسئله ، بحث ، برنامه نویسی ، C ، سی ، Cpp ، Cs , Csharp . Programming , Coding , Visual Studio