幅優先探索と深さ優先探索

haba.jpg

コンピュータの良い点は、計算能力が人と比べて高い点です。

例えば、1から100までの和を計算する際、人にとっては

1+2+3+…+100

の計算はたいへんどころか、計算ミスをするでしょう。

一方、コンピュータなら簡単です。

ですから、コンピュータを使うことで、面倒な計算を瞬時にできるわけです。

ここでは、幅優先探索や深さ優先探索という面倒な計算をコンピュータにやらせます。

問題

整数a_{1},a_{2},\cdots,a_{n}があります。

その中からいくつか選び和がkとすることはできますか?

問題の説明

例えば、n=3として、1,3,13という数列があったとします。

そして、k=16とします。この場合は、

3+13=16

となるので、答えは「ある」ということになります。

解法1(幅優先探索)

一番はじめに思いつくのが、

a_{1}を含めるか?

含めた際に、和はkになっているか?

a_{2}を含めるか?

含めた際に、和はkになっているか?

a_{n}を含めるか?

含めた際に、和はkになっているか?

とすることです。これを図示すると以下のようになります。

Haba

上の層から判定していく方法であることがわかります。これを幅優先探索といいます。

プログラム

#include <stdio.h>
#include <iostream>
using namespace std;

int a[100];
int n,k;

bool solve(){
	int i,j,sum,q_size;
	sum=0;
	queue q;
	if(sum==k)return true; //kが0ならtrueを返す
	q.push(sum); //キューに入れる
	for(i=0;i<n;i++){ //a[i]を足すかでループ
		q_size=q.size();
		for(j=0;j<q_size;j++){//キューの数だけループ
			//キューの値を入手
			sum=q.front();
			q.pop();
			//和がkならtrueを返す
			if(sum+a[i]==k)return true;
			//キューに入れる
			q.push(sum+a[i]);
			q.push(sum);
		}
	}
	return false;
}

int main(void){
	int i;
	//値の入力
	cout<>n;
	cout<>k;
	for(i=0;i<n;i++){
		cout<<"a["<<i<>a[i];
	}
	//結果の出力
	if(solve())cout<<"解はあります。\n";
	else cout<<"解はありません。\n";
	return 0;
}

解説

幅優先探索にはキューを使います。

まず、nだけループさせて、徐々に深みに入っていきます。

そして、1つ前の層の総和をキューqに記憶しておきます。

次の層に進む際に、キューに入れておいた総和使います。

解法2(深さ優先探索)

次の方法は幅優先探索と違って、縦方向に判定していく方法です。

これを深さ優先探索といい、以下のように図示することができます。

深さ優先探索

プログラム

#include <stdio.h>
using namespace std;

int a[100];
int n,k;

bool solve(int i,int sum){
	//最後なら
	if(i==n)return sum==k;
	//a[i]を使う場合
	if(solve(i+1,sum+a[i]))return true;
	//a[i]を使わない場合
	if(solve(i+1,sum))return true;
	//a[i]によらないのでfalseを返す
	return false;
}

int main(void){
	int i;
	//値の入力
	cout<>n;
	cout<>k;
	for(i=0;i<n;i++){
		cout<<"a["<<i<>a[i];
	}
	//結果の出力
	if(solve(0,0))cout<<"解はあります。\n";
	else cout<<"解はありません。\n";
	return 0;
}

解説

関数solveの中身を見ていきましょう。

solveでは再帰関数としてはたらいています。

iが深さで、sumが足した合計です。

if(i==n)return sum==k;

で深さが最終まで来た際の命令を表しています。そして、

if(solve(i+1,sum+a[i]))return true;

でa[i]を足した場合へと進んでいます。

if(solve(i+1,sum))return true;

ではa[i]を足さなかった場合へと進みます。

計算の流れを見ると、深さ優先探索になっていることがわかります。

solve(0,0)->solve(1,a[0])->solve(2,a[0]+a[1])->solve(3,a[0]+a[1]+a[2])->…->solve(n-1,a[0]+…+a[n-1])->solve(n-1,a[0]+…+a[n-2])->solve(n-2,a[0]+…+a[n-3])->solve(n-1,a[0]+…+a[n-3]+a[n-1])->…

著者:安井 真人(やすい まさと)