حل مسئله برج هانوی
توضیحات قوانین بازی در این پست
------------------------------------------
یکی از روش های حل این بازی استفاده یک الگوریتم بازگشتی است که ما ازش استفاده میکنیم .
خیلی وقت ها تو زندگی مون بهینه تر و بهتر است که مشکلات بزرگ رو تا جایی که میتونیم به مشکلات کوچیک تر تقسیم کنیم و هرکدومشون رو جداگانه حل کنیم تا نهایتا مشکل بزرگ که تشکیل شده از تمام این ریزمشکل ها بود حل بشه .
الگوریتم های بازگشتی دقیقا همینطور هستند . یعنی طوری که ما برای حل یک مسئله به روش بازگشتی میایم مسئله رو تا جایی که میشه به ریز مشکلات کوچیکتر تقسیم میکنیم که به سادگی و با روشی یکسان با باقی ریز مشکلات حل میشن ( اما حل هر کدوم نتیجه متفاوتی از باقی ریزمشکل ها داره ) حالا با حل تمام این ریزمشکلات و ترکیب نتیجه ان ها به جواب مشکل بزرگ اصلی و اولیه میرسیم .
برای حل برج هانوی هم از همین روش استفاده میکنیم .
ابتدا برای سادگی بیاین n یا تعداد دیسک رو برابر ۳ در نظر بگیریم یعنی ما با چنین بازی طرف هستیم :
هدف اینه که تمام دیسک های میله مبدا (A) به میله هدف (C) منتقل بشن . این هدف بزرگیه باید بشکونیمش به اهداف کوچکتر . قبول دارید انتقال تمام دیسک ها از میله A به C رو میتونیم به این سه زیرمشکل زیر تقسیم کنیم ؟ :
۱ - انتقال دو دیسک بالایی میله A به میله کمکی (B)
۲ - انتقال دیسک کفی (پایین ترین دیسک) میله A به میله هدف (C) .
۳ - انتقال اون میله ها که برده بودیم روی میله B به روی میله کفی که گذاشتیم روی میله C
این سه مرحله رو در سه تصویر زیر انجام دادم ببینید :
خب ظاهرا تقسیم بندی منطقی به نظر میرسه و اینکه واقعا کار میکنه ! .
حالا بیاین بی جنبه بازی در بیاریم و به قولی شورشو از مزه ببریم . یعنی تا میتونیم هی مسئله رو تقسیم کنیم به این سه مرحله . چجوری ؟
یه بار دیگه اون سه مرحله بالا رو در نظر بگیرید . مرحله ۱ این بود که دو دیسک بالایی A رو به B ببریم . خب این خودش یه برج هانوی جدا شد براخودش با n=2 چون قرار ۲ دیسک رو انتقال بدیم به میله هدف که B هست و اینجا میله C میله کمکی میشه ( فرض میکنیم دیسک کفی تو میله Aوجود نداره اصلا). یعنی چنین برج هانوی میشه :
خود این برج هانوی رو باز طبق اون تقسیم بندی مشکنیم . طبق تقسیم بندیمون باید اول دیسک بالایی میله A رو ببریم به میله کمکی (C). دیسک کفی میله A رو ببریم روی میله هدف (B)و سپس اون دیسک رو از میله کمکی بذاریم روی کفیه .
حالا بیاین برگردیم به اون هانوی اصلیه با n=3 . الان مرحله دو تقسیم بندیش رو انجام دادیم یعنی تمام دیسک های رویی میله A بجز اون کفیه رو بردیم روی B . حالا راحت با یه حرکت دیسک کفی میله A رو میبریم روی C .
حالا کافیه طبق الگوریتممون اون دو تا دیسک رو از میله کمکی B برداریم بذاریم روی میله C . اینجا این باز خودش یه زیرمسئله دیگه میشه که قرار با n=2 حلش کنیم . قرار دو دیسک رو از میله B به میله C به کمک میله A انتقال بدیم . یعنی زیر مسئله مون اینطوری میشه :
حالا بیاید دوباره تقسیمش کنیم . اول دیسک رویی رو میبریم روی میله کمکی ،بعد دیسک کفی رو میبریم رو میله هدف و سپس دیسک روییه رو از میله کمکی میبریم رو هدف میذاریم :
ناگهان به خودمون میایم و میبینیم اون برج هانوی اصلیه حل شده !
الگوریتم بازگشتی حل برج هانوی همینه . تقسیمش کنیم به مسئله برج های هانوی کوچیکتر و اونقدر این تقسیم بندی رو انجام بدیم تا اینقدر آسون بشه که برج هانوی کوچیکه با انتقال یکی دوتا دیسک حل بشه حالا وقتی تمام این برج هانوی کوچیکارو حل کنیم اون مسئله اصلی هم حل میشه
تقسیم بندیمون هم به این شکل بود که برای n تا دیسک ،اول n-1 دیسک بالایی از میله مبدا رو میبریم به میله کمکی . سپس دیسک کفی میله مبدا رو میبریم رو میله هدف . حالا n-1 دیسک رو از میله کمکی بر میداری و میذاریم روی میله هدف و به این صورت هی و دائما مسئله میشکنه و کوچیک میشه تا حلش راحت بشه .
اگر یادتون باشه گفتیم کمترین تعداد حرکت برای حل n دیسک 2n-1 هستش . این فرمول از کجا اومده ؟
فرض کنید تابع f(x) رو داریم که تعداد انتقال دیسک یا حرکت مورد نیاز برای حل برج هانوی با n=xدیسک رو به ما در جواب میده . تابع f(x) یک تابع برگشتی میشه . میدونیم که اگر n=1 باشه ، تعداد حرکت مورد نیاز ۱ خواهد بود و این خیلی واضحه . فقط یه انتقال میدیم .
حالا اگر n بزرگتر از ۱ باشه چی ؟ رجوع کنیم به الگوریتم تقسیممون :
۱ - n-1 دیسک بالایی رو انتقال بده به میله کمکی ( f(n-1) حرکت)
۲ - میله کفی رو انتقال بده به میله هدف (۱ انتقال )
۳ - n-1 دیسک بالایی رو از میله کمکی ببر رو میله هدف ( f(n-1) حرکت)
اگر تعداد حرکت های این سه مرحله رو جمع کنید میشه :
2f(n-1) + 1
پس تابع f اینشکلی تعریف میشه :
اگر جواب های f رو برای x های ۱ و ۲و ۳ و۴ و ... به ترتیب بنویسیم و بخوایم الگویابی کنیم داخلشون به این صورت میشه :
همینطور که میبنیدی تمام جمله های f یکی کمتر از توان های ۲ هستند و این فرمول 2n-1 دقیقا همینجاست
حالا میتونید دقیقا همین الگوریتم رو برای هر n دلخواه پیاده سازی کنید .
دوباره اگر دوست داشتید میتونید به سایت زیر مراجعه کنید و الگوریتم رو برای n های دلخواه امتحان کنید :
https://www.mathsisfun.com/games/towerofhanoi.html
طبیعیه که دفعه اول که میخواید حل کنید سخت باشه و نتونید یه جاهایی الگوریتم رو درک نکنید و نتونید باهاش پیش بریم .
امیدوارم لذت برده باشید .
۴
۰
خیلی خوب توضیح میدی با ذوق تا آخر خوندم