M.Hiroi's Home Page

お気楽 Scala プログラミング入門

経路の探索


Copyright (C) 2014-2021 Makoto Hiroi
All rights reserved.

はじめに

今回は、地図上の A 地点から B 地点までの道順を求める、といった「経路の探索」と呼ばれる問題を取り上げます。「探索」にはいろいろな種類があります。パズルの解法も、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法が「バックトラック」なのです。もちろん、経路の探索もバックトラックで解くことができます。

このほかに、もう一つ基本的な方法として「幅優先探索」があります。バックトラックの場合、失敗したら後戻りして別の道を選び直しますが、幅優先探索の場合は、全ての経路について並行に探索を進めていきます。幅優先探索は最短手順を求めるのに適したアルゴリズムですが、問題によっては必要となるメモリの量がとても多くなり、幅優先探索を使用することができないことがあります。このような場合、「反復深化」という方法を使うと、多少時間はかかりますが、少ないメモリで最短手順を求めることができます。今回はこの 3 つの方法で経路を求めてみましょう。

●グラフ

まず最初に「グラフ (graph)」というデータ構造を説明します。一般にグラフというと、 円グラフや折れ線グラフといった図表を思い出す人が多いと思います。数学の「グラフ理論」では、いくつかの点とそれを結ぶ線でできた図形を「グラフ」といいます。次の図を見てください。

頂点       辺
 ↓        ↓
 ●─────────●
 │                  │
 │                  │
 │                  │
 ●─────────●

    図 : グラフの例

上図に示すように、グラフは点とそれを接続する線から構成されています。点のことを「頂点 (vertex)」や「節点 (node)」と呼び、線のことを「辺 (edge)」や「弧 (arc)」と呼びます。グラフには 2 種類あって、辺に向きの無いグラフを「無向グラフ」といい、辺に向きがあるグラフを「有向グラフ」といいます。有向グラフは一方通行の道と考えればいいでしょう。 次の図を見てください。

(1) A──────────→B  有向グラフ 

(2) A←─────────→B  無向グラフ

        図 : 有向グラフと無向グラフ

たとえば、図 (1) では A 地点から B 地点へ行くことができますが、一方通行のため B 地点から A 地点に戻ることはできません。これが有効グラフです。(2) の無効グラフでは、A 地点から B 地点へ行くことができるし、逆に B 地点から A 地点に戻ることもできます。

データ間のさまざまな関係を表す場合、グラフはとても役に立ちます。たとえば、下図のように経路をグラフで表すことができます。

    B───D───F 
  /│      │
A  │      │
  \│      │
    C───E───G

    図 : 経路図

上図ではアルファベットで頂点を表しています。この例では経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。

●隣接行列と隣接リスト

グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 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 がセットされます。これを Scala でプログラムすると、次のようになります。

リスト : 隣接行列

val adjacent: Array[Array[Int]] = Array(
    Array(0, 1, 1, 0, 0, 0, 0),  // A
    Array(1, 0, 1, 1, 0, 0, 0),  // B
    Array(1, 1, 0, 0, 1, 0, 0),  // C
    Array(0, 1, 0, 0, 1, 1, 0),  // D
    Array(0, 0, 1, 1, 0, 0, 1),  // E
    Array(0, 0, 0, 1, 0, 0, 0),  // F
    Array(0, 0, 0, 0, 1, 0, 0))  // G
}

頂点 A から G を数値 0 から 6 に対応させるところがポイントです。隣接行列は 2 次元配列 (Scala では配列の配列) で表します。

隣接行列の欠点は、辺の数が少ない場合でも 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)

  図 : 隣接リスト

これを Scala でプログラムすると次のようになります。

リスト : 隣接リスト

val adjacent: Array[List[Int]] = Array(
  List(1, 2),
  List(0, 2, 3),
  List(0, 1, 4),
  List(1, 4, 5),
  List(2, 3, 6),
  List(3),
  List(4))

隣接行列と同様に、頂点 A から G を数値 0 から 6 に対応させています。今回は配列の中にリストを格納しましたが、リストの中にリストを格納する、具体的には adjacent の型を List[List[Int]] にしてもかまいません。

ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。

●バックトラックによる探索

まずは最初に、バックトラックで A から G までの経路を求めます。バックトラックを再帰呼び出しで実現する場合、次の頂点へ進むことを再帰呼び出しに対応させるのがポイントです。たとえば、経路を探索する関数を search としましょう。search は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。そして、A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。

それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、一つ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。

具体的に説明しましょう。経路はリストに頂点を格納して表すことにします。次の図を見てください。

  A - B - D      ==>  [0, 1. 3]    ==> [3, 1, 0]

  A - B - C - E  ==>  [0, 1, 2, 4] ==> [4, 2, 1, 0]  

                               逆順で管理する

                図 : 経路の表し方

リストの最後尾にデータを追加するのは面倒なので、経路は上図のように逆順で管理することにします。

プログラムは次のようになります。

リスト : 深さ優先探索

def depthFirstSearch(start: Int, goal: Int): Unit = {
  def dfs(path: List[Int]) {
    val p = path.head
    if (p == goal) println(path.reverse)
    else for (x <- adjacent(p) if (!path.contains(x))) dfs(x::path)
  }
  //
  dfs(List(start))
}

関数 depthFirstSearch は start から goal までの経路を求めます。実際の処理は局所関数 dfs で行います。引数 path が経路を表します。最初に、path の先頭から現在地点 p を取り出します。そして、p がゴール goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールに到達したら println で経路 path.reverse を表示します。ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。

ゴールに到達していない場合、隣接リスト adjacent から頂点 p に接続している頂点のリストを取り出します。そして、for ループでリストの要素を順番に取り出して、dfs を再帰呼び出しします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。経路 path の中に頂点 x がないことを確認してから、コンス演算子で path に x を追加して dfs を再帰呼び出しします。

実行結果は次のようになります。

scala> :load keiro.scala
val args: Array[String] = Array()
Loading keiro.scala...
import dlist._
class imStack
class imQueue
object keiro

scala> import keiro._
import keiro._

scala> depthFirstSearch(0, 6)
List(0, 1, 2, 4, 6)
List(0, 1, 3, 4, 6)
List(0, 2, 1, 3, 4, 6)
List(0, 2, 4, 6)

4 通りの経路を見つけることができました。バックトラックによる探索は、経路を先へ先へ進めるので、「縦形探索」とか「深さ優先探索」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索」です。

●スタックによる深さ優先探索の実装

深さ優先探索は、明示的にスタックを使えば繰り返しでプログラムすることができます。スタックを使った経路の探索は下図のような動作になります。

  (1)     ───── STACK  ─────┐
    ┌── [A]                        │
    │    ──────────────┘
    │
    └─→ スタックからデータを取り出す

  (2)     ───── STACK  ─────┐
  ┌──→                            │
  │      ──────────────┘
  │
  ├─── [A,B]  [A] の経路を進め
  └─── [A,C]  スタックに追加する

  (3)     ───── STACK  ─────┐
   ┌── [A,C] [A,B]                 │
   │     ──────────────┘
   │
   └─→ [A,C] の経路を進めスタックに追加
   ┌── [A,C,B] [A,C,E]
   │
   │     ───── STACK  ─────┐
   └─→ [A,B]                       │
          ──────────────┘

  (4)     ───── STACK  ─────┐
    ┌── [A,C,E] [A,C,B] [A,B]      │
    │    ──────────────┘
    │
    └─→ スタックに経路がある間繰り返す 
    ┌── [A,C,E,D] [A,C,E,G]
    │
    │     ───── STACK  ─────┐
    └─→ [A,C,B] [A,B]               │
           ──────────────┘

        図 : 深さ優先探索とスタックの動作

最初、スタックに出発点を格納した経路 [A] を入れます。次に、スタックから経路を一つ取り出します (1)。そして、経路 [A] を一つ進めた経路 [A, B], [A, C] を作成し、それをスタックに追加します (2)。ここでスタックには経路 [A, B], [A, C] が格納されます。同様にスタックからデータを取り出して経路を一つ進めます、取り出した経路が [A, C] とすると、一つ進めた経路は [A, C, B], [A, C, E] で、これをスタックに追加します (3)。あとは同様に、スタックからデータを取り出して経路を一つ進めます (4)。これをゴールに到達するか、スタックが空になるまで繰り返します。

ここで、スタックから取り出した経路を順番に並べてみましょう。

[A] => [A, C] => [A, C, E] => ...

ひとつの経路を延ばして探索をすすめていることがわかります。

