世界の隅の開発室

 

◎  スポンサーサイト 

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

◎  【C++】ダイクストラ法最短経路探索・通常実装と優先度付きキュー実装比較 

うちの部の勉強会で、ダイクストラ法を扱うことになったので
コードを書いてみました。

ダイクストラ法は
通常の場合、Vをノードの数、Eを辺の数として、オーダーはO(V^2)なのですが
二分ヒープ優先度付きキューだとO((E+V)logV)
フィボナッチヒープ優先度付きキューだとO(E+VlogV)になるとか。

なので、実際に実装して速度を比較してみました。
C++11で開発してます。

includeはこんな感じ。


#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>


まず、通常実装のDijkstra。


std::vector<int> dijkstra(std::vector<std::vector<int>> &distanceTable)
{
int at;
std::vector<int> prev(distanceTable.size());
std::map<int,int> ensemble;


for(int i=0;i<distanceTable.size();i++){
ensemble.insert(std::pair<int,int>(i, 1e5));
}
ensemble[0]=0;
while(ensemble.size()!=0){
auto nodeItr = min_element(ensemble.begin(),ensemble.end(),[&](std::pair<int, int> lhs,std::pair<int, int> rhs){
return lhs.second < rhs.second;
});
at = nodeItr->first;
for(int i=0;i<distanceTable[at].size();i++){
if(ensemble.find(i)!=ensemble.end() && distanceTable[at][i]!=0){
if(ensemble[i] > ensemble[at]+distanceTable[at][i]){
ensemble[i] = ensemble[at]+distanceTable[at][i];
prev[i] = at;
}
}
}
ensemble.erase(nodeItr);
}
return prev;
}



まあこんな感じですかね。
引数は後述しますが探索するグラフです。
グラフの形式にハッシュテーブルを採用しました。


次にpriority_queue版です。
std::priority_queueは、ParingHeapを採用しておりますので、フィボナッチヒープと同等のスコアがでます。



std::vector<int> dijkstra_withPriority(std::vector<std::vector<int>> &distanceTable)
{
int at;
std::vector<int> prev(distanceTable.size());
std::priority_queue<std::pair<int,int>> ensemble;
std::map<int,int> graph;

for(int i=0;i<distanceTable.size();i++){
graph.insert(std::pair<int,int>(i, 1e5));
}

graph[0]=0;

ensemble.push(std::pair<int,int>(0,0));

while(ensemble.size()!=0){
at = ensemble.top().first;
ensemble.pop();
for(int i=0;i<distanceTable[at].size();i++){
if(distanceTable[at][i]!=0){
if(graph[i] > graph[at] + distanceTable[at][i]){
graph[i] = graph[at] + distanceTable[at][i];
prev[i] = at;
ensemble.push(std::pair<int,int>(i,graph[i]));
}
}
}
}
return prev;
}




ちょっと気持ち悪い書き方してるとこありますが気にせずいきましょ。

ぱっと見そんなアルゴリズムに違いは見られませんが
min_elementでの探索と、top()取り出しの部分で、大きく速度に差がでそうです。



int main(){
const int node_num=11;
const int target = 10;
std::vector prev;
std::vector> distanceTable(node_num,std::vector(node_num));
distanceTable[0]={0,7,6,0,0,0,0,0,0,0,0};
distanceTable[1]={7,0,0,5,0,0,0,0,0,0,0};
distanceTable[2]={6,0,0,2,3,0,1,0,15,0,0};
distanceTable[3]={0,5,2,0,5,0,0,0,0,24,0};
distanceTable[4]={0,0,3,5,0,8,0,0,0,0,0};
distanceTable[5]={0,0,0,0,8,0,2,7,0,0,0};
distanceTable[6]={0,0,1,0,0,2,0,0,9,0,0};
distanceTable[7]={0,0,0,0,0,7,0,0,0,5,0};
distanceTable[8]={0,0,15,0,0,0,9,0,0,5,0};
distanceTable[9]={0,0,0,24,0,0,0,5,5,0,1};
distanceTable[10]={0,0,0,0,0,0,0,0,0,1,0};

std::clock_t time = std::clock();
prev = dijkstra(distanceTable);
std::cout << "Dijkstra " << static_cast( std::clock() - time )/1e3 << "[ms]" << std::endl;
time = std::clock();
prev = dijkstra_withPriority(distanceTable);
std::cout << "Dijkstra with Priority_queue " << static_cast( std::clock() - time )/1e3 << "[ms]" << std::endl;

int at=target;
while(true){
std::cout << at << ' ';
if(at==0)break;
at = prev[at];
}

}



