貪欲なアルゴリズムは活動の手配の問題を解決します

4.2活動手配問題にはn個の活動の集合E={1,2,...,n}が設けられており,そのうち各活動はスピーチ会場などの同じ資源の使用を要求しているが,同じ時間内にこの資源を使用できる活動は1つしかない.各アクティビティiには、リソースの使用を要求する開始時間siと終了時間fiがあり、si//ACM —— #include #include using namespace std; struct ActionInfo { // int index; // int startTime; // int endTime; // }; bool cmp(const ActionInfo &a, ActionInfo &b); int main() { int actionsGroups = 0; // cin >> actionsGroups; ActionInfo *act = new ActionInfo[actionsGroups];// for (int i = 0; i < actionsGroups; i ++) { // cin >> act[i].index >> act[i].startTime >> act[i].endTime; } // endtime sort(act, act + actionsGroups, cmp); // ： // int currentAction = 0, count = 0; // int notConflictActionsIndex[100]; // notConflictActionsIndex[count] = act[0].index; for (int j = 1; j < actionsGroups; j ++) { if (act[j].startTime >= act[currentAction].endTime) { currentAction = j; notConflictActionsIndex[++count] = act[j].index; // } } // for (int k = 0; k <= count; k ++) { cout << notConflictActionsIndex[k] << ' '; } delete[] act; // system("pause"); return 0; } bool cmp(const ActionInfo &a, ActionInfo &b) { // ， sort ， if (a.endTime <= b.endTime) { return true; } return false; }
まとめ:1データ構造:struct action{int index;//アクティビティの番号int f;//終了時間};2ソート:アクティビティの終了時間昇順ソート比較因子:if(a.f<=b.f)return true;return false;}標準テンプレートライブラリ関数を使用したソート:sort(a,a+n,cmp);ここでC++sort関数を具体的に紹介する文章をお勧めします:STL sort関数の内部の実現はどうしてあなたが書いたより速い3貪欲な選択です:優先選択の終了時間の早い4活動の手配の問題は与えられた活動の集合の中で最大の適合活動の子の集合を選ぶことで、貪欲なアルゴリズムで有効に解くことができる良い例です.この問題は効率的に安全であることを要求しますある公共資源を競合する一連の活動を並べた.貪欲アルゴリズムは、できるだけ多くの活動が公共資源を互換的に使用できるように簡単できれいな方法を提供した.4.3貪欲アルゴリズム貪欲アルゴリズムは、一歩一歩選択の中で現在の状態で最良または最良の選択を採用し、結果が最良または最良であることを望むアルゴリズムである.貪欲アルゴリズムはある種のメトリックの意味での最適解を得ることができる階層処理方法は、一連の選択によって一つの問題の解を得ることができ、その選択のたびに現在の状態である種の意味の最良の選択である.すなわち、問題の局所最適解を通じて問題全体の最適解を求めることが望ましい.この戦略は簡潔な方法であり、多くの問題に対してそれが生み出すことができる全体の最適解は、常に有効であることは保証できない.それはすべての問題に対して全体の最適解を得ることができるわけではないからである.貪欲な策略を利用して問題を解くには、(1)この問題が貪欲な策略で解くのに適しているかどうか.(2)貪欲基準をどのように選択して、問題の最適/より優れた解を得るか.貪欲選択性質:貪欲選択性質とは、求める問題の全体最適解が一連の局部最適の選択、すなわち貪欲選択によって達成できることを指す.これは貪欲アルゴリズムが実行可能な第一の基礎要素であり、貪欲アルゴリズムと動態計画アルゴリズムの主な違いでもある.(1)動的計画アルゴリズムでは、各ステップの選択は、関連するサブ問題の解に依存することが多いため、関連するサブ問題を解いた後でのみ選択が可能となる.(2)欲張りアルゴリズムでは、現在の状態でのみ最適選択、すなわち局所最適選択を行い、その後、この選択後に生じる対応するサブ問題を解く.最適サブ構造:(1)1つの問題の最適解にそのサブ問題の最適解が含まれている場合、この問題は最適サブ構造特性を有すると称される.貪欲戦略を用いて転化するたびに最適解が得られる.問題の最適サブ構造特性は、この問題が貪欲アルゴリズムまたは動的計画アルゴリズムで解くことができる重要な特徴である.(2)貪欲アルゴリズムの毎回の操作は結果に直接影響を与えるが、動的計画はそうではない.貪欲アルゴリズムはすべてのサブ問題の解決方案に対して選択を行い、後退することができない;動的計画は以前の選択結果によって現在に対して選択を行い、後退機能がある.動的計画は主に二次元或いは三次元問題に運用し、貪欲は一般的に一次元問題である.貪欲アルゴリズムを用いて問題を解くには,(1)候補集合A:問題の解決策を構築するために,問題の可能解として候補集合Aがある.すなわち,問題の最終解はいずれも候補集合Aから取られる.(2)解集合S:貪欲選択が進むにつれて,問題を満たす完全解を構成するまで解集合Sは拡張し続ける.(3)関数solutionを解決する:解集合Sが問題の完全解を構成するかどうかをチェックする.(4)関数selectを選択する:すなわち貪欲戦略であり,これは貪欲法の鍵であり,どの候補が最も問題を構成したい解を指摘し,選択関数は通常ターゲット関数と関係がある.(5)実行可能関数feasible:解集合に候補オブジェクトを追加することが可能かどうかをチェックします.すなわち、解集合が拡張された後、制約条件を満たすかどうか以上、主に先生の貪欲アルゴリズムの概念の説明と活動手配の主な解決ステップと貪欲戦略を通じて、活動手配の世代コードを実現しました.