ichirin2501's diary

いっちりーん。

隣接行列と迷路その2

/dev/null

隣接行列と迷路 - ichirin2501の日記のその後の顛末。


問題はこんな感じでした。

迷路のスタート地点からゴール地点までの最小ステップ数とその経路数を求める。
経路の出力は行わない。

前回は、BFS Algorithm, Warshall-Floyd Algorithm　の2種類で解きました。
別のアルゴリズムでも解いてみようということで、Dijkstra Algorithm　でも解いてみた。

#include <iostream>
#include <queue>
#include <climits>
#include <functional>
#include <string>
using namespace std;

#define mp make_pair
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)

typedef pair<int,int> pii;

int node[64][64];
int visit[64];

pii dijkstra(int n, int s, int g){
	int gc = INT_MAX;
	int cnt = 0;
	priority_queue<pii , vector<pii>, greater<pii> > q;
	
	if( s==g ) return mp(0,1);
	
	q.push(mp(0,s));
	while( !q.empty() ){
		int now_cost = q.top().first;
		int now_node = q.top().second;
		q.pop();
		if( gc<now_cost ) break;
		rep(i,n)if( node[now_node][i]!=INT_MAX && visit[i]>=now_cost+node[now_node][i] ){
			int t = now_cost + node[now_node][i];
			if( i==g ){
				if( visit[i]==t ){
					cnt++;
				}else if( visit[i]>t ){
					cnt = 1;
					gc = t;
				}
			}
			q.push(mp(t, i));
			visit[i] = t;
		}
	}
	
	return mp(gc==INT_MAX?-1:gc, cnt);
}

int main(){
	int n,s,g,a,b,c;
	string T;

	while(getline(cin,T)){
		cin>>n>>s>>g;
		rep(i,64)rep(j,64)node[i][j]=INT_MAX;
		rep(i,64)visit[i]=INT_MAX;
		while(cin>>a>>b>>c,a|b|c){
			node[a][b] = c;
		}
		cin.ignore();
		
		pii ans_dij = dijkstra(n,s,g);
		printf("%s  ::  %d->%d , step:%d , cnt:%d\n",T.c_str(), s, g, ans_dij.first, ans_dij.second);
	}
	
	return 0;
}


BFS Algorithmと大差ないですね。
main関数の入力処理が違うのは、重み付き有効グラフのデータで処理してた名残ですｗ。


Bellman-Ford Algorithmでも解こうとしてだめでした。
グラフが負の閉路を持たないとき、最短経路の辺の個数は最大でも頂点の個数より1個少ない。
Bellman-Ford Algorithmはこの性質を利用します。
ある地点のコストが更新されたからと言って、それが最短経路に含まれてるかどうかはわからない。
重複して処理される最短経路の精確な回数を単純な更新の有無からでは判断できません（たぶん）。
強引に処理すれば出来るのかもしれませんが、Bellman-Fordの処理に挟む程度では無理じゃないかと思います。
できるのでしたら教えてください…。


計3種類のアルゴリズムで解いた感想ですが、各々のアルゴリズムとしての本質が見えた気がします。
今までは最短経路のコストか、その経路の出力ぐらいしかやってきませんでした。
今回、経路数を求めるプログラムを書いたことで気付いた点がいくつもあったので収穫です。


えーっと、

迷路のスタート地点からゴール地点までの経路数がM個以上になる最小ステップ数を求める。

という問題を前回に妄想しました。
有向グラフのときは二分探索とべき乗計算の組み合わせで良いでしょ、とか言ってすみませんでしたｗ
なんかだめだったｗ


もし二分探索で選択した指数kで計算した行列の要素に、値M以上の値が出てきても、
既にi->jとして出現した値なのか、それともまだなのかの判別ができない。
そこで、行列の要素に値M以上が出てきた段階で二分探索をやめ、普通に行列をかける処理と逆行列をかけて戻る処理を同時に行うことで
求めようと考えた。が、そもそも逆行列を求めるがめんどくさい。
なので、行列の全ての要素が値M以下になる状態まで二分探索を行い、その後、経路i->jまでのパターン数がM以上になるまで掛ける処理にした。


二分探索とメモ化で実装したので、単純に掛ける処理と比較すると、最悪ケースでは2〜3倍の違いが出た。
二分探索してるのにどうしてこんなに遅いのか…ということだが、
二分探索を開始する際に、最大の回数がはっきりとわからない。
最悪でも全てのノードを通れば一周することが出来る。とは言え、サイクル状だと常に1でぐるぐる周るだけだけどｗ
という理由で、とりあえず、M*ノード数を二分探索開始時の最大値に設定した。
結果、計算量が膨大になってしまい、劇的に速くなることはなかった。
増加率についてはグラフの状態に依存するから、それを元に二分探索の値を調節すれば〜
って思ったけど、それがわかれば狙い打ちできそうだな。