ichirin2501's diary

いっちりーん。

隣接行列と迷路

/dev/null

その後の顛末について　隣接行列と迷路その2 - ichirin2501の日記


ちょうど隣接行列について調べてて、こんな記事を見かけたので自分も書いてみようと思った。

迷路を隣接行列で攻略（part1） - 似非学問的な手記


問題についてはid:g940425さんの記事に書かれていますが、
今回自分がやったのでは、

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

です。
書かれてるように、普通なら幅優先探索とかA*アルゴリズムで解くのが一般的。
注意することは、経路数も求めたいのでゴールに到達しても、すぐに探索を打ち切ってはだめ、ということだけです。
同じステップ数の状態を調べてから探索終了ですね。


えっと…、まぁそれだけでしょうｗ
まずは幅優先。ノード数は64個までという暗黙の了解で。

#include <iostream>
#include <queue>
#include <climits>
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)

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

pair<int,int> bfs(int n, int s, int g){
	queue<pair<int,int> > q;
	bool flag = false;
	int cnt = 0;
	
	if( s==g ) return mp(0,1);
	visit[s] = 0;
	q.push(mp(s,0));
	while( !q.empty() ){
		int now = q.front().first;
		int step = q.front().second;
		q.pop();
		rep(i,n)if( node[now][i] && visit[i]>=step+1 ){
			if( i==g ){
				flag = true;
				cnt++;
			}
			if( !flag )q.push(mp(i,step+1));
			visit[i] = step+1;
		}
	}
	return mp(visit[g]==INT_MAX?-1:visit[g], cnt);
}

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

	memset(node,0,sizeof(node));
	
	cin>>n>>s>>g;
	while(cin>>a>>b){
		node[a][b] = node[b][a] = 1;
	}
	
	rep(i,n)visit[i] = INT_MAX;

	pair<int,int> ans_bfs = bfs(n,s,g);
	printf("%d->%d , step:%d , cnt:%d\n",s,g,ans_bfs.first,ans_bfs.second);

	return 0;
}


面白みが全くない。


競技プログラミングにおいては最短経路を求める伝家の宝刀があります（個人的に）。


わーしゃるふろいどあるごりずむ〜(Warshall-Floyd Algorithm)


なぜ伝家の宝刀なのかと言うと、短く書けるからです。
競技プログラミングではシビアな実行速度が求められることは殆どありません。
アルゴリズムが概ね合ってればなんとかなるように問題が作られています。（はず


というわけで、Warshall-Floyd Algorithmでも解いてみました。
以下のコードはバグありでした。修正するまでお待ちくださいorz
修正した！
重み付きなしのグラフだと以前のコードでも動くが、有りのグラフだとバグがあったので修正。
バグが多すぎて笑えない
バグ多すぎて笑えない。
スタート地点とゴール地点が同一の場合、経路数0と出力してたバグを修正。あるある勘違いの類…。BFS側も合わせて修正。
ここまでバグが多いと、もはや演出。

#include <iostream>
#include <queue>
#include <climits>
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)

int node[64][64];

pair<int,int> warshall(int n, int s, int g){
	int cnt = 0;
	int sum[64][64];
	memset(sum,0,sizeof(sum));
	if( s==g ) return mp(0,1);
	rep(i,i)node[i][i]=0;
	rep(i,n)rep(j,n)if( node[i][j]!=INT_MAX )sum[i][j]=1;
	
	rep(k,n)rep(i,n)rep(j,n)if( node[i][k]!=INT_MAX && node[k][j]!=INT_MAX ){
		if( node[i][j]==node[i][k]+node[k][j] ){
			node[i][j] = node[i][k]+node[k][j];
			sum[i][j] += sum[i][k]*sum[k][j];
		}else if( node[i][j]>node[i][k]+node[k][j] ){
			node[i][j] = node[i][k]+node[k][j];
			sum[i][j] = sum[i][k]*sum[k][j];
		}
	}
	
	return mp(node[s][g]==INT_MAX?-1:node[s][g],sum[s][g]);
}

int main(){
	int n,s,g,a,b;
	
	rep(i,64)rep(j,64)node[i][j]=INT_MAX;
	
	cin>>n>>s>>g;
	while(cin>>a>>b){
		node[a][b] = node[b][a] = 1;
	}
	
	pair<int,int> ans_warshall = warshall(n,s,g);
	printf("%d->%d , step:%d , cnt:%d\n",s,g,ans_warshall.first,ans_warshall.second);

	return 0;
}


Warshall-Floyd Algorithmなので計算量はO(n^3)ですね。
i->k までの経路数と k->j までの経路数を掛け合わせれば i->j の経路数となります。
ただし、最小ステップに更新されたときは掛けた経路数に更新、最小ステップと等しいときは掛けた経路数を加算
の場合分けが必要になることに注意です。（この一文は追記）
さらに追記：(なんか色々修正してたら長くなった…)


これまでは「iからjまでの最小ステップ数」でしたが、

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

という問題になった場合を考えてみます。
その前に、

重みなしグラフ G の隣接行列を A とすると、A^n で表される行列の (i, j) 成分は、i から j への相違なる長さ n の路の数と等しい

隣接行列にはこのような性質があります。（まさかWikiに書いてあるとは…引用してきた)


この性質を利用して、
迷路のスタート地点からゴール地点までの経路数がM個以上になるまで隣接行列をかけていくことで求めることもできます。
行列の掛け算はn^3ですので、もしMが大きい値の場合は毎回掛けて確かめるため時間がかかります。


…と、思ったんだけど、パターン数の増加率のほうがずっと大きいから大丈夫？


数値を見てみた。kの値はA^kの指数


図1

k:1
                0                 1                 1
                1                 0                 1
                1                 1                 0

k:2
                2                 1                 1
                1                 2                 1
                1                 1                 2

k:48
   93824992236886    93824992236885    93824992236885
   93824992236885    93824992236886    93824992236885
   93824992236885    93824992236885    93824992236886

k:49
  187649984473770   187649984473771   187649984473771
  187649984473771   187649984473770   187649984473771
  187649984473771   187649984473771   187649984473770


図2

k:1
       0        1        0
       1        0        1
       0        1        0

k:2
       1        0        1
       0        2        0
       1        0        1

k:48
 8388608        0  8388608
       0 16777216        0
 8388608        0  8388608

k:49
       0 16777216        0
16777216        0 16777216
       0 16777216        0


図3

k:1
             0              1              0              0
             1              0              1              0
             0              1              0              1
             0              0              1              0

k:2
             1              0              1              0
             0              2              0              1
             1              0              2              0
             0              1              0              1

k:48
    2971215073              0     4807526976              0
             0     7778742049              0     4807526976
    4807526976              0     7778742049              0
             0     4807526976              0     2971215073

k:49
             0     7778742049              0     4807526976
    7778742049              0    12586269025              0
             0    12586269025              0     7778742049
    4807526976              0     7778742049              0


図4

k:1
   0  1  1  0
   1  0  0  1
   0  0  0  1
   0  0  1  0

k:2
   1  0  0  2
   0  1  2  0
   0  0  1  0
   0  0  0  1

k:48
   1  0  0 48
   0  1 48  0
   0  0  1  0
   0  0  0  1

k:49
   0  1 49  0
   1  0  0 49
   0  0  0  1
   0  0  1  0


無向グラフの場合、普通に掛けて行っても増加数が多いので問題ないと思われる。
有向グラフの場合、殆ど増加しないパターンが存在するため、二分探索とべき乗計算の組み合わせで解くほうが良いと思われる。


合ってるかどうかは知らないｗ