چه موقع از الگوریتم های حریص استفاده کنید - و چه موقع از آنها جلوگیری کنید [با مشکلات مثال]

خوزه جی. رودریگز

الگوریتم های حریص سعی می کنند با استفاده از بهترین انتخاب در دسترس در هر مرحله ، راه حل بهینه را پیدا کنند.

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

به همین ترتیب ، مشکلاتی وجود دارد که الگوریتم های حریص بهترین راه حل را ارائه نمی دهند. در واقع ، آنها ممکن است بدترین راه حل ممکن را ارائه دهند.

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

در این مقاله ، من در مورد الگوریتم های حریص و استفاده از این استراتژی حتی اگر تضمین نشود که یک راه حل بهینه پیدا خواهید کرد ، می نویسم.

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

توجه: بیشتر الگوریتم ها و مشکلاتی که در این مقاله در مورد آنها بحث می کنم شامل نمودارها است. خوب است اگر با نمودارها آشنا باشید تا از این پست بیشترین استفاده را کنید.

الگوریتم های حریص چگونه کار می کنند

الگوریتم های حریص همیشه بهترین گزینه موجود را انتخاب می کنند.

به طور کلی ، آنها از نظر محاسباتی ارزان تر از سایر خانواده های الگوریتم هایی مانند برنامه نویسی پویا یا نیروی بی رحمانه هستند. این امر به این دلیل است که آنها فضای راه حل را بیش از حد کشف نمی کنند. و به همین دلیل ، آنها بهترین راه حل برای بسیاری از مشکلات را پیدا نمی کنند.

اما مشکلات زیادی وجود دارد که با یک استراتژی حریص قابل حل است ، و در این موارد که استراتژی دقیقاً بهترین راه برای پیشبرد است.

یکی از محبوب ترین الگوریتم های حریص ، الگوریتم Dijkstra است که مسیر را با حداقل هزینه از یک راس به دیگران در یک نمودار می یابد.

این الگوریتم با رفتن همیشه به نزدیکترین راس ، چنین مسیری را پیدا می کند. به همین دلیل می گوییم این یک الگوریتم حریص است.

این شبه کد برای الگوریتم است. من با G نمودار و با S منبع را نشان می دهم.

Dijkstra (G ، S): مسافت

پس از اجرای این الگوریتم ، لیستی از مسافت ها را دریافت می کنیم به گونه ای که مسافت [u] حداقل هزینه برای رفتن از گره S به گره U است.

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

مثال دیگری که برای معرفی مفاهیم استراتژی حریص استفاده می شود ، کوله پشتی کسری است.

در این مشکل ، مجموعه ای از موارد را داریم. هر مورد دارای وزن WI بیشتر از صفر است و سود Pi نیز بیشتر از صفر است.

ما یک کوله پشتی با ظرفیت W داریم و می خواهیم آن را به گونه ای پر کنیم که حداکثر سود را بدست آوریم. البته ، ما نمی توانیم از ظرفیت کوله پشتی فراتر برویم.

در نسخه کسری مشکل Knapsack ، می توانیم کل شیء یا فقط کسری از آن را بگیریم. هنگام گرفتن کسری 0

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

تعداد مشکلاتی که می توانیم با استفاده از الگوریتم های حریص حل کنیم بسیار زیاد است. اما تعداد مشکلاتی که نمی توانیم از این طریق حل کنیم حتی بزرگتر است. بخش بعدی در مورد مشکلات دوم است - مواردی که نباید از این طریق حل کنیم.

وقتی حریص بودن بدترین است

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

اما ، همانطور که گفتم ، الگوریتم Dijkstra در نمودارهایی با لبه های منفی کار نمی کند.

و مشکل حتی بزرگتر است. من همیشه می توانم یک نمودار با لبه های منفی بسازم به گونه ای که راه حل Dijkstra به همان اندازه که می خواستم بد خواهد بود! مثال زیر را که از stackoverflow استخراج شده است در نظر بگیرید

Dijkstra's algorithm fails to find the distance between A and C . It finds d(A, C) = 0 when it should be -200. And if we decrease the value of the edge D >ب ، ما مسافتی را بدست می آوریم که حتی از حداقل فاصله واقعی دورتر خواهیم بود.

به همین ترتیب ، هنگامی که ما نمی توانیم اشیاء را در مشکل Knapsack (مشکل 0-1 Knapsack) بشکنیم ، راه حلی که هنگام استفاده از یک استراتژی حریص به دست می آوریم نیز می تواند بسیار بد باشد. ما همیشه می توانیم ورودی را به مسئله بسازیم که باعث می شود الگوریتم حریص بد ناکام باشد.

مثال دیگر مشکل فروشنده مسافرتی (TSP) است. با توجه به لیستی از شهرها و فاصله بین هر جفت شهر ، کوتاهترین مسیر ممکن که دقیقاً یک بار از هر شهر بازدید می کند و به شهر مبدا باز می گردد چیست؟

ما می توانیم با حریص بودن همیشه با رفتن به نزدیکترین شهر ممکن ، به این مشکل نزدیک شویم. ما هر یک از شهرها را به عنوان اولین انتخاب می کنیم و از آن استراتژی استفاده می کنیم.

همانطور که در مثالهای قبلی اتفاق افتاد ، ما همیشه می توانیم شهرها را به گونه ای بسازیم که استراتژی حریص بدترین راه حل ممکن را پیدا کند.

در این بخش ، ما دیده ایم که یک استراتژی حریص می تواند ما را به سمت فاجعه سوق دهد. اما مشکلاتی وجود دارد که در آن چنین رویکردی می تواند راه حل بهینه را به خوبی تقریبی کند.

وقتی حریص بودن چندان بد نیست

ما دیده ایم که یک استراتژی حریص می تواند به همان اندازه که می خواهیم برای برخی از مشکلات بد شود. این بدان معنی است که ما نمی توانیم از آن برای به دست آوردن راه حل بهینه و حتی تقریب خوبی از آن استفاده کنیم.

اما نمونه هایی وجود دارد که در آن الگوریتم های حریص تقریب های بسیار خوبی را به ما ارائه می دهند! در این موارد ، رویکرد حریص بسیار مفید است زیرا تمایل به ارزان تر و اجرای آن آسان تر است.

پوشش vertex یک نمودار حداقل مجموعه ای از راس ها است به گونه ای که هر لبه نمودار حداقل یکی از نقاط پایانی خود را در مجموعه دارد.

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

ما هر لبه را از نمودار انتخاب می کنیم و U و V را به مجموعه اضافه می کنیم. سپس ، ما تمام لبه هایی را که U یا V را به عنوان یکی از نقاط پایانی آنها دارند حذف می کنیم و روند قبلی را تکرار می کنیم در حالی که نمودار باقی مانده دارای لبه هایی بود.

این ممکن است شبه کد الگوریتم قبلی باشد:

vertexCover(G): VertexCover // empty set E' where is in E' E' = E' - U edges incident to u, v>Retu vertexcover 

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

من قصد ندارم نمایش این جمله را در این پست گنجانم ، اما می توانید با توجه به این که برای هر لبه ای که به پوشش راس اضافه می کنیم ، آن را اثبات کنید ، یا U یا V در راه حل بهینه قرار دارند (یعنی درپوشش راس کوچکتر).

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

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

نتیجه گیری

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

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

اگر از این پست لذت بردید و می خواهید این نوع محتوا را در حال آمدن نگه دارم ، با به اشتراک گذاشتن آن و برچسب زدن به من ، به من اطلاع دهید. همچنین می توانید برای محتوای بیشتر مربوط به CS ، مرا در توییتر دنبال کنید.