バックトラックも簡単です。次の図を見てください。

          ───── STACK  ─────┐
    ┌── [A,C,E,D] [A,C,B] [A,B]    │
    │    ──────────────┘
    │
    └─→ [A,C,E,G] 行き止まり
    │
    │     次のデータを取り出す
    └─→ [A,C,E,D]

    [A] => [A,C] => [A,C,E] => [A,C,E,G] 行き止まり
                            => [A,C,E,D] バックトラック

        図 : バックトラックの動作

行き止まりになったら、その経路を捨ててスタックから新しい経路を取り出します。たとえば、[A, C, E, G] は行き止まりなので、スタックから [A, C, E, D] を取り出します。この動作は [A, C, E, G] から [A, C, E] に戻って [A, C, E, D] に進む動作に対応します。スタックは後入れ先出し (LIFO) のデータ構造です。スタックの中には通ってきた経路が格納されているので、スタックから経路を取り出せばバックトラック (後戻り) することができるわけです。

プログラムは次のようになります。

リスト : スタックを使った深さ優先探索

def depthFirstSearchLoop(start: Int, goal: Int): Unit = {
  val s = new Stack[List[Int]]
  s.push(List(start))
  while (!s.isEmpty()) {
    val path = s.pop()
    val p = path.head
    if (p == goal) println(path.reverse)
    else for (x <- adjacent(p) if (!path.contains(x))) s.push(x::path)
  }
}

スタックは拙作のページ「多相クラス」で作成したクラス Stack[A] を使います。プログラムは改良版である「入れ子クラスとイテレータ」のプログラムリスト3をお使いください。プログラムは package dlist に格納されているので、コンパイルしておけば、import dlist._ で読み込むことができます。

最初に、スタックを生成して変数 s にセットします。そして、start を格納したリストをスタックにプッシュします。あとは、スタックが空になるまで探索を繰り返します。while ループの中で、スタックから経路をポップして変数 path にセットし、先頭の位置を変数 p にセットします。p が goal と等しければ、println で経路を表示します。そうでなければ探索を続けます。このとき、新しい経路をスタックにプッシュします。

それでは実行してみましょう。

scala> depthFirstSearchLoop(0, 6)
List(0, 2, 4, 6)
List(0, 2, 1, 3, 4, 6)
List(0, 1, 3, 4, 6)
List(0, 1, 2, 4, 6)

●immutable なスタックを使う場合

拙作のページ「多相クラス (2)」で作成した immutable なスタックを使っても深さ優先探索を実装することができます。次のリストを見てください。

リスト : immutable なスタック (再掲)

case class imStack[A](top: List[A] = Nil) {
  def push(x: A): imStack[A] = imStack[A](x :: top)
  def pop: (A, imStack[A]) = top match {
    case Nil => throw new Exception("imStack.pop: Stack is Empty")
    case x::xs => (x, imStack[A](xs))
  }
  def isEmpty: Boolean = top == Nil
  def isFull: Boolean = false
  def length: Int = top.length
}
リスト : immutable なスタックを使う場合

  def depthFirstSearchStack(start: Int, goal: Int): Unit = {
    def dfs(s: imStack[List[Int]]): Unit = {
      if (!s.isEmpty) {
        val (path, s1) = s.pop
        val p = path.head
        if (p == goal) {
          println(path.reverse)
          dfs(s1)
        } else {
          dfs(adjacent(p).foldLeft(s1)((a, x) => if (!path.contains(x)) a.push(x::path) else a))
        }
      }
    }
    val s = new imStack[List[Int]]
    dfs(s.push(List(start)))
  }

スタックにデータがある場合、pop でデータを取り出して、path と s1 に経路とスタックをセットします。path の先頭要素が goal と等しい場合、経路をひとつ見つけたので println で表示します。ここで、dfs(s1) を呼び出してバックトラックすることで全ての経路を見つけることができます。goal に到達していない場合は新しい経路を生成して、それをスタックに積んで dfs を再帰呼び出しします。新しい経路をスタックに積む操作は畳み込み foldLeft を使えば簡単です。

ここで、dfs の再帰呼び出しは「末尾再帰」になっていることに注意してください。Scala の末尾再帰は最適化により繰り返しに変換されます。これで、スタックオーバーフローは発生せず、プログラムを高速に実行することができます。

それでは実行してみましょう。

scala> depthFirstSearchStack(0, 6)
List(0, 2, 4, 6)
List(0, 2, 1, 3, 4, 6)
List(0, 1, 3, 4, 6)
List(0, 1, 2, 4, 6)

