データ構造——欲張りな方法
7513 ワード
欲張り方法greedy method:
ステップ構造が一番よく解ります.一歩ごとに、私たちは一定の基準(この基準は欲張り基準greedy criterionといいます)の下で最適な決定をします.
最適化問題optimization problem:制約条件のセットと最適化関数を含みます.制限条件に適合する問題解を実行可能解と呼びます.最適化関数が最適値を得る可能性のある実行可能解を最適解と呼ぶ.
1.箱の積載問題
大きな船が貨物を積載します.貨物を貨物箱に積み込むには、全部の箱の大きさは同じですが、箱の重さはそれぞれ違います.i番目の貨物箱の重量をWiとし、(1<=i==n)貨物船の最大積載量をcとする.私たちの目的は貨物船に一番多くの貨物を積み込むことです.
note:この問題は正確に最適化問題として記述できます.変数xiのセットが存在する場合(i号箱の船積みかどうか)、xiの値は0か1です.xiが0なら、貨物箱iは船積しません.xiは1の場合、貨物箱iは船積します.私たちはチベットのセットを見つけて、制限条件を満たすようにします.ΣWixi<=c.最適化関数はΣxi各グループが制限条件を満たすxiは実行可能です.よろしいΣxiの最大の実行可能解は最良解です.
貨物箱を貨物船に積み込み、一歩ずつ貨物箱に積み込む.一歩ごとにどの箱を積載するかを決めます.決定する根拠となる貪欲な基準は、残りの箱の中から、一番小さい重さの箱を選ぶことです.これは選択された貨物箱の総重量が最小であることを保証し、貨物船を最大容量に変えてもっと多くの貨物箱を積載させることができます.このような貪欲な策略によって、まず一番軽い箱を選んで、それから軽い箱を選んで、このように降りて、すべての箱がベッドに入るまで、あるいは船の中にもう一つの箱の空間を入れられません.
私たちの最終的なプロセスは、重さが小さい時から大きい順に並べられ、順番に船に積み込まれます.素朴ですね
手順はまず積み立て法を使って重さによって箱を並べ替えます.そして重さが増えた順に箱を船に積み込みます.並べ替えO(nlogn)、アルゴリズムの他の部分は時O(n)を使います.したがって、プログラム全体の複雑さはO(nlogn)です.
2.単一ソースの最短経路
このブログには実例を紹介します.
貪欲な解決方法——ディックストローの貪欲なアルゴリズム
これは現在公認されている解の最短経路の最良のアルゴリズムである.しかし、Dijkstraアルゴリズムは主に他のすべての点への最短経路を計算しています.
ステップで一番短いパスを生成します.各ステップは、新しい目的の頂点に到達する最短のパスを生成する.各最短経路の目的頂点の選択方法は、greedy criterion:最短経路がまだ到達していない頂点から、最短経路を生成できる目的の頂点を選択することである.すなわち、Dijkstra法は経路長の増加順に最短経路を生成する.
アルゴリズムの各ステップにおいて、次の最短経路が生成され、この経路は既に生成された最短経路に実行可能な辺を加えて得られる.
最も短いパスを簡単に記憶する方法は、配列p[].令p[i](すなわちpredeesser)を使用して、ソースの頂点から頂点iまでの経路のうち、頂点iの前の頂点である.
長さの増加順に最短経路を生成するために、d[i]は生成された最短経路において最短辺を拡張して頂点iに到達するときの最短辺の長さを定義する.
簡単に言えば、p[i]は前の頂点であり、d[i]は前の辺権である.
Dijkstraの最短経路アルゴリズムの簡略化:
二つの異なる貪欲な方法:Kruskyal、Prim
1)Kruskyal
アルゴリズムの思想:
ステップに分けてn-1の辺を選択して、一歩ごとに1つの辺を選択して、1つのgreedy criterionは:残りの辺の中から1本のコストが最小で、しかもループを発生することはできません.
Kruskyalアルゴリズムはeステップに分けられ、eはネットワークの中の辺の数である.コストの増加順にe条の辺を考察し、各ステップに一つの辺を考察する時、この辺が選択された辺集中に参加するとループが発生し、それを捨てる.そうでなければ、選択された辺集中に参加する.
疑似コード:
アルゴリズムの考え:ステップ選択によって最小生成ツリーを作成し、ステップ選択において一つの辺を選択します.ステップ毎のgreedy criterion:残りの端からコストが一番小さい辺を選び、選択した辺に入れて集めて木を作る.
ノート:Primは一歩ごとに獲得した入選の辺集はすべて1本の木を形成して、Kruskyalは一歩ごとに入選して辺集は1つの森林です.
疑似コード:
i)問題説明
車を組み立てて、任務の間に相前後関係があります.このグループの任務と任務の先着順は図に示すことができます.AOV(activity on vertex)ネットワークといいます.頂点は任務を表します.
タスクには、図のいずれかのエッジ(i,j)があり、このシーケンスにおいて、タスクiは、ジョブjの前に必ず現れる.このような性質を持つシーケンスをトポロジカルシーケンスと呼ぶ.
トポロジ順序とは、図に従ってトポロジシーケンスを確立するプロセスをいう.
ii)貪欲な方法
貪欲な方法は、左から右へのステップに従ってトポロジーシーケンスを構築する.ステップごとに新しい頂点を選択して、シーケンスに追加します.新しい頂点を選択する根拠は、貪欲準則である.残りの頂点から頂点を選択するwは、頂点vがシーケンス内にない.つまり、wに端があれば、この辺はシーケンスから繋がっています.
上記の欲張り基準を満たさない頂点wが選択された場合、すなわち辺(v,w)の頂点vがシーケンスにないと、トポロジーシーケンスは構築されない.
疑似コード:
ステップ構造が一番よく解ります.一歩ごとに、私たちは一定の基準(この基準は欲張り基準greedy criterionといいます)の下で最適な決定をします.
最適化問題optimization problem:制約条件のセットと最適化関数を含みます.制限条件に適合する問題解を実行可能解と呼びます.最適化関数が最適値を得る可能性のある実行可能解を最適解と呼ぶ.
1.箱の積載問題
大きな船が貨物を積載します.貨物を貨物箱に積み込むには、全部の箱の大きさは同じですが、箱の重さはそれぞれ違います.i番目の貨物箱の重量をWiとし、(1<=i==n)貨物船の最大積載量をcとする.私たちの目的は貨物船に一番多くの貨物を積み込むことです.
note:この問題は正確に最適化問題として記述できます.変数xiのセットが存在する場合(i号箱の船積みかどうか)、xiの値は0か1です.xiが0なら、貨物箱iは船積しません.xiは1の場合、貨物箱iは船積します.私たちはチベットのセットを見つけて、制限条件を満たすようにします.ΣWixi<=c.最適化関数はΣxi各グループが制限条件を満たすxiは実行可能です.よろしいΣxiの最大の実行可能解は最良解です.
貨物箱を貨物船に積み込み、一歩ずつ貨物箱に積み込む.一歩ごとにどの箱を積載するかを決めます.決定する根拠となる貪欲な基準は、残りの箱の中から、一番小さい重さの箱を選ぶことです.これは選択された貨物箱の総重量が最小であることを保証し、貨物船を最大容量に変えてもっと多くの貨物箱を積載させることができます.このような貪欲な策略によって、まず一番軽い箱を選んで、それから軽い箱を選んで、このように降りて、すべての箱がベッドに入るまで、あるいは船の中にもう一つの箱の空間を入れられません.
私たちの最終的なプロセスは、重さが小さい時から大きい順に並べられ、順番に船に積み込まれます.素朴ですね
void continerLoading(container* c, int capacity, int numberOfContainers, int* x)
{//
// x[i] = 1, i （i >= 1）
// O(nlogn)
heapSort(c, numberOfContainers);
int n = numberOfContainers;
// x
for(int i = 1; i <= n; i++)
x[i] = 0;
//
for(int i = 1; i <= n && c[i].weight <= capacity; i++)
{// c[i].id id ， 1 。
x[c[i].id] = 1;
capacity -= c[i].weight; //
}
}手順はまず積み立て法を使って重さによって箱を並べ替えます.そして重さが増えた順に箱を船に積み込みます.並べ替えO(nlogn)、アルゴリズムの他の部分は時O(n)を使います.したがって、プログラム全体の複雑さはO(nlogn)です.
2.単一ソースの最短経路
このブログには実例を紹介します.
http://blog.csdn.net/mu399/article/details/50903876貪欲な解決方法——ディックストローの貪欲なアルゴリズム
これは現在公認されている解の最短経路の最良のアルゴリズムである.しかし、Dijkstraアルゴリズムは主に他のすべての点への最短経路を計算しています.
ステップで一番短いパスを生成します.各ステップは、新しい目的の頂点に到達する最短のパスを生成する.各最短経路の目的頂点の選択方法は、greedy criterion:最短経路がまだ到達していない頂点から、最短経路を生成できる目的の頂点を選択することである.すなわち、Dijkstra法は経路長の増加順に最短経路を生成する.
アルゴリズムの各ステップにおいて、次の最短経路が生成され、この経路は既に生成された最短経路に実行可能な辺を加えて得られる.
最も短いパスを簡単に記憶する方法は、配列p[].令p[i](すなわちpredeesser)を使用して、ソースの頂点から頂点iまでの経路のうち、頂点iの前の頂点である.
長さの増加順に最短経路を生成するために、d[i]は生成された最短経路において最短辺を拡張して頂点iに到達するときの最短辺の長さを定義する.
簡単に言えば、p[i]は前の頂点であり、d[i]は前の辺権である.
Dijkstraの最短経路アルゴリズムの簡略化:
step1: d[i] = a[s][i],1 <= i <= n;
s i， p[i] = s;
， p[i] = 0;
L p[i] != 0 i;
step2: L ， 。 ， step3;
step3: L d i;
step4: i j， d[j]=min{ d[j], d[i]+a[i][j] }.
d[j] ， p[j] = i ， j L ， j 。
step2;template
void AdjacencyWDigraph::ShortestaPaths(int s, T d[], int p[])
{//Shortest pats from vertex s, return shortest distances in d and predecessor info in p.
if (s < 1 || s > n) throw OutOfBounds();
Chain L; //List of reachable vertices for which paths have yet to be found
ChainIterator I;
//initialize d, p, and L
for (int i = 1; i <= n; i++){
d[i] = a[s][i];
if (d[i] == NoEdge) p[i] = 0;
else {p[i] = s;
L.Insert(0,1);}
}
//update d and p
while (!L.IsEmpty()){// more paths exist
//find vertex *v in L with least d
int *v = I.Initialize(L);
int *w = I.Next();
while(w){
if(d[*w] < d[*v]) v = w;
w = I.Next();
}
//next shortest path is to vertex *v
//delete from L and update d
int i =*v;
L.Delete(*v);
for (int j = 1; j <= n; j++){
if(a[i][j] != NoEdge && (!p[j] || d[j] > d[i] + a[i][j]))
{//d[j] decreases
d[j] = d[i] + a[i][j];
//add j to L if not already in L
if (!p[j]) L.Insert(0,j);
p[j] = i;
}
}
}
} 二つの異なる貪欲な方法:Kruskyal、Prim
1)Kruskyal
アルゴリズムの思想:
ステップに分けてn-1の辺を選択して、一歩ごとに1つの辺を選択して、1つのgreedy criterionは:残りの辺の中から1本のコストが最小で、しかもループを発生することはできません.
Kruskyalアルゴリズムはeステップに分けられ、eはネットワークの中の辺の数である.コストの増加順にe条の辺を考察し、各ステップに一つの辺を考察する時、この辺が選択された辺集中に参加するとループが発生し、それを捨てる.そうでなければ、選択された辺集中に参加する.
疑似コード:
//Find a minimum-cost spanning tree in an n-vertex network
Let T be the set of selected edges. Initialize T= ;
Let E be the set of network edges.
while(E!= )&&（|T|！=n-1）{
Let (u,v) be a least cost edges in E.
E = E-{(u,v)}.//delete edge from E
if((u,v)does not create a cycle in T)
Add edge(u,v)to T.
}
if(|T|==n-1) T is a minimum-cost spanning tree.
else The network is not connected and has no spanning tree.template
bool UNetwork ::Kruskal ( EdgeNode) t[ ] )
{//Find a min cost spanning tree using Kruskal's method.
//Return false if not connected. If connected,return min spanning tree in t[0:n-2].
int n = Vertices();
int e = Edges();
//set up array of network edges
InitializePos(); // graph iterator
EdgeNode *E = new EdgeNode [e+1];
int k = 0; //cursor for E.
for (int i = 1; i <= n; i++){
//get all edges incident to i
int j;
T c;
First(i, j, c);
while(j){ //j is adjacent from i
if(i < j){ //add edge to E
E[++k].weight = c;
E[k].u = i;
E[k].v = j;
}
Next(i,j,c);
}
}
//put edges in min heap
MinHeap >H(1);
H.Initialize(E,e,e);
UnionFind U(n);// union/find structure
//extract edges in cost order and select/reject
k = 0;// use as cursor for t now.
while(e && k < n-1){
//spanning tree not complete & edges remain
EdgeNode x;
H.DeleteMin(x); //min cost edge
e--;
int a = U.Find(x.u);
int b = U.Find(x.v);
if(a != b){//select edge
t[k++] = x;
U.Union(a,b);
}
}
DeactivatePos();
H.Deactivate();
return (k == n - 1);
}
アルゴリズムの考え:ステップ選択によって最小生成ツリーを作成し、ステップ選択において一つの辺を選択します.ステップ毎のgreedy criterion:残りの端からコストが一番小さい辺を選び、選択した辺に入れて集めて木を作る.
ノート:Primは一歩ごとに獲得した入選の辺集はすべて1本の木を形成して、Kruskyalは一歩ごとに入選して辺集は1つの森林です.
疑似コード:
//Assume that the network has at least one vertex.
Let T be the set of selected edges.Initialize T =
Let TV be the set of vertices already in the tree. Set TV = {1}
Let E be the set of network edges.
while(E<> )&&(|T|<>n-1){
Let (u,v) be a least-cost edge such that u TV and v TV //
if(there is no such edge) break.
E=E-{(u,v)}.//delete edge from E
Add edge(u,v) to T.
}
if (|T| == n-1) T is a minimum-cost spanning tree.
else The network is not connected and has no spanning tree.i)問題説明
車を組み立てて、任務の間に相前後関係があります.このグループの任務と任務の先着順は図に示すことができます.AOV(activity on vertex)ネットワークといいます.頂点は任務を表します.
タスクには、図のいずれかのエッジ(i,j)があり、このシーケンスにおいて、タスクiは、ジョブjの前に必ず現れる.このような性質を持つシーケンスをトポロジカルシーケンスと呼ぶ.
トポロジ順序とは、図に従ってトポロジシーケンスを確立するプロセスをいう.
ii)貪欲な方法
貪欲な方法は、左から右へのステップに従ってトポロジーシーケンスを構築する.ステップごとに新しい頂点を選択して、シーケンスに追加します.新しい頂点を選択する根拠は、貪欲準則である.残りの頂点から頂点を選択するwは、頂点vがシーケンス内にない.つまり、wに端があれば、この辺はシーケンスから繋がっています.
上記の欲張り基準を満たさない頂点wが選択された場合、すなわち辺(v,w)の頂点vがシーケンスにないと、トポロジーシーケンスは構築されない.
疑似コード:
Let n be the number of vertices in the digraph.
Let V be an empty sequence
while(true){
Let w be any vertex that has no incoming edge (v,w) such that v is not in V.
if there is no such w,break.
Add w to the end of V.
}
if(V has fewer than n vertices) the algorithm fails.
else V is a topological sequence.