مبانی الگوریتم های حریص

در یک طرح الگوریتم هیچ کس "گلوله نقره ای" وجود ندارد که درمانی برای همه مشکلات محاسبات باشد. مشکلات مختلف نیاز به استفاده از انواع مختلف تکنیک ها دارد. یک برنامه نویس خوب از تمام این تکنیک ها بر اساس نوع مشکل استفاده می کند. برخی از تکنیک های متداول عبارتند از:

1. تفرقه بینداز و حکومت کن
2. الگوریتم های تصادفی
3. الگوریتم های حریص (این یک الگوریتم نیست ، یک تکنیک است.)
4. برنامه نویسی پویا

"الگوریتم حریص" چیست؟

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

چگونه تصمیم می گیرید کدام انتخاب بهینه است؟

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

الگوریتم های حریص دارای مزایا و مضراتی هستند:

1. برای یک الگوریتم حریص (یا حتی الگوریتم های حریص) برای یک مشکل بسیار آسان است.
2. تجزیه و تحلیل زمان اجرای الگوریتم های حریص به طور کلی بسیار ساده تر از سایر تکنیک ها (مانند تقسیم و فاتح) خواهد بود. برای تکنیک تقسیم و فاتح ، مشخص نیست که آیا این تکنیک سریع یا کند است. این امر به این دلیل است که در هر سطح بازگشت ، اندازه کوچکتر می شود و تعداد مشکلات فرعی افزایش می یابد.
3. بخش دشوار این است که برای الگوریتم های حریص شما باید برای درک مسائل صحت بسیار سخت تر کار کنید. حتی با وجود الگوریتم صحیح ، اثبات درست بودن آن دشوار است. اثبات اینکه یک الگوریتم حریص صحیح است بیشتر از یک علم است تا یک علم. این شامل خلاقیت زیادی است.

توجه: بیشتر الگوریتم های حریص صحیح نیستند. مثالی بعداً در این مقاله شرح داده شده است.

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

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

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

این یک مشکل ساده الگوریتم حریص است. در هر تکرار ، شما باید با حرص و طمع چیزهایی را انتخاب کنید که ضمن حفظ دو متغیر جریان و شماره های فعلی ، حداقل زمان لازم را برای تکمیل داشته باشید. برای تکمیل محاسبه ، شما باید:

1. آرایه A را به ترتیب غیر کاهش دهنده مرتب کنید.
2. هر مورد را یک به یک انتخاب کنید.
3. زمان لازم را برای تکمیل آن مورد انجام به زمان فعلی اضافه کنید.
4. یکی را به شماره های اضافه کنید.

این کار را تا زمانی که زمان فعلی کمتر یا برابر با t باشد ، تکرار کنید.

بگذارید a = و t = 6

بعد از مرتب سازی ، a =

بعد از تکرار 1 st:

بعد از تکرار دوم:

بعد از تکرار 3:

پس از تکرار چهارم ، زمان فعلی 6 + 4 = 10 است که از T. بیشتر است. بنابراین ، پاسخ 3 است.

پیاده سازی

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

یک مشکل دشوارتر-مشکل برنامه ریزی را در نظر بگیرید.

شما موارد زیر را دارید:

• لیست تمام کارهایی که امروز باید انجام دهید
• زمانی که برای انجام هر کار لازم است
• اولویت (یا وزن) برای هر کار.

برای به دست آوردن مطلوب ترین نتیجه ، باید تعیین کنید که در چه ترتیب باید وظایف را انجام دهید.

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

• Integer n برای تعداد کارهایی که می خواهید انجام دهید
• لیست های P: اولویت (یا وزن)
• لیست T: زمانی که برای انجام یک کار لازم است

برای فهمیدن چه معیارهایی برای بهینه سازی ، باید کل زمان لازم برای انجام هر کار را تعیین کنید.

c (j) = t [1] + t [2] +.+ t [j] که در آن 1

این امر به این دلیل است که کار JTH باید منتظر بماند تا اولین کارها (J-1) به اتمام برسد و پس از آن به زمان [J] برای تکمیل نیاز داشته باشد.