scala> depthFirstSearchStack(6, 0)
List(6, 4, 3, 1, 2, 0)
List(6, 4, 3, 1, 0)
List(6, 4, 2, 1, 0)
List(6, 4, 2, 0)

●幅優先探索

バックトラックによる探索は「深さ優先探索」や「縦形探索」とも呼ばれるように、一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。

幅優先探索の様子を下図に示します。

    [A] ─┬─ [A, B] ─┬─ [A, B, C]  ・・・・
          │            └─ [A, B, D] ─┬─ [A, B, D, F] 行き止まり  
          │                             └─ [A, B, D, E]
          └─ [A, C] ─┬─ [A, C, B]  ・・・・
                        └─ [A, C, E] ─┬─ [A, C, E, G] GOAL
                                         └─ [A, C, E, D] 

(出発点)    (2節点)  (3節点)      (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)     ───── QUEUE  ──────
  ┌── [A]
  │    ───────────────
  │
  └─→ キューからデータを取り出す

(2)     ───── QUEUE  ──────
                                    ←─┐
        ───────────────  │
                                        │
        [A] の経路を進め   [A, B] ───┤
        キューに追加する   [A, C] ───┘

 (3)     ───── QUEUE  ──────
  ┌── [A, B] [A, C]                ←─┐
  │    ───────────────    │
  │                                      │
  └─→ [A, B] の経路を進めキューに追加  │
         [A, B, C] [A, B, D]  ──────┘

(4)     ───── QUEUE  ──────
  ┌── [A, C] [A, B, C] [A, B, D]   ←─┐
  │    ───────────────    │
  │                                      │
  └─→ キューに経路がある間繰り返す ──┘  

        図 : 幅優先探索とキューの動作

最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A B] [A C] を作り、それをキューに追加します。(3) では、経路 [A B] を取り出して、一つ進めた経路 [A B C] と [A B D] をキューに追加します。あとはキューに経路がある間、探索処理を繰り返します。

キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。

●幅優先探索のプログラム

プログラムは次のようになります。

リスト : 幅優先探索

def breadthFirstSearch(start: Int, goal: Int): Unit = {
  val q = new Queue[List[Int]]
  q.enqueue(List(start))
  while (!q.isEmpty()) {
    val path = q.dequeue()
    val p = path.head
    if (p == goal) println(path.reverse)
    else for (x <- adjacent(p) if (!path.contains(x))) q.enqueue(x::path)
  }
}

キューは拙作のページ「多相クラス」で作成したクラス Queue[A] を使います。プログラムは改良版である「入れ子クラスとイテレータ」のプログラムリスト3をお使いください。最初にキューを生成し変数 q にセットします。次に、経路 List(start) を enqueue でキューに追加します。あとは、キューに経路がある間、while ループで探索を行います。

まず、dequeu でキューから経路を取り出して変数 path にセットします。そして、path の先頭から現在位置を求め、それを変数 p にセットします。p が goal と等しければ println で経路を表示します。

そうでなければ、経路を一つ進めます。この処理は深さ優先探索とほぼ同じですが、新しい経路をキューに追加していくところが異なります。けっきょくのところ、breadthFirstSearch の動作は depthFirstSearchLoop のスタックをキューに取り替えただけです。これで全ての経路を求めることができます。

それでは、実際に実行してみましょう。

scala> breadthFirstSearch(0, 6)
List(0, 2, 4, 6)
List(0, 1, 2, 4, 6)
List(0, 1, 3, 4, 6)
List(0, 2, 1, 3, 4, 6)

結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。

●immutable なキューを使う場合

幅優先探索は immutable なキューを使っても実装することができます。次のリストを見てください。

リスト : immutable なキュー (再掲)

case class imQueue[A](front: List[A] = Nil, rear: List[A] = Nil) {
  def enqueue(x: A): imQueue[A] = imQueue[A](front, x::rear)

  def dequeue: (A, imQueue[A]) = {
    if (isEmpty) throw new Exception("imQueue.dequeue: Queue is Empty")
    front match {
      case Nil => imQueue[A](rear.reverse, Nil).dequeue
      case x::xs => (x, imQueue[A](xs, rear))
    }
  }

  def peek: A = {
    if (isEmpty) throw new Exception("imQueue.peek: Queue is Empty")
    front match {
      case Nil => rear.reverse.head
      case x::_ => x
    }
  }

  def isEmpty: Boolean = front == Nil && rear == Nil
  def length: Int = front.length + rear.length
}
リスト : immutable なキューを使う場合

