C++ でアクティビティ選択アルゴリズムを使用する方法

C でのアクティビティ選択アルゴリズムの使用方法

アクティビティ選択アルゴリズム (アクティビティ選択アルゴリズム) は、アクティビティのスケジュール設定の問題を解決するために使用される古典的な貪欲アルゴリズムです。アクティビティの開始時間と終了時間のセットが与えられた場合、アルゴリズムの目標は、互換性のあるアクティビティの最大セット、つまり、互いに競合せずに同時に実行できるアクティビティの最大数を選択することです。この記事では、C を使用してアクティビティ選択アルゴリズムを実装する方法を、具体的なコード例とともに紹介します。

アルゴリズムのアイデア:

アクティビティ選択アルゴリズムの基本的なアイデアは、まず終了時間に従ってアクティビティを並べ替えることです。次に、終了時間が最も早いアクティビティを選択し、それと競合する他のアクティビティを除外します。具体的な手順は次のとおりです。

1. まず、各アクティビティを表す構造を定義する必要があります。この構造には、アクティビティの開始時刻と終了時刻が含まれています。

struct Activity
{
    int start;
    int end;
};

2. 次に、アクティビティ選択アルゴリズムを実装する関数を定義します。関数の入力はアクティビティの配列と配列のサイズであり、出力はアクティビティの最大一貫性セットです。

vector<Activity> activitySelection(Activity arr[], int n)
{
    // 根据结束时间对活动进行排序
    sort(arr, arr + n, [](Activity a, Activity b) {
        return a.end < b.end;
    });

    vector<Activity> selectedActivities;
    selectedActivities.push_back(arr[0]); //选择第一个活动

    int lastSelected = 0;
    //遍历剩余的活动
    for (int i = 1; i < n; i++)
    {
        if (arr[i].start >= arr[lastSelected].end)
        {
            selectedActivities.push_back(arr[i]);
            lastSelected = i;
        }
    }

    return selectedActivities;
}

3. 最後に、main 関数でアクティビティ配列を構築し、アクティビティ選択関数を呼び出して、最大の一貫性のあるアクティビティ セットを出力します。

int main()
{
    Activity arr[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<Activity> selectedActivities = activitySelection(arr, n);

    cout << "最大相容活动集合：" << endl;
    for (int i = 0; i < selectedActivities.size(); i++)
    {
        cout << "(" << selectedActivities[i].start << ", " << selectedActivities[i].end << ")" << endl;
    }

    return 0;
}

コード サンプル分析:

まず、定義された構造体で、各アクティビティの開始時刻 (start) と終了時刻 (end) を構造体のメンバーとして使用します。

次に、実装されたアクティビティ選択関数では、アクティビティの配列が最初にアクティビティの終了時間に従って並べ替えられるため、後続のアクティビティを選択するときに、終了時間の順序に簡単に従うことができます。

次に、ベクトル コンテナ selectedActivities を定義して、一貫したアクティビティの最大セットを保存し、最初のアクティビティをそれに追加します。

次に、2 番目のアクティビティから開始して、残りのアクティビティを実行します。現在のアクティビティの開始時刻が最後に選択したアクティビティの終了時刻以上である場合、そのアクティビティは最大互換性アクティビティ セットに追加され、現在選択されている最後に選択されたアクティビティとして設定されます。

最後に、main 関数でアクティビティ配列を作成し、アクティビティ選択関数を呼び出して、最大の一貫したアクティビティ セットを出力します。

概要:

上記のサンプル コードを通じて、C でアクティビティ選択アルゴリズムを実装する方法を確認できます。貪欲な戦略を使用して、終了時間に基づいて互換性のあるアクティビティの最大のセットを選択します。アクティビティ選択アルゴリズムは、会議の手配やプロジェクト管理など、現実の世界で広く使用されています。

[参考文献]

[1] Cormen, T. H.、Leiserson, C. E.、Rivest, R. L.、& Stein, C. (2009). Introduction to Algorithms (3rd edition). MIT Press 。

以上がC++ でアクティビティ選択アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。