テーブル作成部分気持ち悪いですけどおおめに見て下さい()
返り値は、あるノードに対する最短経路上の直前のノードが格納されてますので
まあ再帰なり、あるいは自己代入で通った道筋が分かります。

ついでに時間を計測してます。

実際に勉強会で用いたスライドより、このテーブルが意味するグラフをのっけときます


Dijkstra.jpg



実行結果は

Dijkstra 0.127[ms]
Dijkstra with Priority_queue 0.059[ms]
10 9 8 6 2 0

経路はたぶんあってます。(aが0、bが1...と脳内で置換してください)
実行速度にかなり差が出てますね。
倍以上違います。

ただ、何十回かテストをすると
大体1.3~1.5倍程度にスコアは落ち着くようです。


凄いですねえ。


では、今回はこの辺で。


スポンサーサイト

◎  金属棒切り出し問題 トップダウン方式とボトムアップ方式 

前回は、金属棒切り出し問題において、全探索における指数爆発の説明を行った。
整数回分割条件下で、長さ30の金属棒の最適分割ですら計算に数分かかるようでは、話にならない。
オーダーはO(2^n)であり、長さが1増える度に計算量は2倍になる。

ここまで非効率な理由は、同じ部分問題を何度も解いているせいだと述べた。
これを解決する方法として、トップダウン方式とボトムアップ方式の2種類がある。これらを実装して、高速化を図ろう。


トップダウン方式はとても簡単な考え方である。
計算過程で、lengthに対する計算結果の表を作っておけば、毎回その表の対応するlengthが未知か既知か確かめることによって、同じ部分問題、すなわち引数lengthの値が同じときのCut_Rodにおいて同じ計算をする必要がなくなる。



int Cut_Rod_Aux(int table[],int length,int* r){
int price=-1;
if(r[length]>=0)return r[length];
if(length==0)price=0;
else{
for(int i=1;i<=length;i++){
price=bigger(price,price_table(i,table)+Cut_Rod_Aux(table,length-i,r));
}
}
r[length]=price;
return price;
}

int Memorized(int table[],int length){
int *r = new int[length+1];
int price;
for(int i=0;i<=length;i++){
r[i]=-1;
}
price = Cut_Rod_Aux(table,length,r);
delete(r);
return price;
}


Memorized関数において宣言したr配列が、lengthと計算結果の表にあたる。
値が既知の場合は非負整数であることは保障されているので、Cut_Rod関数においてr[length]の値の正負を確かめるだけで良い。


続いて、ボトムアップ方式も解説する。
こちらは、計算される部分問題がそれより小さい部分問題にのみ依存する構造である。
全ての部分問題をサイズ(この"サイズ"は命題に依存する抽象的な概念である)についてソートし、小さいものが解いていくことによって、これは実装される。
未知の部分問題を解く環境下では、前提の部分問題は全て解決済みとなる。

では、実装してみよう。
コードはトップダウンより簡潔である。



int BottomUp_Cut_Rod(int table[],int length){
int *r = new int[length+1];
int price=-1;
r[0]=0;
for(int j=1;j<=length;j++){
for(int i=1;i<=j;i++){
price=bigger(price,price_table(i,table)+r[j-i]);
}
r[j]=price;
}
return r[length];
}



iするとこのプログラムはサイズがj=0,1,2....lengthの部分問題をこの順序で解く。

ボトムアップ方式では再帰的にj-iのサイズを計算する代わりに、r[j-i]を直接参照する。
これが可能な理由は、解く部分問題の前提部分問題は解決済みということが保障されているからである。
price変数にはj=0....lengthにおいて毎回現在の値と新しい計算結果が比較され、大きい方をとり末尾に追加する。
即ち全計算終了後、rの末尾要素が最適値となる。

これらを実行すると、なんとどちらも長さ1000ですら20ms前後で計算が終了する。
計算される部分問題が未解決であることが保障されているボトムアップは、関数を再帰的に呼び出して表と比較するトップダウンに比べ関数呼び出しのオーバーヘッドが小さいため若干早いが、この2つの速度は漸近的に同一である。

ボトムアップ方式で考えると、二重ループ構造からオーダーはO(length^2)であると分かる。
O(2^length)とO(length^2)、この2つは似ているようで値は天と地ほど違う。


折角なので、どのように分割されたのかも保存できるようにしよう。


int BottomUp_Cut_Rod(int table[],int length,int parts[]){
int *r = new int[length+1];
int price=-1;
r[0]=0;
for(int j=1;j<=length;j++){
for(int i=1;i<=j;i++){
if(price<price_table(i,table)+r[j-i]){
price=price_table(i,table)+r[j-i];
parts[j]=i;
}
}
r[j]=price;
}
return r[length];
}


