最弱最遅サルゴリズマー

突然だが今回は最強の探索『ボゴ探索』について説明しようと思う。正直寒い

ボゴ探索(勝手に命名)の紹介

(どうでもいいことだがこれからの説明はボゴ探索が最大のパフォーマンスを発揮したと仮定する。)

このアルゴリズムを終えた後のdepthの中の値がゴール到達に必要な最小手数である。
その割にメモリは探索するものの最低限必要な情報だけ。しかもかなり高速。

例えば上下左右にだけ移動できる迷路とか探索する場合、ボゴ探索部分は以下のソースな感じだけでいける。

y = (スタート地点のY座標);
x = (スタート地点のX座標);
depth = 0;

/* data[][] は マップの情報 */
while(data[y][x] != (ゴール地点) ){
	switch( (乱数)%4 ){
		case 0:
			if(data[y+1][x] != (壁) ){ y++; depth++; }
		break;
		case 1:
			if(data[y-1][x] != (壁) ){ y--; depth++; }
		break;
		case 2:
			if(data[y][x+1] != (壁) ){ x++; depth++; }
		break;
		case 3:
			if(data[y][x-1] != (壁) ){ x--; depth++; }
		break;
	}
}

これだけです。超シンプル。超高速、超ヤバイ。

ボゴ探索の素晴らしさに納得できないおバカさんのための証明『ボゴ探索は必ず最小手数を返す』

ボゴ探索で迷路を探索する場合にゴール到達に必要な最小手数を返さないと仮定します。

しかし、下記の迷路でこのアルゴリズムを実行すると必ずゴール到達に必要な最小手数である1がdepthに代入される。

この時点で仮定は明らかに誤っているので、ボゴ探索は必ず最小手数を返すことが証明される。(証明おわり)

(Sはスタート,Gはゴール,#は壁)

####

#SG#

####

尚、最悪計算時間はO(∞)だが、最大のパフォーマンスを発揮することを信じて使うので考慮しない。また、高速で乱数を生成できる手段が必要である。