حسام حداد تکنولوژی، برنامه‌نویسی، هوش مصنوعی

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

کجا نمیتوان از الگوریتم حریصانه استفاده کرد؟

گراف بدون جهت زیر را در نظر بگیرید.

برای پیدا کردن کوتاه ترین مسیر بین گره A   و D اگر به صورت حریصانه عمل کنیم  یال A-C از یال A-B  دارای وزن کمتری میباشد پس یال A-C  را در نظر میگیریم ولی در ادامه مجبوریم از تنها انتخاب یعنی C-D استفاده کنیم و به گره  D برسیم. طول مسیر 9 + 15 یعنی 24 میباشد اما در صورتی که در ابتدا یال A-B را انتخاب کرده بودیم  با اینکه نسبت به A-C در مرحله اول انتخاب بدتری بود اما در ادامه مسیر بهینه تر و کوتاه تری را داشتیم.
پس نمیتوان از الگوریتم حریصانه در پیدا کردن کوتاه ترین میسر بین دو گره استفاده کرد برای اینکار میتوان از الگوریتم هایی مثل Dijkstra استفاده کرد که به این مقاله مربوط نمیشود.
اما باید بدانیم که اگر در مسئله ای الگوریتم حریصانه درست باشد بی شک بهترین راه حل برای آن مسئله حریصانه است چون نسبت به بقییه الگوریتم ها دارای پیچیده گی زمانی کمتری میباشد.
ما بنا بر روال همیشگی امروز یک مسئله ICPC – ACM را برای مثال انتخاب کرده ایم که در حل آن از الگوریتم حریصانه میتوان استفاده کرد.
ابتدا متن سوال را مرور میکنیم

ادامه مطلب