def breadthFirstSearchQueue(start: Int, goal: Int): Unit = {
  def bfs(q: imQueue[List[Int]]): Unit = {
    if (!q.isEmpty) {
      val (path, q1) = q.dequeue
      val p = path.head
      if (p == goal){
        println(path.reverse)
        bfs(q1)
      } else {
        bfs(adjacent(p).foldLeft(q1)((a, x) => if (!path.contains(x)) a.enqueue(x::path) else a))
      }
    }
  }
  val q = new imQueue[List[Int]]
  bfs(q.enqueue(List(start)))
}

プログラムは関数 depthFirstSearchStack のスタックをキューに変更しただけで、あとの処理はほとんど同じです。局所関数 bfs も末尾再帰になっているので、スタックオーバーフローは発生せずに高速に実行することができます。

それでは実行してみましょう。

scala> breadthFirstSearchQueue(0, 6)
List(0, 2, 4, 6)
List(0, 1, 2, 4, 6)
List(0, 1, 3, 4, 6)
List(0, 2, 1, 3, 4, 6)

scala> breadthFirstSearchQueue(6, 0)
List(6, 4, 2, 0)
List(6, 4, 2, 1, 0)
List(6, 4, 3, 1, 0)
List(6, 4, 3, 1, 2, 0)

●反復深化

幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。

それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。

たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。

反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。

●反復深化のプログラム

それでは、同じ経路図を使って反復深化を具体的に説明しましょう。反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を1手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。

リスト : 反復深化

def idSearch(start: Int, goal: Int): Unit = {
  def dfs(limit: Int, path: List[Int]): Unit = {
    val p = path.head
    if (path.length == limit) {
      if (p == goal) println(path.reverse)
    } else {
      for (x <- adjacent(p)) dfs(limit, x::path)
    }
  }
  for (i <- 1 to 7) {
    println("-----" + i + "-----")
    dfs(i, List(start))
  }
}

局所関数 dfs の引数 limit が上限値を表します。経路の長さが上限値 limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。反復深化の場合、探索の上限値が決められているので、巡回経路が発生してもプログラムは正常に動作します。ただし、最短手数以外の経路は無駄な移動が発生する場合があります。あとは、limit の値を増やしながら dfs を呼び出せばいいわけです。それでは実行結果を示しましょう。

scala> idSearch(0, 6)
-----1-----
-----2-----
-----3-----
-----4-----
List(0, 2, 4, 6)
-----5-----
List(0, 1, 2, 4, 6)
List(0, 1, 3, 4, 6)
-----6-----
List(0, 1, 0, 2, 4, 6)
List(0, 2, 0, 2, 4, 6)
List(0, 2, 1, 2, 4, 6)
List(0, 2, 1, 3, 4, 6)
List(0, 2, 4, 2, 4, 6)
List(0, 2, 4, 3, 4, 6)
List(0, 2, 4, 6, 4, 6)
-----7-----
List(0, 1, 0, 1, 2, 4, 6)
List(0, 1, 0, 1, 3, 4, 6)
List(0, 1, 2, 0, 2, 4, 6)
List(0, 1, 2, 1, 2, 4, 6)
List(0, 1, 2, 1, 3, 4, 6)
List(0, 1, 2, 4, 2, 4, 6)
List(0, 1, 2, 4, 3, 4, 6)
List(0, 1, 2, 4, 6, 4, 6)
List(0, 1, 3, 1, 2, 4, 6)
List(0, 1, 3, 1, 3, 4, 6)
List(0, 1, 3, 4, 2, 4, 6)
List(0, 1, 3, 4, 3, 4, 6)
List(0, 1, 3, 4, 6, 4, 6)
List(0, 1, 3, 5, 3, 4, 6)
List(0, 2, 0, 1, 2, 4, 6)
List(0, 2, 0, 1, 3, 4, 6)
List(0, 2, 1, 0, 2, 4, 6)

結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。なお、巡回経路が発生しないようにすると、反復深化でも 4 通りの経路を得ることができます。興味のある方はプログラムを修正してみてください。


●プログラムリスト

//
// keiro.scala : 経路の探索
//
//               Copyright (C) 2014-2021 Makoto Hiroi
//
import dlist._     // プログラムリスト3 (dlist.scala)

