はじめに
Puzzle DE Go! は、パズルを題材に Go 言語でプログラミングを楽しみましょう、というお気楽なページです。どのプログラミング言語でもそうですが、上達の秘訣は実際にプログラムを作って、その動作を確認してみることです。ところが、いざとなると「さて、何を作ろうか？」と困ってしまう方も多いのではないでしょうか。
このようなときにぴったりな題材が「パズルの解法」です。なんといっても、実際にパズルが解けたときの喜びはとても大きく、プログラムを作る意欲をかきたててくれます。そして、解を求めるだけではなく、実行時間を短縮するためにプログラムを改良するのです。これがパズルプログラミングの醍醐味といってもいいでしょう。
簡単なパズルは力任せでも解くことができますが、少し複雑なパズルになると力任せでは時間がかかってしまいます。ところが、パズルの性質や特徴を見極めてプログラムを作ると、実行時間を劇的に短縮できる場合があります。プログラミングに興味をお持ちの方は、ぜひパズルの解法にも挑戦してみてください。
今回は「経路の探索」を例題に、パズルを解くのに必要となる基本的なデータ構造とアルゴリズムについて説明します。
●グラフ
まず最初に「グラフ (graph)」というデータ構造を説明します。一般にグラフというと、 円グラフや折れ線グラフといった図表を思い出す人が多いと思います。数学の「グラフ理論」では、いくつかの点とそれを結ぶ線でできた図形を「グラフ」といいます。次の図を見てください。
図 : グラフの例
上図に示すように、グラフは点とそれを接続する線から構成されています。点のことを「頂点 (vertex)」や「節点 (node)」と呼び、線のことを「辺 (edge)」や「弧 (arc)」と呼びます。グラフには 2 種類あって、辺に向きの無いグラフを「無向グラフ」といい、辺に向きがあるグラフを「有向グラフ」といいます。有向グラフは一方通行の道と考えればいいでしょう。 次の図を見てください。
図 : 有向グラフと無向グラフ
たとえば、図 (1) では A 地点から B 地点へ行くことができますが、一方通行のため B 地点から A 地点に戻ることはできません。これが有効グラフです。(2) の無効グラフでは、A 地点から B 地点へ行くことができるし、逆に B 地点から A 地点に戻ることもできます。
データ間のさまざまな関係を表す場合、グラフはとても役に立ちます。たとえば、下図のように経路をグラフで表すことができます。
図 : 経路図
上図ではアルファベットで頂点を表しています。この例では経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。
●隣接行列と隣接リスト
グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。経路図を隣接行列で表すと次のようになります。
│A B C D E F G ─┼─────── A│0 1 1 0 0 0 0 B│1 0 1 1 0 0 0 C│1 1 0 0 1 0 0 D│0 1 0 0 1 1 0 E│0 0 1 1 0 0 1 F│0 0 0 1 0 0 0 G│0 0 0 0 1 0 0 図 : 隣接行列
A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。これを Go 言語でプログラムすると、次のようになります。
リスト : 隣接行列
var adjacent = [][]int{
{0, 1, 1, 0, 0, 0, 0}, // A
{1, 0, 1, 1, 0, 0, 0}, // B
{1, 1, 0, 0, 1, 0, 0}, // C
{0, 1, 0, 0, 1, 1, 0}, // D
{0, 0, 1, 1, 0, 0, 1}, // E
{0, 0, 0, 1, 0, 0, 0}, // F
{0, 0, 0, 0, 1, 0, 0}, // G
}
頂点 A から G を数値 0 から 6 に対応させるところがポイントです。隣接行列は 2 次元配列 (Go 言語ではスライスのスライス) で表します。
隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これはつながっている頂点を格納する方法です。
A => (B, C) B => (A, C, D) C => (A, B, E) D => (B, E, F) E => (C, D, G) F => (D) G => (E) 図 : 隣接リスト
これを Go 言語でプログラムすると次のようになります。
リスト : 隣接リスト
const (
A = iota
B
C
D
E
F
G
Size // 頂点の個数
)
var adjacent = [][]int{
{B, C}, // A
{A, C, D}, // B
{A, B, E}, // C
{B, E, F}, // D
{C, D, G}, // E
{D}, // F
{E}, // G
}
隣接行列と同様に、頂点 A から G を数値 0 から 6 に対応させています。これを const で定義しています。このように、Go 言語ではスライスを使うと簡単に隣接リストを表すことができます。
ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。
●バックトラックによる探索
それでは簡単な例題として、地図上の A 地点から B 地点までの道順を求めるプログラムを作ってみましょう。「探索」にはいろいろな種類があります。パズルを解くプログラムも、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法が「バックトラック (backtracking)」です。もちろん、経路の探索もバックトラックで解くことができます。
今回は隣接リストを使って、A から G までの経路をバックトラックで求めます。バックトラックを再帰呼び出しで実現する場合、次の頂点へ進むことを再帰呼び出しに対応させるのがポイントです。たとえば、経路を探索する関数を search としましょう。search は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。そして、A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。
それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、一つ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。
それでは具体的に説明しましょう。経路はスライスに頂点を格納して表すことにします。プログラムは次のようになります。
リスト : 深さ優先探索
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x { return true }
}
return false
}
func dfs(goal int, path []int) {
n := path[len(path) - 1]
if n == goal {
fmt.Println(path)
} else {
for _, x := range adjacent[n] {
if !member(x, path) {
dfs(goal, append(path, x))
}
}
}
}
func depthFirstSearch(start, goal int) {
path := make([]int, 0, Size )
dfs(goal, append(path, start))
}
関数 depthFirstSearch は start から goal までの経路を求めます。実際の処理は関数 dfs で行います。引数 path が経路を表します。最初に、path の末尾から現在地点 n を取り出します。そして、n がゴール goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールに到達したら Println で経路を表示します。ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。
ゴールに到達していない場合、adjacent から頂点 n の隣接リストを取り出します。そして、for ループでスライスの要素を順番に取り出して、dfs を再帰呼び出しします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。このチェックを関数 member で行います。経路 path の中に頂点 x がないことを確認してから、append で path に x を追加して dfs を再帰呼び出しします。
実行結果は次のようになります。
リスト : 深さ優先探索 (keiro.go)
func main() {
depthFirstSearch(A, G)
}
$ go run keiro.go [0 1 2 4 6] [0 1 3 4 6] [0 2 1 3 4 6] [0 2 4 6]
4 通りの経路を見つけることができました。バックトラックによる探索は、経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索」です。
●幅優先探索
バックトラックによる探索は「深さ優先探索」や「縦形探索」とも呼ばれるように、一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。
幅優先探索の様子を下図に示します。
図 : 幅優先探索
まず、出発点 A から一つ進んだ経路 (2 節点) を全て求めます。この場合は、[A B] と [A C] の 2 つあり、これを全て記憶しておきます。次に、これらの経路から一つ進めた経路 (3 節点) を全て求めます。経路 [A B] は [A B C] と [A B D] へ進めることができますね。ほかの経路 [A C] も同様に進めて、全ての経路を記憶します。あとはこの作業をゴールに到達するまで繰り返せばいいのです。
上図では、4 節点の経路 [A C E G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、全ての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことからバックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せば全ての経路を求めることができます。
完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。
今回の経路図の場合、メモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。
●経路の管理
経路の管理はキューを使うと簡単です。幅優先探索でのキューの動作を下図に示します。
図 : 幅優先探索とキューの動作
最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A B] [A C] を作り、それをキューに追加します。(3) では、経路 [A B] を取り出して、一つ進めた経路 [A B C] と [A B D] をキューに追加します。あとはキューに経路がある間、探索処理を繰り返します。
キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。
●幅優先探索のプログラム
プログラムは次のようになります。
リスト : 幅優先探索
// 新しい経路を作る
func makePath(path []int, x int) []int {
k := len(path)
newPath := make([]int, k + 1)
copy(newPath, path)
newPath[k] = x
return newPath
}
// 幅優先探索
func breadthFirstSearch(start, goal int) {
que := make([][]int, 0)
front := 0
que = append(que, []int{start})
for ; front < len(que); front++ {
path := que[front]
n := path[len(path) - 1]
if n == goal {
fmt.Println(path)
} else {
for _, x := range adjacent[n] {
if !member(x, path) {
que = append(que, makePath(path, x))
}
}
}
}
}
キューはスライスを使って実装します。先頭データの位置を front とします。キューからデータを取り出すときは front の位置のデータを取り出して front の値を +1 します。キューにデータを追加するときはスライスの末尾に追加します。これでキューの動作を実現することができます。
一般に、配列を使ってキューを実装する場合、配列をリングバッファとして使うのが一般的です。詳細は拙作のページ 構造体 (2) Appendix : 配列によるキューの実装 をお読みください。
最初に make でキューの本体 (スライス) を生成し、変数 que にセットします。次に、変数 front を 0 に初期化して、que の末尾にスタート地点の経路 [ ]int{start} を追加します。あとは、キューに経路がある間、for ループで探索を行います。キューから経路を取り出して path にセットします。そして、path の末尾から現在位置を求め、それを変数 n にセットします。
n が goal と等しければ Println で経路を表示します。そうでなければ、経路を一つ進めます。この処理は深さ優先探索とほぼ同じですが、新しい経路を関数 makePath で生成し、それをキューに追加していくところが異なります。makePath は新しいスライスを生成することに注意してください。これで全ての経路を求めることができます。
それでは、実際に実行してみましょう。
リスト : 幅優先探索 (keiro.go)
func main() {
// depthFirstSearch(A, G)
breadthFirstSearch(A, G)
}
$ go run keiro.go [0 2 4 6] [0 1 2 4 6] [0 1 3 4 6] [0 2 1 3 4 6]
結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。
●反復深化
幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。
それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。
たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。
反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。
●反復深化のプログラム
それでは、同じ経路図を使って反復深化を具体的に説明しましょう。反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を１手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。
リスト : 反復深化
func ids(goal, limit int, path []int) {
n := path[len(path) - 1]
if len(path) == limit {
if n == goal {
fmt.Println(path)
}
} else {
for _, x := range adjacent[n] {
if !member(x, path) {
ids(goal, limit, append(path, x))
}
}
}
}
func idSearch(start, goal int) {
path := make([]int, 1, Size)
path[0] = start
for i := 1; i <= Size; i++ {
fmt.Println("----", i, "----")
ids(goal, i, path)
}
}
関数 ids の引数 limit が上限値を表します。経路の長さが上限値 limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。あとは、limit の値を増やしながら ids を呼び出せばいいわけです。それでは実行結果を示しましょう。
リスト : 反復深化 (keiro.go)
func main() {
// depthFirstSearch(A, G)
// breadthFirstSearch(A, G)
idSearch(A, G)
}
$ go run keiro.go ---- 1 ---- ---- 2 ---- ---- 3 ---- ---- 4 ---- [0 2 4 6] ---- 5 ---- [0 1 2 4 6] [0 1 3 4 6] ---- 6 ---- [0 2 1 3 4 6] ---- 7 ----
結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。
●プログラムリスト
//
// keiro.go : 経路の探索
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import "fmt"
/*
Ｂ───Ｄ───Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ───Ｅ───Ｇ
図 : 経路図
*/
const (
A = iota
B
C
D
E
F
G
Size // 頂点の個数
)
// 隣接リスト
var adjacent = [][]int{
{B, C}, // A
{A, C, D}, // B
{A, B, E}, // C
{B, E, F}, // D
{C, D, G}, // E
{D}, // F
{E}, // G
}
// n は xs の要素か？
func member(n int, xs []int) bool {
for _, x := range xs {
if n == x { return true }
}
return false
}
//
// 深さ優先探索
//
func dfs(goal int, path []int) {
n := path[len(path) - 1]
if n == goal {
fmt.Println(path)
} else {
for _, x := range adjacent[n] {
if !member(x, path) {
dfs(goal, append(path, x))
}
}
}
}
func depthFirstSearch(start, goal int) {
path := make([]int, 0, Size )
dfs(goal, append(path, start))
}
//
// 幅優先探索
//
// 新しい経路を作る
func makePath(path []int, x int) []int {
k := len(path)
newPath := make([]int, k + 1)
copy(newPath, path)
newPath[k] = x
return newPath
}
func breadthFirstSearch(start, goal int) {
que := make([][]int, 0)
front := 0
que = append(que, []int{start})
for ; front < len(que); front++ {
path := que[front]
n := path[len(path) - 1]
if n == goal {
fmt.Println(path)
} else {
for _, x := range adjacent[n] {
if !member(x, path) {
que = append(que, makePath(path, x))
}
}
}
}
}
//
// 反復深化
//
func ids(goal, limit int, path []int) {
n := path[len(path) - 1]
if len(path) == limit {
if n == goal {
fmt.Println(path)
}
} else {
for _, x := range adjacent[n] {
if !member(x, path) {
ids(goal, limit, append(path, x))
}
}
}
}
func idSearch(start, goal int) {
path := make([]int, 1, Size)
path[0] = start
for i := 1; i <= Size; i++ {
fmt.Println("----", i, "----")
ids(goal, i, path)
}
}
// 実行
func main() {
fmt.Println("----- dfs -----")
depthFirstSearch(A, G)
fmt.Println("----- bfs -----")
breadthFirstSearch(A, G)
fmt.Println("----- ids -----")
idSearch(A, G)
}
改訂 2021 年 12 月 11 日