آبجی
7th August 2010, 04:34 PM
راه‌حل بازگشتي براي يك مساله كلاسيك
يکي از مسائل معروف دنياي برنامه‌نويسي کامپيوتر که جزو قديمي‌ترين آنها هم به‌شمار مي‌رود، مساله برج‌هاي هانوي است.
اين مساله ريشه تاريخي دارد، هانوي يک شهر در ويتنام است، در اين شهر معبدي وجود داشته که سه ميله الماسي در آن قرار داشته است، در يکي از اين ميله‌ها ?? قرص وجود داشته است، مردم بر اين باور بوده‌اند که اگر بتوان تمام قرص‌ها را تحت يک شرايط خاص مانند اين‌که «در هر بار انتقال فقط يک قرص جابه‌جا شود» يا «قرص بزرگ‌تر هيچ وقت روي قرص کوچک‌تر قرار نگيرد»، طوري جابه‌جا کنند که به‌صورت نزولي بر حسب اندازه قرص‌ها مرتب کنند، عمر دنيا به پايان خواهد رسيد.
حال بگذاريد مساله را قدري عاميانه و ساده مطرح و سپس آن را حل کنيم. فرض کنيد مطابق شکل، سه ميله A و B و C وجود دارد.
http://www.jamejamonline.ir/Media/images/1389/05/10/100881956234.jpg
در ميله 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 معروف است، يعني شکستن مساله به مسائل ساده‌تر و کوچک‌تر که حل آنها يک مساله بزرگ‌تر را حل مي‌کند.
بسيار خب، کد اين مساله را بررسي مي‌کنيم.
hanoiTower(integer :
diskNo,character : start, character : temp, character : finish){
if ( diskNo equal 1)
print start “ -- “ finish
else{
hanoiTower(diskNo - 1, start, finish, temp)
print start “ -- “ finish
hanoiTower(diskNo - 1, temp, start, finish)
}
}
ابتدا که اين تابع فراخواني مي‌شود، مقدار 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 است.
يکي از مسائل معروف دنياي برنامه‌نويسي کامپيوتر که جزو قديمي‌ترين آنها هم به‌شمار مي‌رود، مساله برج‌هاي هانوي است.
اين مساله ريشه تاريخي دارد، هانوي يک شهر در ويتنام است، در اين شهر معبدي وجود داشته که سه ميله الماسي در آن قرار داشته است، در يکي از اين ميله‌ها ?? قرص وجود داشته است، مردم بر اين باور بوده‌اند که اگر بتوان تمام قرص‌ها را تحت يک شرايط خاص مانند اين‌که «در هر بار انتقال فقط يک قرص جابه‌جا شود» يا «قرص بزرگ‌تر هيچ وقت روي قرص کوچک‌تر قرار نگيرد»، طوري جابه‌جا کنند که به‌صورت نزولي بر حسب اندازه قرص‌ها مرتب کنند، عمر دنيا به پايان خواهد رسيد.
حال بگذاريد مساله را قدري عاميانه و ساده مطرح و سپس آن را حل کنيم. فرض کنيد مطابق شکل، سه ميله A و B و C وجود دارد.
http://www.jamejamonline.ir/Media/images/1389/05/10/100881956234.jpg
در ميله 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 معروف است، يعني شکستن مساله به مسائل ساده‌تر و کوچک‌تر که حل آنها يک مساله بزرگ‌تر را حل مي‌کند.
بسيار خب، کد اين مساله را بررسي مي‌کنيم.
hanoiTower(integer :
diskNo,character : start, character : temp, character : finish){
if ( diskNo equal 1)
print start “ -- “ finish
else{
hanoiTower(diskNo - 1, start, finish, temp)
print start “ -- “ finish
hanoiTower(diskNo - 1, temp, start, finish)
}
}
ابتدا که اين تابع فراخواني مي‌شود، مقدار 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 است.