مقدمه ای بر انواع الگوریتم
الگوریتم به مراحل و فرآیندهای متوالی ای اشاره دارد که باید برای حل یک مسئله دنبال شوند. انواع مختلفی از الگوریتم ها برای حل مسائل مختلف ابداع شده و مورد استفاده قرار می گیرند. ولی بعضی از الگوریتم های خلق شده در دنیای کامپیوتر بسیار پرکاربرد هستند. در این سری مقاله ها قصد داریم با این الگوریتم ها آشنا بشویم و مثال ها و تمرین هایی را روی آنها انجام دهیم، تا هرچه بهتر آنها را درک کنیم.
الگوریتم ها فقط برای حل مسائل کامپیوتری نیستند. شخصی که ذهنش با الگوریتم های مختلف آشنا شده است، می تواند در مواجهه با همه ی مسائل و مشکلات زندگی اش از همین روش ها برای حل آنها استفاده کند.
در سری مقالات 6 الگوریتم جادویی قرار است به ترتیب با الگوریتم های زیر آشنا بشویم:
- الگوریتم Brute Force
- الگوریتمGreedy
- الگوریتمRecursive
- الگوریتم Backtracking
- الگوریتم Dynamic programming
- الگوریتمRandomized
الگوریتم Brute Force
ساده ترین و ابتدایی ترین الگوریتم ممکنی که می توان برای حل یک مسئله استفاده کرد، الگوریتم Brute Force نام دارد. ترجمه ی عبارت Brute Force، نیروی بی رحم است ولی به صورت خودمونی تر می توانیم آن را زوری ترجمه اش کنیم! این الگوریتم بر توان محاسباتی تکیه می کند و اصلا خودش را درگیر مسائل بهینه سازی نمی کند.
اینکه می گوییم الگوریتم Brute Force رویکردی ساده برای یک مسئله است، یعنی اولین رویکردی که با دیدن مشکل به ذهن ما می رسد. اگر بخواهیم کمی فنی تر درباره ی این روش صحبت کنیم، تکرار هر امکان موجود برای حل آن مشکل است.
تفکر اصلی که پشت این الگوریتم است جمله ای زیباست که می گوید:
برای ارائه یک راه حل بهینه ابتدا باید حداقل یک راه حل بدست آوریم و سپس سعی کنیم آن را بهینه کنیم.
مثال: فرض کنید کد شما قرار است یک عدد (مثلا رمز عبور یا هر چیز دیگری) چهار رقمی را پیدا کند و شما اعداد 0 تا 9 را برای تولید این عدد دارید. راه حلی که Brute Force پیشنهاد می دهد ساخت و تست تمامی ترکیب های ممکن از 0000 تا 9999 است. و آنقدر ترکیب های جدید را می سازد و امتحان می کند تا ترکیب اصلی را بدست بیاورد. در این مثال ما می توانیم 10000 حالت مختلف داشته باشیم.
پس به طور کلی در حالت Brute Force تعداد حالت های ممکن برای رسیدن به یک پاسخ (در بدترین حالت) m به توان n است. که در این فرمول n تعداد جایگاه هایی است که باید تولید کنیم (در مثال بالا 4 خواهد بود) و m تعداد گزینه هایی است که برای قرار دادن در آن جایگاه ها داریم (در مثال بالا 10 عددی که می تواند در آن 4 خانه بنشیند).
یک مثال کلاسیک در علوم کامپیوتر، مسئله فروشنده دوره گرد (TSP) است. این مسئله به این شکل مطرح می شود که مثلا یک فروشنده باید از 10 شهر در سراسر کشور بازدید کند. چگونه می توان ترتیب بازدید از آن شهرها را به گونه ای تعیین کرد که کل مسافت طی شده به حداقل برسد و از هیچ شهری دوبار عبور نکند؟
راه حل Brute Force برای حل این مسئله، محاسبه مسافت کل برای هر مسیر ممکن و سپس انتخاب کوتاه ترین مسیر است. همانطور که می بینیم، این روش بهینه نیست زیرا می توان بسیاری از مسیرهای ممکن را از طریق الگوریتم های هوشمند حذف کرد.
کد نویسی در این الگوریتم هم خیلی ساده است. برای مثال بیاید کد مثال پیدا کردن یک عدد چهار رقمی خاص را باهم بنویسیم. در زیر شبه کد این برنامه را مشاهده می کنید.
var pin int = 1938
var buildedNumber int
//Brute Force Algorithm
for firstNumber = 0; firstNumber <= 9; firstNumber++ {
for secondNumber = 0; secondNumber <= 9; secondNumber++ {
for thirdNumber = 0; thirdNumber <= 9; thirdNumber++ {
for fourthNumber = 0; fourthNumber <= 9; fourthNumber++ {
buildedNumber = firstNumber*1000 + secondNumber*100 + thirdNumber*10 + fourthNumber
if pin == buildedNumber {
Print("Found It :",buildedNumber)
}
}
}
}
}همانطور که در تکه کد بالا مشاهده می کنید، مجبور شده ایم اعداد زیادی را بسازیم تا بتوانیم به عدد مورد نظرمان برسیم. شما می توانید اجرای این کد با زبان go را در اینجا ببینید.
حالا به عنوان تمرین، مسئله ی زیر را حل کنید و کدی که برای آن می نویسید را در Git قرار دهید و لینک آن را برایمان بفرستید تا کدتان را بررسی کنم.
تمرین الگوریتم Brute Force
تیم سکان آکادمی قرار است برای نوروز از جلوی درب دفتر آن در تهران حرکت کرده و به یزد سفر کند. ولی دوست دارد در راه رسیدن به یزد، سه شهر دیگر را هم ببیند. با توجه به نقشه ی شهر-مسافت زیر، کوتاه ترین مسیر را برای ما پیدا کنید.
