الگوریتم حریصانه چیست؟ ( همراه با حل نمونه مثال ICPC ACM)

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

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

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

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

Gene Assembly

With the large amount of genomic DNA sequence data being made available, it is becoming more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more complicated, because of the presence of junk DNA that interrupts the coding regions of genes in the genomic sequence. That is, a gene is composed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and their lengths can be arbitrary.

Most gene finding algorithms have two steps: in the first they search for possible exons; in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in the genomic sequence. We say that exon i appears before exon j if the end of i precedes the beginning of j.

The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that could be assembled to generate a gene.

Input

Several input instances are given. Each instance begins with the number 0 < n < 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most 50000 basis. The input ends with a line with a single `0'.

Output

For each input instance your program should print in one line the chain with the largest possible number of exons, by enumerating the exons in the chain. The exons must follow the order of appearance (as defined in the statement of the problem). If there is more than one chain with the same number of exons, your program can print anyone of them.

Sample Input

6
340 500
220 470
100 300
880 943
525 556
612 776
3
705 773
124 337
453 665
0
2

Sample Output

3 1 5 6 4
2 3 1

توضیح مختصری راجب سوال:

سوال N بازه به ما میدهد و بزرگترین مجموعه از بازه ها را میخواهد که برهم نهی نداشته باشند
این مسئله در واقع همان مسئله انتخاب بهینه فعالیت ها Activity Selection Problem میباشد که الگوریتم حریصانه را میتوان برای حل آن استفاده کرد.

حل سوال:
در الگوریتم انتخاب بهینه فعالیت ها ابتدا کل بازه ها را بر اساس پایان به صورت صعودی مرتب میکنیم. حال اولین بازه را به مجموعه اضافه میکنیم و با یک حلقه بترتیب بازه های بعدی را چک میکنیم هر کدام که شروعش بعد از پایان اخرین بازه اضافه شده به مجموعه بود . به مجموعه اضافه میکنیم. و در پایان این مجموعه همان جواب مسئله است.
فقط نکته ای که وجود دارد این است که در این مسئله ما ID اولیه بازه ها را باید در خروجی بترتیب قرار گرفتن در مجموعه چاپ کنیم و با مرتب سازی ای که انجام میدهیم این ID از دست میرود پس نیاز به یک متغییر برای هر بازه داریم که در آن ID اولیه را ذخیره کنیم و بعد مرتب سازی این متغیر برای هر بازه تغییر نکند.
نکته دیگری وجود دارد این است که برای مرتب سازی روش های زیادی وجود دارد. در کتابخانه جدید C++ و Header file Algorithm تابعی به اسم Sort وجود دارد که در زمانی بسیار بهینه مرتب سازی را انجام میدهد. فقط این را در نظر بگیرید که ما برای کلاس ها و ساختمان هایمان باید عملگر های کوچکتر و بزرگتر بودن را پیاده سازی کنیم در غیر این صورت مقایسه دو شی یک کلاس امکان پذیر نخواهد بود.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define Author "DemoVersion"
#define MAXN 1010
struct term{
int a,b,ID;
    bool operator < (const term &e) const {
        return b < e.b;
    }
};
int main()
{
    term terms[MAXN];
    vector<int> out;
    int N,i,first;
    while(cin>>N&&N){
        out.clear();
        for(i=0;i<N;i++){
            cin>>terms[i].a>>terms[i].b;
            terms[i].ID=i+1;
        }
        sort(terms,terms+N);
        out.push_back(0);
        for(i=1;i<N;i++){
            if(terms[i].a>terms[out.back()].b)
                out.push_back(i);
        }
        first=1;
        for(vector<int>::iterator k=out.begin();k!=out.end();k++){
            if(first)first = 0;
            else cout<<" ";
            cout<<terms[*k].ID;
        }
        cout<<endl;
    }
    return 0;
}