実行結果は以下のようになった(入力は25とした)
25
max price = 73
---------divided---------
2
2
3
2
2
3
2
2
time is 0 [ms]


実行時間が早過ぎて時間の計測に失敗しているが、それだけ高速ということである。
全探索のCut_Rodは2300msかかったのだ。その速度差は一目瞭然だろう。


では、また次のテーマで。


参考文献:世界標準MIT教科書 アルゴリズムイントロダクション






◎  動的計画法と指数爆発-トップダウンやボトムアップによる高速化- 

ある金属棒がある。
この金属棒は長過ぎる為に、複数ある規定のどれかの長さにカットして出荷しなければならない。
また、金属棒の規定長さに対する値段の表は存在するが、金属棒の長さと値段は比例の関係を持たないとする。
この金属棒をもっとも高く売るためにはどう切り分けたら良いのだろうか。

残念ながら人間には計算は難しい。

しかし、一方PCの力を借りて全探索を行えば、最適解は簡単に算出できる。
この時の簡単というのは、あくまでアルゴリズムとしての簡単であり、計算量とは別問題である。

実際にこの問題を解いてみる。

考え方は単純、長さnの金属棒をk個に分割するとして
n = i1 + i2 + ... + ik
とn(金属棒の長さ)は分割される。

このときこのk個の分割が最適な切り分けであると仮定すると
P[x]がxの長さの金属棒の値段を示す手続きであるとして

R[n] = P[i1] + P[i2] + ... + P[ik]

k分割した金属棒の値段の和を示す関数R[x]は最適ということになる。

当然、この分割組み合わせは当然未知である。

しかしこの時、可変長引数を取り、もっとも最大のものを返す関数MAX[...]を定義すると
長さnの金属棒が最適分割によって得られる最大の値段R[n]は

R[n] = MAX[P[n],R[1]+R[n-1],R[2]+R[n-2],...,R[n-1]+R[1]]

と再帰的に表現できる。(最初の引数は分割なしということ)
即ち金属棒を長さLに切り分けた時、
R[L]とR[n-L]のうち、前者を確定した金属棒、後者を分割の余地がある金属棒として
Lについて全ての場合を考えた時に、全ての通りにおけるR[x]が計算できるのである。

この時Lの全ての通りのR[x]を比較し、最大のものが、もっとも最適なL、つまりはR[n] = R[L]+R[n-L]を満たすのである。

実際にコードを書いてみよう(c++)。
実装は非常に簡潔である。



#include<iostream>
using namespace std;

const int TABLESIZE=10;

inline int bigger(int n1,int n2){
return (n1>n2)? n1 : n2;
}

inline int price_table(int i,int table[]){
return (i>TABLESIZE)? 0 :table[i];
}

int Cut_Rod(int table[],int length){
int price=-1;
if(length==0)return 0;
for(int i=1;i<=length;i++){
price=bigger(price,price_table(i,table)+Cut_Rod(table,length-i));
}
return price;
}

int main(){
int table[11]={0,1,5,8,9,10,17,17,20,24,30};
int length;
cin >> length;
cout << "max price = " << Cut_Rod(table,length) << endl;
return 0;
}


mainで入力するstick_lengthは金属棒の長さを表しており
priuce_tableが今回の金属棒の長さと値段の表である。(長さ0の値段は0としている)
表の値段
Cut_Rod関数は再帰的に呼び出される。
あるlengthにおける最大値priceを返すCut_Rodは、lengthの全ての通りを計算する為再帰的に呼び出され、最終的にlengthの値をただ一つ定め、priceを返す。
MAXの実装は不可能(恐らく)であるため、単純な比較関数biggerとforループを組み合わせMAXと等価のはたらきをさせている。

これを実際に実行し時間を計測すると、おおよそstick_lengthが15以下の場合は1ms以下で計算できるが
20程度になると約80msと跳ね上がり、25と5増やすだけで約2300msという結果をたたき出す。
それ以上は時間の無駄であるので計測していないが、想像し得ないほどの長い時間がかかるということは明らかである。
これはプログラムが全探索を行っている性質上、切り分け方の通りが2^(2*stick_length-1)であるため、計算時間が指数爆発を起こすためである。

ここまで非効率な原因は、Cut_Rod関数が同じ部分問題を解いているため、即ち、関数R[x]が同じxについて何度も計算されているためである。

これらを解決する方法を、次回解説する。













back to TOP

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。