به عنوان مثال ، اگر t = ، زمان تکمیل خواهد بود:

• ج (1) = t [1] = 1
• C (2) = t [1] + t [2] = 1 + 2 = 3
• C (3) = t [1] + t [2] + t [3] = 1 + 2 + 3 = 6

بدیهی است که شما می خواهید زمان تکمیل تا حد امکان کوتاه باشد. اما خیلی ساده نیست.

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

روش بهینه برای انجام وظایف چیست؟

این به عملکرد عینی شما بستگی دارد. در حالی که بسیاری از کارکردهای عینی در مشکل "برنامه ریزی" وجود دارد ، عملکرد هدف شما F مبلغ وزنی زمان تکمیل است.

f = p [1] * c (1) + p [2] * c (2) +.+ p [n] * c (n)

این عملکرد هدف باید به حداقل برسد.

موارد خاص

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

دو مورد خاص به شرح زیر است:

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

مورد 1

عملکرد عینی را که برای به حداقل رساندن آن نیاز دارید در نظر بگیرید. فرض کنید زمان لازم برای انجام کارهای مختلف t است.

صرف نظر از اینکه چه دنباله ای استفاده می شود ، زمان تکمیل برای هر کار به شرح زیر خواهد بود: C (1) = t [1] = t c (2) = t [1] + t [2] = 2 * t c (3) = t [1] + t [2] + t [3] = 3 * t. C (n) = n * t

برای اینکه عملکرد عینی تا حد ممکن کوچک باشد بالاترین اولویت باید با کوتاهترین زمان تکمیل همراه باشد.

مورد 2

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

f = p [1] * c (1) + p [2] * c (2) +.+ p [n] * c (n) f = p * c (1) + p * c (2) +.+ p * c (n) f = p * (c (1) + c (2) +. + c (n))

برای به حداقل رساندن مقدار F ، باید (C (1) + C (2) +. + C (n)) را به حداقل برسانید ، که در صورت شروع کار روی کارهایی که نیاز به کوتاهترین زمان برای تکمیل دارند ، می توان انجام داد.

دو قانون وجود دارد. به وظایفی که:

• اولویت بالاتری داشته باشید
• برای تکمیل زمان کمتری داشته باشید

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

If you have 2 tasks and both these rules give you the same advice, then the task that has a higher priority and takes less time to complete is clearly the task that must be completed first. But what if both these rules give you conflicting advice? What if you have a pair of tasks where one of them has a higher priority and the other one requires a longer time to complete? ( i.e. P[i] > P[j] but T[i] >t [j]). ابتدا کدام یک را باید کامل کنید؟

آیا می توانید این 2 پارامتر (زمان و اولویت) را در یک امتیاز واحد جمع کنید به گونه ای که اگر شغل ها را از نمره بالاتر به نمره پایین تر مرتب کنید ، همیشه یک راه حل بهینه می گیرید؟

2 قانون را به خاطر بسپارید.

1. اولویت های بالاتر را ترجیح دهید تا اولویت های بالاتر منجر به نمره بالاتر شود.
2. به کارهایی که نیاز به زمان کمتری برای تکمیل دارند ، ترجیح دهید تا هرچه زمان بیشتری لازم باشد ، نمره را کاهش دهد.

شما می توانید از یک عملکرد ریاضی ساده استفاده کنید ، که 2 عدد (اولویت و زمان لازم) را به عنوان ورودی می گیرد و ضمن دیدار با این دو ویژگی ، یک عدد (نمره) را به عنوان خروجی باز می گرداند.(تعداد نامحدودی از این توابع وجود دارد.)

بیایید دو مورد از ساده ترین کارکردهای دارای این خصوصیات را انجام دهیم

• الگوریتم شماره 1: مشاغل را با کاهش ارزش (P [i] - t [i]) سفارش دهید
• الگوریتم شماره 2: مشاغل را با کاهش ارزش (P [I] / T [I]) سفارش دهید

برای سادگی فرض می کنیم که هیچ ارتباطی وجود ندارد.

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

