وبلاگ جامع برای دانشجویان و... کامپیوتر

یا حق  

 نيازمندى كه به تو روى آورده فرستادة خداست ، كسى كه از يارى او دريغ كند، از خدا دريغ كرده، و آن كس كه به او بخشش كند، به خدا بخشيده است

ACM¹ : شركت كردن  برنامه نويسان ماشينهاي حسابگر(كامپيوتر) كه هر ساله برگزار مي شود و به تازگي توسط شركت بزرگ كامپيوتري  اي بي ام(IBM)  حمايت مي شود.  كه اين رقابت ها در سطح بالا و بين المللي اجرا مي شود . هر ساله 2400 تيم به اين مسابقات اعزام ميشوند كه از اين بين 6 تيم به فينال مسابقات راه مي يابند .(رقابت بين المللي برنامه نويسان دانشگاهي²)

تيمها در ماه نوامبر به مسابقات اعزامي شوند و فينال در ماه مارس روي ميدهد.تيم ها شامل 3 نفر مي باشند و مجاز هستند از زبان هاي برنامه نويسي C,C++,JAVA   براي حل مسائل خود استفاده نماييند. براي هر تيم يك كامپيوتر فراهم شده است . يك يا دو عضو ي كه در تيم اعزام شدند مختار هستند نظريه ها را در بين خود رد و بدل نماييند.معمولا يك نفر براي ترجمه سوالات و يك نفر براي نوشتن در كامپيوتر و يك نفر براي فهم سريع مسئله ميكوشد .

مساله برج هانوی (Tower of Hanoi) یکی از مسائل جذاب، قدیمی و مشهور است که به یک مساله کلاسیک در علوم کامپیوتر تبدیل شده است. تاریخچه مساله از این قرار است:

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

شکل زیر نمونه ای با چهار دیسک را نشان می دهد:

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

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

حل مساله:

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

1) دیسک 1 را به میله B منتقل می کنیم:

2) دیسک 2 را به میله C منتقل می کنیم:

3) دیسک 1 را به میله C منتقل می کنیم:

به طور خلاصه می توان نوشت:

1) A --> B

2) A --> C

3) B --> C

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

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

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

• n - 1 دیسک بالایی را با شرایط ذکر شده و به کمک میله C به میله B منتقل می کنیم.
• بزرگترین دیسک را از میله مبدا به میله مقصد حرکت می دهیم.
• n - 1 دیسک را که هم اکنون در میله B هستند با شرایط داده شده به میله مقصد انتقال می دهیم.

می بینیم که توانستیم عملیات جابجا کردن n دیسک را به دو عملیات مشابه ولی با اندازه کمتر و یک عملیات ساده تقسیم کنیم. واضح است که جابجا کردن n - 1 قرص راحتتر از جابجا نمودن 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 - 1 حرکت برای انتقال n - 1 دیسک به میله کمکی، یک حرکت برای انتقال بزرگترین دیسک به میله مقصد، و باز ( T( n - 1 حرکت برای انتقال n - 1 دیسک موجود در میله کمکی به میله مقصد نیاز است. پس می توان نوشت:

T( n ) = 2 T( n - 1 ) + 1

با حل این رابطه بازگشتی داریم:

T( n ) = 2ⁿ - 1

همانطور که مشاهده می کنیم مرتبه اجرایی این الگوریتم ( O( 2ⁿ است که اصلا مرتبه خوبی نیست. اما چاره دیگری نداریم! این روش حداقل تعداد حرکتهای ممکن را می دهد.

برای درک وخامت اوضاع کافی است سعی کنید زمان پایان جهان را محاسبه کنید! اگر فرض کنیم کاهنان با سرعت عمل زیاد توانسته باشند به صورت شبانه روزی و نسل به نسل در هر دو ثانیه یک قرص را جابجا کنند، برای انتقال تمامی 64 قرص به میله مقصد، در حدود 1.169 ترلیون (میلیون میلیون) سال زمان لازم دارند!

در واقع ما از روش Divide and Conquer یا حل و تقسیم برای ارائه راه حل استفاده نموده ایم. اما چون در تقسیم مساله اصلی به دو زیر مساله، اندازه ورودیهای زیر مساله ها نزدیک به اندازه ورودی اصلی هستند، کارایی الگوریتم مطلوب نیست.

منبع : سایت طراحی الگوریتم

نويسنده :محمدعلي مزيدي - جانيس گيليسژي مزيدي

مترجم: دكتر سپيد نام