دنیای الگوریتم‌ها: سرزمینِ استراتژی‌ها و تاکتیک‌ها

algorithm
تصویر یاسر دهقان

یاسر دهقان

دنیای الگوریتم‌ ها، سرزمینی پهناور و پرماجراست که در آن، برنامه‌نویسان همچون سرداران جنگی، برای حل مسائل و غلبه بر چالش‌ها، از استراتژی‌ها و تاکتیک‌های گوناگونی بهره می‌برند. درست همانطور که یک ژنرالِ پیروز، از میان انبوهی از ترفندها، بهترین را برای نبرد انتخاب می‌کند، یک برنامه‌نویس نیز باید با تسلط بر الگوریتم‌های مختلف، مناسب‌ترین را برای حل مسئله پیش روی خود برگزیند.

در این سرزمین پهناور، الگوریتم‌ها نقش سربازان را ایفا می‌کنند که هر کدام توانایی‌ها و وظایف خاص خود را دارند. برخی از آن‌ها در مرتب‌سازی داده‌ها مهارت دارند، برخی دیگر در جستجو و برخی دیگر در بهینه‌سازی. انتخاب الگوریتم مناسب، همانند انتخاب سربازانِ کارآزموده، ضامن موفقیت در نبرد با چالش‌هاست.

در اینجا، به تعدادی از این  استراتژی های حل مسئله به صورت خلاصه  اشاره می‌کنیم. اگر می خواهید در این موراد اطلاع بیشتری کسب کنید می توانید به کتاب های مختلف طراحی الگوریتم سر بزنید.

مطالب مرتبط

الگوریتم و اهمیت آن در برنامه نویسی

استراتژی های مختلف برای حل مسائل

 

iterative (تکرارشونده):

در این روش، گویی مجموعه‌ای از دستورالعمل‌ها بارها و بارها اجرا می‌شوند تا به نتیجه‌ی دلخواه برسیم. این تکرارها  به Iteration معروف هستند.حلقه‌های while و for از جمله ابزارهای اصلی پیاده‌سازی الگوریتم‌های تکراری هستند.

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

recursive (بازگشتی):

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

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

Brute Force:

یکی از ساده‌ترین و در عین حال ابتدایی‌ترین استراتژی‌ برای جل مسائل الگوریتمی، Brute Force می باشد. این روش که معمولاً توسط مبتدیان در طراحی الگوریتم‌ها مورد استفاده قرار می‌گیرد، بر پایه‌ی جستجوی بی‌وقفه تمام حالات ممکن برای یافتن پاسخ مسأله بنا شده است.

فرض کنید با مسأله‌ای روبرو هستیم که باید در میان انبوهی از گزینه‌ها، گزینه‌ی درست را پیدا کنیم. استراتژی Brute Force،تک به تک تمام گزینه‌ها را چک می‌کند تا سرانجام به گزینه‌ی مورد نظر برسد.

مزایا:

  • سادگی: این روش به دلیل عدم نیاز به پیچیدگی‌های ریاضی یا ساختارهای داده‌ی خاص، بسیار ساده و قابل فهم است.

معایب:

  • کارایی پایین: در مسائلی که تعداد حالات ممکن بسیار زیاد باشد، جستجوی تک تک آن‌ها می‌تواند بسیار زمان‌بر و غیرقابل‌تحمل باشد.

بهبود الگوریتم‌های Brute Force:

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

Backtracking (پس گرد)

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

 استراتژی Backtracking، این کار را به صورت گام به گام و با بررسی هر یک از خانه‌های صفحه انجام می‌دهد. در هر مرحله، یک مهره را در یکی از خانه‌های خالی قرار می‌دهیم و سپس بررسی می‌کنیم که آیا این چیدمان قوانین را نقض می‌کند یا خیر. اگر چیدمان مغایر با قوانین باشد، به مرحله‌ی قبل باز می‌گردیم (پس‌گرد) و مهره را در خانه‌ی دیگری قرار می‌دهیم.این کار را تا جایی انجام می دهیم تا به جواب خود برسیم.

Heuristics

در یک بازی شطرنج با 32 مهره و 64 خانه، بعد از چهار مرحله بازی، همچنان 288 میلیون موقعیت احتمالی برای تغییر مکان مهره‌ها وجود دارد. حتی حرفه‌ای‌ترین شطرنج‌بازان نیز نمی‌توانند بهترین حرکت را پیدا کنند و آن را انجام دهند. آنها بر اساس تجربه خود، حرکتی را انجام می‌دهند که به نظر خودشان خوب است. ما می‌توانیم از همین روش برای حل مسائل الگوریتمی نیز استفاده کنیم. استراتژی Heuristics، روشی برای حل مسئله است که جوابی برای مسئله ارائه می‌دهد، اما لزوماً بهترین جواب نیست. می‌توان از این روش در مسائلی استفاده کرد که حل آنها با روش‌های Brute Force و Backtracking به دلیل کندی و عدم کارایی دشوار است.

Divide and Conquer

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

ارسال دیدگاه