//
// immutable なスタック
//
case class imStack[A](top: List[A] = Nil) {
  def push(x: A): imStack[A] = imStack[A](x :: top)
  def pop: (A, imStack[A]) = top match {
    case Nil => throw new Exception("imStack.pop: Stack is Empty")
    case x::xs => (x, imStack[A](xs))
  }
  def isEmpty: Boolean = top == Nil
  def isFull: Boolean = false
  def length: Int = top.length
}

//
// immutable なキュー
//
case class imQueue[A](front: List[A] = Nil, rear: List[A] = Nil) {
  def enqueue(x: A): imQueue[A] = imQueue[A](front, x::rear)

  def dequeue: (A, imQueue[A]) = {
    if (isEmpty) throw new Exception("imQueue.dequeue: Queue is Empty")
    front match {
      case Nil => imQueue[A](rear.reverse, Nil).dequeue
      case x::xs => (x, imQueue[A](xs, rear))
    }
  }

  def peek: A = {
    if (isEmpty) throw new Exception("imQueue.peek: Queue is Empty")
    front match {
      case Nil => rear.reverse.head
      case x::_ => x
    }
  }

  def isEmpty: Boolean = front == Nil && rear == Nil
  def length: Int = front.length + rear.length
}

//
// 経路の探索
//
object keiro {
  // 隣接リスト
  val adjacent: Array[List[Int]] = Array(
    List(1, 2),
    List(0, 2, 3),
    List(0, 1, 4),
    List(1, 4, 5),
    List(2, 3, 6),
    List(3),
    List(4))

  // 深さ優先探索
  def depthFirstSearch(start: Int, goal: Int): Unit = {
    def dfs(path: List[Int]): Unit = {
      val p = path.head
      if (p == goal) println(path.reverse)
      else for (x <- adjacent(p) if (!path.contains(x))) dfs(x::path)
    }
    //
    dfs(List(start))
  }

  // mutable なスタックを使う
  def depthFirstSearchLoop(start: Int, goal: Int): Unit = {
    val s = new Stack[List[Int]]
    s.push(List(start))
    while (!s.isEmpty()) {
      val path = s.pop()
      val p = path.head
      if (p == goal) println(path.reverse)
      else for (x <- adjacent(p) if (!path.contains(x))) s.push(x::path)
    }
  }

  // immutable なスタックを使う
  def depthFirstSearchStack(start: Int, goal: Int): Unit = {
    def dfs(s: imStack[List[Int]]): Unit = {
      if (!s.isEmpty) {
        val (path, s1) = s.pop
        val p = path.head
        if (p == goal) {
          println(path.reverse)
          dfs(s1)
        } else {
          dfs(adjacent(p).foldLeft(s1)((a, x) => if (!path.contains(x)) a.push(x::path) else a))
        }
      }
    }
    val s = new imStack[List[Int]]
    dfs(s.push(List(start)))
  }

  // 幅優先探索
  def breadthFirstSearch(start: Int, goal: Int): Unit = {
    val q = new Queue[List[Int]]
    q.enqueue(List(start))
    while (!q.isEmpty()) {
      val path = q.dequeue()
      val p = path.head
      if (p == goal) println(path.reverse)
      else for (x <- adjacent(p) if (!path.contains(x))) q.enqueue(x::path)
    }
  }

  // immutable なキューを使う
  def breadthFirstSearchQueue(start: Int, goal: Int): Unit = {
    def bfs(q: imQueue[List[Int]]): Unit = {
      if (!q.isEmpty) {
        val (path, q1) = q.dequeue
        val p = path.head
        if (p == goal){
          println(path.reverse)
          bfs(q1)
        } else {
          bfs(adjacent(p).foldLeft(q1)((a, x) => if (!path.contains(x)) a.enqueue(x::path) else a))
        }
      }
    }
    val q = new imQueue[List[Int]]
    bfs(q.enqueue(List(start)))
  }

  // 反復深化
  def idSearch(start: Int, goal: Int): Unit = {
    def dfs(limit: Int, path: List[Int]): Unit = {
      val p = path.head
      if (path.length == limit) {
        if (p == goal) println(path.reverse)
      } else {
        for (x <- adjacent(p)) dfs(limit, x::path)
      }
    }
    for (i <- 1 to 7) {
      println("-----" + i + "-----")
      dfs(i, List(start))
    }
  }
}

初版 2014 年 9 月 7 日
改訂 2021 年 4 月 4 日