BFS,DFSを一つの関数で表したい
迷路を探索するコードをc++で書いているときにふと思った.
BFS,DFSアルゴリズムの本質的な違いはデータを入れるコンテナがStackかQueueかの違いのみ.ならばコードをキレイにしたいので２つのアルゴリズムを統合したい.
BFS,DFSがそれぞれ何かはググったほうが早いので省略するが,直感的な理解のために画像だけ載せておく.
ちなみに迷路でなく,一般にグラフに対して適応可能.
BFSによる迷路探索画像
DFSによる迷路探索画像
A*による迷路探索画像
BFSの実装
まずはBFSをつくる.迷路クラス（もしくは構造体）を作ってそのメンバ関数として実装するのが自然かと思われる.しかし,この記事で説明したいことの本質ではないので,迷路を作るのは省略して関数だけ書く.
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using PII = std::pair<int, int>;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
std::string start,goal,wall,path;
std::vector<std::vector<std::string>> maze;
int N;
void bfs(){
std::queue<PII> container;
bool isGoaled = false; // Goalに到達したかどうかを管理する変数.
container.push(std::make_pair(1,1)); // 地点(1,1)から探索を始める.
std::vector<std::vector<bool>> visited;
visited.assign(N,std::vector<bool>(N,false)); //visitedの初期化
while((!container.empty())&(!isGoaled)){ // containerの中身が空になるかゴールに到達するまでループ.
PII now;
now = container.front();
container.pop();
visited[now.first][now.second]=true;
for(int k=0;k<4;k++){ // 現在地nowから上下左右の探索.
int x,y;
x = now.first+dx[k];
y = now.second+dy[k];
// mazeは N×N行列.地点(x,y)が壁か,道か,スタートかゴールかの情報が入ってる.メンバ変数もしくはグローバル変数.
if(maze[x][y]==goal) {isGoaled=true; break;}
if((maze[x][y]==wall)|(visited[x][y]==true)) continue;
if(maze[x][y]==path) container.push(std::make_pair(x,y));
}
}
}
ここからさらに何をしたいのかによって機能を追加していく.ゴールまでの最短距離を求めるのか,ゴールまでの道を求めるのか,はたまたゴールできるか判定するだけなのか.それらについてはここでは触れない.適切な場所（特にif(maze[x][y]==foo)のあと）に文を追加すればいい.
BFSとDFSを一つの関数で表す.
結論としては,templateとif constexprを使えばうまく表現できた.templateをあまり使ったことがなかったのでいい勉強になった.
以下にコードの本質的な部分と,犯したミスを刻み同じようなミスを起こさないようにする.
// 省略
template <typename T>
void solve(){
T container;
bool isGoaled = false; // Goalに到達したかどうかを管理する変数.
container.push(std::make_pair(1,1)); // 地点(1,1)から探索を始める.
std::vector<std::vector<bool>> visited;
visited.assign(N,std::vector<bool>(N,false));
while((!container.empty())&(!isGoaled)){ // containerの中身が空になるかゴールに到達するまでループ.
PII now;
if constexpr (std::is_same<T, std::stack<PII> >{}) now = container.top();
else if constexpr (std::is_same<T, std::queue<PII> >{}) now = container.front();
container.pop();
visited[now.first][now.second]=true;
for(int k=0;k<4;k++){ // 現在地nowから上下左右の探索.
int x,y;
x = now.first+dx[k];
y = now.second+dy[k];
// mazeは N×N行列.地点(x,y)が壁か,道か,スタートかゴールかの情報が入ってる.メンバ変数もしくはグローバル変数.
if(maze[x][y]==goal) {isGoaled=true; break;}
if((maze[x][y]==wall)|(visited[x][y]==true)) continue;
if(maze[x][y]==path) container.push(std::make_pair(x,y));
}
}
}
int main(){
if(bfs) solve<std::stack<PII>>();
else if(dfs) solve<std::queue<PII>>();
}
犯したミス
ミス1：if文の中で変数を定義する.
if文の中で定義した変数のスコープはif文内なのでif文の外で使うことはできない.
基本的にはコードを書くときはスコープを狭めたい欲が出てくるので,if文内で定義できる変数はif文内で定義したほうがいいが今回のケースでは不適.
// 省略
void solve(){
//何らかの処理
if constexpr(bfs)
std::stack<PII> container;
else if constexpr(dfs)
std::queue<PII> container; // if文内で定義した変数であるcontainerはif文の外では使えない.
else
// bfs でも dfs でもない場合の処理.
}
templateを使う.
// 省略
template <typename T>
void solve(){
T container;
// 何らかの処理
}
int main(){
// 何らかの処理
if(bfs)
solve<std::stack<PII>>();
else if(dfs)
solve<std::queue<PII>>(); // 関数を呼び出す側で型を指定してあげる.
else
// bfs でも dfs でもない場合の処理.
}
ミス2：if文で型の分岐をする.
StackとQueueは入れた変数の取り出し方が異なる.
Stackはcontainer.top(),Queueはcontainer.front()でそれぞれコンテナにいれた
変数を取り出すが,この分岐をif文で行うとコンパイルエラーを起こす.
// 省略
template <typename T>
void solve(){
T container;
PII now;
container.push(make_pair(1,1));
while(!container.empty()){
if(std::is_same<T, std::stack<PII>>{})
now = container.top(); // コンパイルエラーを起こす.
else if(std::is_same<T, std::queue<PII>>{})
now = container.front(); // コンパイルエラーを起こす.
else
// stack でも queue でもない場合の処理.
container.pop();
// 何らかの処理
}
}
if文は中身が実行されるかに関わらず,共にエラーとならない文でないといけない.
if constexprを使う.
// 省略
template <typename T>
void solve(){
T container;
PII now;
container.push(make_pair(1,1));
while(!container.empty()){
if constexpr(std::is_same<T, std::stack<PII>>{})
now = container.top();
else if constexpr(std::is_same<T, std::queue<PII>>{})
now = container.front();
else
// stack でも queue でもない場合の処理.
container.pop();
// 何らかの処理
}
}
if文はコンパイル時に中身の評価が行われない一方で,if constexprはコンパイル時に中身を評価され
選択されないブランチはコンパイル時に排除されるようだ.
一見すると条件付きコンパイルのように思えるが,if constexprは選択されないブランチのテンプレートの実体化を抑制する機能になっている.
詳細はここでは触れない.
A*アルゴリズムの実装
厳密なA*アルゴリズムとはなんぞやとは一旦置いておいて,効率的にゴールを探すために現在地からゴールまでの距離（の推定値）が最も小さい順に迷路を進みたい.この場合でもコンテナにpriority_queueを用いることで簡単に実装できる.コードの流用ができて便利.ただし自分で距離とpriority_queueから値を取り出す順番だけは指定しないといけないので,今回はゴールと現在地のマンハッタン距離が小さい順に迷路を進んでいくようにした.
(ゴールの座標は既知とした.ゴールのだいたいの場所すらわからなかったらこの方法は使えない.)
またA*アルゴリズムというと（スタートから現在地までのコスト）＋（現在地からゴールまでのコストの推定値）が最小になる道を探索する方法だが今回は（スタートから現在地までのコスト）を０とした例として理解してもらいたい.
// 省略
// CompareDist内のGx, Gyはゴールの位置を表す.
class CompareDist{
public:
bool operator()(pair<int,int> p1, pair<int,int> p2){
int dist1 = abs(Gx-p1.first)+abs(Gy-p1.second);
int dist2 = abs(Gx-p2.first)+abs(Gy-p2.second);
return dist1 < dist2 ;
}
};
template <typename T>
void solve(){
T container;
PII now;
container.push(make_pair(1,1));
while(!container.empty()){
if constexpr (std::is_same<T, std::stack<PII> >{})
now = container.top();
else if constexpr (std::is_same<T, std::queue<PII> >{})
now = container.front();
else if constexpr (std::is_same<T, std::priority_queue<PII, vector<PII>, CompareDist> >{})
now = container.top();
// 何らかの処理
}
}
int main(){
if(bfs) solve<std::stack<PII>>();
else if(dfs) solve<std::queue<PII>>();
else if(A*) solve<std::priority_queue<PII, vector<PII>, CompareDist>>();
}
参考文献
自分がtemplateに弱かったのでtemplate関連で参考にしたLinkを載せておく.
明示的特殊化とテンプレート用語の解説
みんなも使おうif constexpr
Difference between “if constexpr()” Vs “if()”
constexpr ifの落とし穴
テンプレートの明示的 (完全) 特殊化
C++ で型によるコンパイル時条件分岐技法まとめ
テンプレートの特殊化 | Programming Place Plus
C++関数テンプレートと半順序とオーバーロード