در تعیین حد سود حریص نباشید

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

خواص الگوریتم های حریص

الگوریتم های حریص می تواند برای مشکلات زیر دو شرط اساسی اعمال شود:

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

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

بیایید با تلاش برای حل یک مشکل در مورد این موضوع بحث کنیم: کله ای کسری!

سؤال: به شما وزن و مقادیر N وسایل و یک کوله پشتی داده می شود که می تواند تا واحدهای وزن Knapsack_Capacity را نگه دارد. شما باید حداکثر مقدار کل را که می توانیم وارد Knapsack کنیم ، پیدا کنید.

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

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

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

این مشکل همچنین از خاصیت زیر ساختار بهینه پیروی می کند.

شبه

BOOL COMP (مورد A ، مورد B)(b.value / b.weight)>

Double ConceithalalkNapsack (مورد arr [] ، int n ، int knapsack_capacity)

 int curr = 0 double ans = 0. 0

برای (i = 0 تا n-1)

 دیگر> retu ans>

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

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

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

If you form the path by choosing the maximum value child at each level(The Greedy Choice!), you will end up with the path 5>7>2 But we can see that clearly 5>3>17 مسیری با حداکثر مقدار مقادیر است. ما فرض کردیم که خاصیت انتخاب حریص در این مشکل اعمال می شود و با پاسخ اشتباه به پایان رسید! ما باید هر مسیر را طی کنیم و یک بار که به برگ رسیدیم ، مبلغ را بررسی کنیم و مبلغ مسیر را با حداکثر مبلغ جهانی که تا آن زمان به آن رسیدیم مقایسه کنیم.

شبه

int findmaxroottoleafpath (ریشه Treenode)

 retu root.val + max(left_sum, right_sum)>

★ سعی کنید پیچیدگی های کد فوق را تجزیه و تحلیل کنید.

مثال ها

سوال: مشکل توالی شغلی → به شما مهلت مهلت های N داده می شود. هر شغل سود مرتبط با آن دارد. هر شغل یک واحد زمان را می گیرد. حداکثر سود را که می توانید با توالی کردن مشاغل بدست آورید ، پیدا کنید.

به عنوان مثال ، لیست زیر از مشاغل به شما داده می شود

JobID |مهلت |سود ------ | ----------- | -------- A |2 |100 B |1 |19 C |2 |27 D |1 |25 E |3 |15

شما باید حداکثر سود را که می توان با توالی شغل بهینه به دست آورد ، پیدا کنید.

به وضوح می توانیم ببینیم که دو شغل با مهلت 1 و دو شغل با مهلت 2 وجود دارد. این بدان معناست که از این چهار شغل ، ما فقط قادر خواهیم بود دو کار را به موقع انجام دهیم. هر یک از یک کار با مهلت 1 و یک کار با مهلت 2 یا هر دو کار با مهلت 2. ما دو کار را با مهلت 2 انتخاب خواهیم کرد زیرا این امر حداکثر سود را برای ما به همراه دارد.

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

شبه

int adfeblencing (کار شغلی [] ، int n)>> retu max_profit>

آیا اکنون مفهوم الگوریتم های حریص را می فهمید؟آیا اکنون می توانید همین مسئله را در مورد مشکلات مختلف پیاده سازی کنید؟

بگذارید با رویکرد حریص یک مشکل دیگر را حل کنیم.

سؤال: حداقل تعداد سکه های مورد نیاز → ما یک منبع نامحدود از سکه های این فرقه ها داریم:<1, 2, 5, 10, 20, 50, 100, 500, 1000>بشربا توجه به مقدار C ، حداقل تعداد سکه هایی را پیدا کنید که به جمع c برسند.

هنگامی که شما نیاز به تغییر به کسی دارید که به C به کسی تغییر دهید و از فرقه های داده شده نامحدودی دارید. چگونه می توانید تغییر دهید؟

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

شبه

int findminimumnumberofcoins (int c)> retu count>

اول ، بیایید کمی در مورد این کد بحث کنیم. آیا می توانید این کد را حتی بیشتر بهینه کنید؟(اشاره: چند بار درونی در حالی که حلقه اجرا می شود؟) خوب ، ما می توانیم

• تعداد را به یکباره افزایش دهید. تعداد += (c/فرقه [i])
• اختصاص C = C ٪ فرقها [i]

سعی کنید این کد را با چند مثال خشک کنید. آیا هر بار جواب درست می دهد؟

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

چگونه می توان این مشکل را پیچیده کرد تا دیگر ویژگی انتخاب حریص دیگر قابل استفاده نباشد؟

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

• C = 12 ، انتخاب حریص: (10،1،1) ، انتخاب بهینه: (6،6)
• C = 24 ، انتخاب حریص: (20،1،1،1،1) ، انتخاب بهینه: (6،6،6،6)

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

با استفاده از یک رویکرد برنامه نویسی پویا ، مشکل را حل کنید!

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

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

ایده های انتقادی برای فکر کردن!

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