C++ 貪欲アルゴリズム（会場配置、間隔選択）の例

アルゴリズム講座学習後の初収録 徐々にプログラム設計で考慮すべき要素が増えてきました プログラム＝データ構造アルゴリズム この方程式が深く理解できました。単純な C プログラミングから始めて、適切なデータ構造を選択するまで、さらに一歩進んで、アルゴリズム レベルからプログラム実行の効率を考慮する必要があります。私のアルゴリズムの理解は、より少ないオーバーヘッドでより良い実行結果を達成することです。

分割統治法と動的計画法はこれまで記録されたことがなかったので、貪欲アルゴリズムを学んだとき、学んだことを要約して理解する必要があると感じました。よりよく理解できました。動的プログラミングの設計では、最適な部分構造特性と重複する部分問題を満たし、ボトムアップ戦略を採用して最適値を計算し、全体的な最適解を見つける必要があります。このプロセスは非常に難しい場合もありますが、重要なことは、再帰式を記述し、テーブルを下から上に埋めていくことです。貪欲戦略は動的計画法に少し似ていますが、いくつかの点で異なり、貪欲アルゴリズムのアイデアの方が考えやすい場合もあります。部分問題の最適性を満たし、全体の最適性が得られるか? 2 つの条件: 最適な部分構造プロパティと貪欲な選択プロパティ。貪欲な選択プロパティを満たすには、最適な部分構造のプロパティを満たす必要がありますが、最適な部分構造のプロパティを満たすことが必ずしも貪欲な選択のプロパティを満たすとは限りません。たとえば、ナップサック問題は貪欲なアルゴリズムで解決できますが、0-1 ナップザック問題は、貪欲なアルゴリズムでのみ解決できます。動的計画法で解決します。

典型的な貪欲問題のアクティビティの配置では、n 個のアクティビティがあり、開始時刻と終了時刻が指定されており、できるだけ多くのアクティビティを配置する必要があります (時間が互いに競合しないようにします)。この問題を解決するための正しい貪欲なアイデアは、各アクティビティの終了時刻を比較変数として使用し、終了時刻の昇順にアクティビティを並べ替えて、比較と選択を実行することです。会場手配の問題と活動内容には多少の違いがありますが、私なりの問題解決プロセスは以下の通りです。

7-2 会場手配の問題 (20 点)

十分な会場で一連のアクティビティを手配し、使用する会場をできるだけ少なくしたいとします。スケジューリングのための効率的な貪欲アルゴリズムを設計します。 (この問題は実は有名なグラフの色付け問題です。各アクティビティをグラフの頂点とみなした場合、互換性のないアクティビティはエッジで接続されます。隣接する頂点が異なる色になる最小の色付けの数が最小会場数に相当します。 )

入力形式:

最初の行には正の整数 k が含まれており、配置するアクティビティが k 個あることを示します。次の k 行では、各行に 2 つの正の整数があり、それぞれスケジュールされる k 個のアクティビティの開始時刻と終了時刻を表します。時間は 0 時から分単位で測定されます。

出力形式:

最小会場数を出力します。

入力サンプル:

5
1 23
12 28
25 35
27 80
36 50

出力サンプル:

3

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//标记该活动是否被安排，0表示未安排，1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比较规则：以结束时间升序排列 
{ 
    return a.end<b.end;
 } 
int main()
{
    int i,j,n;
    node temp;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//总共需要的会场数量 
    for(i=0;i<n;i++)//方法2 
    {
        if(!t[i].flag)//找到未安排的活动，进行场地安排 
        {
            sum++;
            int p=i;
            for(j=p+1;j<n;j++)//当前活动结束时间与下一个活动开始不相交 ，则安排到同一个会场 
            {
                if(t[p].end<=t[j].begin&&!t[j].flag)
                {
                    p=j;t[j].flag=1;
                }
            }
            t[i].flag=1;
        }
    }
    cout<<sum;
    return 0;
}

貪欲な戦略は、競合しないアクティビティをできるだけ多く 1 つの会場に配置することです。重複の場合は別会場に調整させていただきます。

すべてのアクティビティを終了時刻の昇順に並べ、sort 関数を使用し、cmp メソッドをカスタマイズします。ループ本体では、毎回スケジュールされていないアクティビティを検索し、このアクティビティを使用して、同時に会場に収容できる他のアクティビティを検索できます (このステップは内側のループにネストされています)。これで、必要な会場数の合計が計算されました。

同様の問題は区間点選択問題です。

7-10 点選択問題 (15 点)

数値軸上に n 個の閉区間があります。 [アイ、ビ]。各間隔に少なくとも 1 つのポイントが存在するように、できるだけ少ないポイントを取得します (異なる間隔のポイントは同じであってもかまいません)。

入力形式:

最初の行の数字 n は、n 個の閉じた間隔があることを意味します。次の n 行。各行には閉区間を示す 2 つの数値が含まれます [ai, bi]

出力形式:

整数。少なくとも点の数を示します。が必要です

入力サンプル:

ここに一連の入力を入力します。例:

3
1 3
2 4
5 6

出力サンプル:

対応する出力をここに示します。例: 2

は、最初に、いくつかの間隔の間で共通のセグメントを見つけ、選択された最小点を計算するために、各共通セグメントにどの間隔が含まれるかを記録したいと考えています。後で、このアイデアは実際に単純化できることがわかりました。その戦略は、右端をバッフルとして使用して、その前に他の間隔があるかどうかを確認することです。ある場合は、カウントしないでください。そうでない場合は、共通の間隔がないことを意味しますセグメントを数えて、バッフルの位置を移動して続行する必要があります。探してください。貪欲な戦略は、区間の正しい終点を選択して、より大きな交差セグメントを確実に含めることができ、選択するポイントの数を最小限に抑えることです。

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比较规则，按区间右端点升序排列 
{
    return a.r<b.r;
} 
int main()
{
    int n,i,j,count=1,select;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//预处理，将区间按规则排好序，方便后续比较 
    select=dots[0].r;
    //贪心策略是选择区间右端点，保证能够包含更大交叉段，选的点最少 
    for(i=1;i<n;i++)//每次将当前选择的一个区间的右端点与下一个（或者同一区间，可忽略）左端比较 
    {
        if(dots[i].l>select)//如果没有交叉，选点+1,并以此区间右端为新一轮比较的点 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<<count;
    return 0;
}

アルゴリズムを学んだ後、問題を解決するには考え方を変える必要があることがわかりました。プログラミング前のアルゴリズムの選択は非常に重要です。偉人から学ぶことも必要です。代表的なアルゴリズムの調査と研究本当に広くて奥が深いです！

この記事は C#.Net チュートリアル 列から引用したものです。ぜひ学習してください。

以上がC++ 貪欲アルゴリズム（会場配置、間隔選択）の例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。