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

• تقسیم و غلبه – Divide and conquer
• الگوریتم های تصادفی – Randomized algorithms
• الگوریتم های حریصانه – Greedy algorithms (که در واقع الگوریتم نیستند، بلکه رویکرد طراحی الگوریتم هستند)
• برنامه ریزی پویا – Dynamic programming

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

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

حالا سوال اینجاست که چطور می توان فهمید چه انتخابی بهینه است؟

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

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

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

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

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

چیزهایی را که تا به اینجا مطرح کرده ایم در ذهن داشته باشید، حالا با دو مثال می خواهیم پیش برویم.

تصور می کنیم شما آدمی بسیار پرمشغله هستید، که تنها دقیقاً مقدار T زمان در اختیار دارید که تعدادی کار را به انجام برسانید. به شما آرایه ای به نام A از اعداد صحیح داده شده است که هر کدام از اعداد آرایه زمان لازم برای یکی از آن کارها را مشخص می کند. با فرض این که تعداد کارهای انجام شده مهم است، شما می خواهید در زمانی که دارید بیشترین تعداد کار را انجام دهید! اما بیشترین تعداد چند تاست؟

این یک مسئله ساده از نگرش حریصانه است. در هر مرحله شما به طور حریصانه کوتاه ترین کار را انتخاب می کنید تا کارهای بیشتری را تمام کنید و در این حین دو مقدار را نگهداری می کنید. اولی currentTime و دومی numberOfThings است.

برای محاسبه مقادیر و انجام امور شما باید:

1. آرایه A را به صورت صعودی مرتب کنید.
2. به ترتیب هر کدام از کارها را یکی یکی انتخاب کنید.
3. زمان هر کاری را که انتخاب می کنید به currentTime اضافه کنید.
4. numberOfThings را یک واحد افزایش دهید.

این مراحل را تا هنگامی که مقدار currentTime کوچکتر از T یا مساوی آن بماند تکرار می کنید.

فرض کنیم {A = {5, 3, 4, 2, 1 و T = 6 است. پس از مرتب سازی داریم {A = {1, 2, 3, 4, 5.

بعد از تکرار مرحله اول:

• • currentTime = ۱

• numberOfThings = ۱

بعد از تکرار مرحله دوم:

• • currentTime = ۱ + ۲ = ۳

• numberOfThings = ۲

بعد از تکرار مرحله سوم:

• • currentTime = ۳ + ۳ = ۶

• numberOfThings = ۳

بعد از تکرار مرحله چهارم currentTime = ۶ + ۴ = ۱۰ می شود که از مقدار T بزرگتر است. بنابراین جواب ۳ است.

پیاده سازی به شکل زیر است:

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 100;
int A[MAX];

int main()
{
    int T, N, numberOfThings = 0, currentTime = 0;
    cin >> N >> T;
    for(int i = 0;i < N;++i)
        cin >> A[i];
    sort(A, A + N);
    for(int i = 0;i < N;++i)
    {
        currentTime += A[i];
        if(currentTime > T)
            break;
        numberOfThings++;
    }
    cout << numberOfThings << endl;
    return 0;
}

این مثال بسیار ساده و بدیهی بود و به محض این که خواندن مسئله مثال را تمام کنید واضح به نظر می رسد که باید الگوریتمی حریصانه را به کار ببرید.

بیایید یک مسئله مشکل را بررسی کنیم. با مسئله زمان بندی (برنامه ریزی) ادامه می دهیم.

در این مسئله چیزهایی که داریم این هاست:

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

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

• تعداد کارها – عدد صحیح N
• لیستی از اولویت (وزن) کارها – لیست P
• لیستی از زمان لازم برای انجام هر کار – لیست T

برای درک معیارهای قابل بهینه سازی، کل زمان لازم برای اتمام کامل هر کار را هم به شیوه زیر محاسبه می کنیم و لیست C را به همین منظور در نظر می‌گیریم.

به ازای تمام j های ۱ تا N :

C(j) = T[1] + T[2] + .... + T[j]

در واقع j امین کار بعد از اتمام j-1 کار قبلی شروع و خودش برای تکمیل شدن به اندازه [T[j زمان نیاز دارد. برای مثال اگر {T = {1, 2, 3 باشد که لیستی صعودی-مرتب است، زمان اتمام هر کار در آرایه C ، به شکل زیر پر خواهد شد:

• • C(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 = P[1] * C(1) + P[2] * C(2) + ...... + P[N] * C(N)

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

برای این موضوع دو قانون به ذهن متبادر می شود که در هر مرحله در انتخاب کار بعدی باید رعایت شوند:

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

بررسی دو رویکرد و الگوریتم حریصانه برای این مسئله

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

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

طبق دو قانون گفته برای انتخاب کارها نتیجه می گیریم:

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

تعداد زیادی تابع می توان تعریف کرد که دو ورودی زمان و اولویت را بگیرند و طبق دو خصوصیت بالا خروجی بدهند. اما از این میان ما دو تابع زیر را در نظر می گیریم و دو الگوریتم بر اساس آن ها تعریف می کنیم:

• الگوریتم شماره ۱ : کارها را به صورت نزولی بر اساس مقدار ( [P[i] – T[i ) مرتب می کنیم.
• الگوریتم شماره ۲ : کارها را به صورت نزولی بر اساس مقدار ( [P[i] / T[i ) مرتب می کنیم.

برای سادگی ما فرض می کنیم مقادیر مساوی به وجود نمی آیند.

حالا ما دو الگوریتم داریم که البته درباره درستی آن ها فعلاً چیزی نمی دانیم. با مقادیر مثالی زیر، نتیجه الگوریتم ها را بررسی می کنیم.

T = {5, 2} و P = {3, 1}

طبق الگوریتم شماره ۱ داریم ( [P[1] – T[1] ) < ( P[2] – T[2] ) ، بنابراین ابتدا کار دوم انتخاب می شود و برای مقدار تابع هدف داریم:

F = P[1] * C(1) + P[2] * C(2) = 3 * 7 + 1 * 2 = 23

طبق الگوریتم شماره ۱ داریم ( [P[1] / T[1] ) > ( P[2] / T[2] ) ، بنابراین ابتدا کار اول انتخاب می شود و برای مقدار تابع هدف داریم:

F = P[1] * C(1) + P[2] * C(2) = 3 * 5 + 1 * 7 = 22

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

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

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

Algorithm (P, T, N)
    {
        let S be an array of pairs ( C++ STL pair ) to store the scores and their indices
        , C be the completion times and F be the objective function
        for i from 1 to N:
            S[i] = ( P[i] / T[i], i )            // Algorithm #2
        sort(S)
        C = 0
        F = 0
        for i from 1 to N:                // Greedily choose the best choice
            C = C + T[S[i].second]
            F = F + P[S[i].second]*C
        return F
    }

پیچیدگی زمانی: یک مرتب سازی با هزینه (O(N * log N و دو حلقه از درجه زمانی (O(N داریم که در نهایت پیچیدگی زمانی (O(N * log N است.

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

یک مسئله حتماً باید دو ویژگی زیر را داشته باشد تا بتوان یک الگوریتم حریصانه برای آن طراحی کرد.

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

چند مسئله معروف که با الگوریتم های حریصانه حل می شوند:

۱- Activity Selection problem

۲- Fractional Knapsack problem

۳- Scheduling problem

۴- Minimum Spanning Tree

۵- Dijkstra’s algorithm for shortest paths from a single source

۶- Huffman codes ( data-compression codes )