f = p [1] * c (1) + p [2] * c (2) = 1 * 2 + 3 * 7 = 23

According to algorithm #2 ( P[1] / T[1] ) >(P [2] / t [2]) ، بنابراین ، اولین کار باید ابتدا انجام شود و عملکرد هدف شما این خواهد بود:

f = p [1] * c (1) + p [2] * c (2) = 3 * 5 + 1 * 7 = 22

الگوریتم شماره 1 پاسخ بهینه را به شما نمی دهد و بنابراین ، الگوریتم شماره 1 (همیشه) صحیح نیست.

توجه: به یاد داشته باشید که الگوریتم های حریص اغلب اشتباه هستند. فقط به این دلیل که الگوریتم شماره 1 صحیح نیست ، دلالت بر این ندارد که الگوریتم شماره 2 صحیح است. با این حال ، معلوم می شود که در این مورد الگوریتم شماره 2 همیشه صحیح است.

بنابراین ، الگوریتم نهایی که مقدار بهینه عملکرد هدف را برمی گرداند:

پیچیدگی زمان شما 2 حلقه دارید که هر بار و یک عملکرد مرتب سازی O (n * logn) را می گیرید. بنابراین ، پیچیدگی زمان کلی o (2 * n + n * logn) = o (n * logn) است.

درستی

برای اثبات اینکه الگوریتم شماره 2 صحیح است ، از اثبات با تضاد استفاده کنید. فرض کنید آنچه شما می خواهید اثبات کنید نادرست است و از آن چیزی که بدیهی است نادرست است.

بنابراین ، فرض کنید که این الگوریتم حریص یک راه حل بهینه را تولید نمی کند و راه حل دیگری (خروجی توسط الگوریتم حریص) وجود ندارد که بهتر از الگوریتم حریص است.

A = برنامه حریص (که یک برنامه بهینه نیست) B = برنامه بهینه (بهترین برنامه ای که می توانید تهیه کنید)

Assumption #1: all the ( P[i] / T[i] ) are different . Assumption #2: (just for simplicity, will not affect the generality) ( P[1] / T[1] ) > ( P[2] / T[2] ) > . >(P [n] / t [n])

Because of assumption #2, the greedy schedule will be A = ( 1, 2, 3, . N ) . Since A is not optimal (as we considered above) and A is not equal to B (because B is optimal), you can claim that B must contain two consecutive jobs ( i, j ) such that the earlier of those 2 consecutive jobs has a larger index ( i >ج). این درست است زیرا تنها برنامه ای که دارای خاصیت است ، که در آن شاخص ها فقط بالا می روند ، A = (1 ، 2 ، 3 ،. n) است.

Therefore, B = ( 1, 2, . i, j, . , N ) where i >ج.

اگر این 2 شغل را عوض کنید ، باید در مورد تأثیر سود یا ضرر فکر کنید. در مورد تأثیر این مبادله در زمان تکمیل موارد زیر فکر کنید:

1. کار روی K غیر از من و j
2. کار روی من
3. کار در J

برای K ، 2 مورد وجود خواهد داشت:

وقتی K در سمت چپ من و j در B قرار دارد اگر من و j را عوض کنید ، هیچ تاثیری در زمان تکمیل k نخواهد داشت.

هنگامی که K در سمت راست I و J در B پس از تعویض قرار دارد ، زمان تکمیل K C (K) = T [1] + T [2] + .. + T [J] + T [I] + است.. t [k] ، k یکسان باقی خواهد ماند.

برای من زمان تکمیل: قبل از تعویض c (i) = t [1] + t [2] + بود.+ t [i] بعد از تعویض c (i) = t [1] + t [2] + است.+ t [j] + t [i]

واضح است که زمان تکمیل برای من با T [J] بالا می رود و زمان تکمیل J با T [i] پایین می آید.

ضرر به دلیل مبادله (p [i] * t [j]) سود به دلیل مبادله است (p [j] * t [i])

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

یک مشکل باید این دو مؤلفه را برای یک الگوریتم حریص تشکیل دهد:

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

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

مثال ها

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