乗換案内のようなアプリ開発において、特定の経路でスタックなどが発生してしまう。

Question

実現したいこと

• 乗換回数が最も少ない経路の表示（通る駅の数は問わない）
• スタックの解消

前提

現在、都市開発ゲームの駅名に対応して、経路検索が出来るアプリの公開を目指して開発を進めている者です。
ソースコードはコピペしていただければそのまま動作します。
ヒントだけでも構いませんので、よろしければご回答よろしくお願いいたします。

以下、今回使用している路線図です。
赤……路線リストのline1
青……路線リストのline2
緑……路線リストのline3
に対応しています。
また、書かれた数字はコード内の駅番号リストと対応しています。

発生している問題・エラーメッセージ

（最初の調査の際の情報です。コメント欄に調査し直した際の情報が書かれています）
・期待した結果
０と５……０，１，１，４，４，５の順で表示される。
１と５……１，４，４，５の順で表示される。
２と５……２，４，４，５の順で表示される。
３と５……３，１，１，４，４，５の順で表示される。
５と０……５，４，４，１，１，０の順で表示される。
５と１……５，４，４，１の順で表示される。
５と２……５，４，４，２の順で表示される。
５と３……５，４，４，１，１，３の順で表示される。

・実際の結果
０と５……System.IndexOutOfRangeException: インデックスが配列の境界外です。と表示される(337行目)
１と５……Process is terminated due to StackOverflowException.と表示される。
２と５……２，４，１と表示後、Process is terminated due to StackOverflowException.と表示される。
３と５……３，１と表示後、Process is terminated due to StackOverflowException.と表示される。
５と０……System.IndexOutOfRangeException: インデックスが配列の境界外です。と表示される(337行目)
５と１……System.IndexOutOfRangeException: インデックスが配列の境界外です。と表示される(337行目)
５と２……System.IndexOutOfRangeException: インデックスが配列の境界外です。と表示される(337行目)
５と３……System.IndexOutOfRangeException: インデックスが配列の境界外です。と表示される(337行目)

該当のソースコード

長文なので、リンクを貼らせていただきます。
リンク内容
お手数ですが、ソースコードのダウンロードをお願いします。

試したこと

for文やforeach文内で、路線番号や駅番号が若い順に処理されるようになっているので、if文を用いて適切な値を代入させようとしましたが、うまくいきませんでした。

補足情報（FW/ツールのバージョンなど）

Visual Studio 2022

Comments

[Kamine]

大変申し訳ございません。調査内容を整理してまとめます。

[ikedas]

「遠回り」、「スタック」、「無限ループ」とは、それぞれ
・どのような結果になると期待したのか。
・実際にはどのような結果になったのか。
を、具体的に記してください。

なお、このコメント欄に書くのではなく、質問文を編集して書いてください。

[Kamine]

わかりました。

[Kamine]

申し訳ございません。調査し直した結果、遠回りとwhile文の無限ループは発生していなかったことがわかりました。

[退会済みユーザー]

開始地点が３、終点が２の場合の期待する結果はどうなりますか。

３，１，１，４，４，２　なのか、３，１，１，２のどちらでしょうか？

編集前にあった「ただし距離の概念が実装されていないので移動する駅の数もしくは乗換回数がもっとも少なくなるようにしたい」という文章が、意図的にかどうかわかりませんが、削除されています。

前者は経由する駅の数が多いですが、乗り換え数は0回。
後者は経由する駅の数が一番少ないですが、乗り換え数は1回。
「移動する駅の数もしくは乗換回数がもっとも少なくなるようにしたい」という削除前の文を素直に受け取れば、乗り換え数が0回の前者が期待する結果とする考え方もありますが、そのような理解でいいですか？

また、仮に、同じ数の”最短”経路が複数見つかった場合は、どのような結果を返せばよいでしょうか？複数の結果を返すべきなのか、どちらか一方の結果を任意に返してよいのでしょうか？

[Kamine]

混乱を招いてしまいましたら申し訳ございません。「ただし距離の～」の部分は自分で削除しました。理由として、実現したいことが多いと回答がつかなくなるのではと思ったためです。
「乗換回数が最も少なくなる」ことを優先したいです。修正し追記しておきます。
よって開始３、終点２の場合は、３，１，１，４，４，２を期待します。
最短経路が複数の場合は、そのうち１つの結果で構いません。

[ikedas]

「実際の結果」に「と表示される(337行目)」とありますが、この「337行目」とはソースコードのどこのことですか。

[Kamine]

申し訳ございません。
今日改めて確認しようとしましたところ、「ソースファイルがモジュールがビルドされたときのものと異なります。デバッガでこのファイルを使用しますか？」と表示されました。
そのため、一度クリーンをした所、表示されなくなりました。
その後念のため動作を確認し直しました所、以下のようになりましたので、こちらに訂正情報を書きます。

[Kamine]

０と５……０，１と表示後、Process is terminated due to StackOverflowException.と表示される。
１と５……１，２と表示後。Process is terminated due to StackOverflowException.と表示される。
２と５……２，４，１、１，２と表示後、Process is terminated due to StackOverflowException.と表示される。
３と５……３，１、１，２と表示後、Process is terminated due to StackOverflowException.と表示される。
３と０……while内無限ループ
４と０……while内無限ループ
５と０……while内無限ループ
５と１……while内無限ループ
５と２……while内無限ループ
５と３……while内無限ループ

残りの組み合わせは問題ありませんでした。
また「System.IndexOutOfRangeException: インデックスが配列の境界外です。」の表示は出ませんでした。

[luuguas]

コードを実行して出発駅０、到着駅５で試したところ、1回目の移動で駅０から駅１に移動する直前の passedDupStNum の中身は{4, 1, 2, 1}となっています。(1番目の4は219行目/2,3番目の1,2は261行目/4番目の1は 140行目のコードで追加)
通過する乗換駅は駅１だけなので、本来の中身は{1}であるべきです。

そのため、2回目の移動で駅１から駅４に移動したいのにも関わらず、DecideLine2 関数内で駅４(さらに駅２)が移動先の候補から外れてしまい、無限ループに陥っているようです。

おそらく他にもエラーの原因はあると思いますが、まずは passedDupStNum の中身が正しくなるようにコードを修正するとよいと思います。

[Kamine]

luuguas様、詳しい情報まで添えて下さりありがとうございます。

Answer 1

Kamine さんのコードで発生している不具合に対する回答ではありませんが、乗り換え回数が最小となるような経路を求める問題に対して私なりに解き方を考えてみました。あくまで解法の1つですのでご了承ください。

路線図(グラフ)を工夫する

今回の問題で厄介なのは、「同じ路線上の駅を移動する」と「違う路線に乗り換える」の2種類の動き方があることです。

そのため、単純に路線図上を移動しようとしても「今どの路線にいるのか」や「同じ路線を移動したのか、それとも違う路線に乗り換えたのか」などの判断が難しいです。

---

そこで、複数の路線を1つの路線図で表すのではなく、路線ごとに別々の路線図で表すことにします。

そして、異なる路線図の同じ駅同士を線で繋げることで、「同じ路線上の駅を移動する」と「違う路線に乗り換える」の両方を「線で繋がっている別の駅に移動する」という1種類の動きで表すことができます。

さらに、この図を使うと「乗り換え回数のカウント」についても上手く考えることができます。

乗り換え回数を「目的の駅に到着するまでにかかるコスト」と言い換えることで、

• 同じ路線上を移動する場合は 0 のコストがかかる(=乗り換え回数は増えない)
• 別の路線に乗り換える場合は 1 のコストがかかる(=乗り換え回数が1増える)

と表現することができ、それぞれの線を通るときに対応するコストがかかると考えることができます。

ちなみに、複数の点(今回は各駅のこと)とそれらを繋ぐ線からなる構造のことを「グラフ」といい、グラフにおける点のことを「頂点」、線のことを「辺」といいます。さらに、それぞれの辺がコスト(重み)を持っているグラフのことを「重み付きグラフ」といいます。(「グラフ理論」で調べるとよいです)

コストを最小化する問題を解く

上の図を使うと、「乗り換え回数を最小化する」という問題は「通過した辺のコストの合計を最小化する」問題に言い換えられます。

例えば「0番目の駅から出発して、4番目の駅に到着するまでに必要な最小の乗り換え回数」を求めるには、上の図において「(0番または6番または12番)の駅から出発して、(4番または10番または16番)の駅に到着するまでに必要な最小のコスト」を求めればよいです。この答えとなる経路の1つは 0番→1番→7番→10番 で、かかるコストは1です。

---

肝心の経路をどうやって求めるかについては、様々なグラフ探索の方法があります。その中でも特に有効そうな方法を2つ紹介します。

1. ダイクストラ法

色んなグラフ探索の手法のなかで「重み付きグラフ上の2つの頂点を繋ぐ経路のうち最小のコストを求める」のに適しているのが「ダイクストラ法」というアルゴリズムです。

ダイクストラ法では「出発地点を固定したとき、すべての頂点について出発地点からの経路のうち最小のコストを求める」ことができます。

また、経路における所要時間(または所要距離)と乗り換え回数の優先度が変わった場合にも、辺の重みを調整することで同様に解くことができます。

• (今回の問題をダイクストラ法で解いてみました。バグがあったらごめんなさい。)
  https://gist.github.com/luuguas/db1d3f675120be2090f1fc91f136b84a

2. 深さ優先探索

今回の問題では考慮すべき条件が乗り換え回数だけなので上記のダイクストラ法で上手くいきますが、条件がさらに増えた場合や複数の経路を求めたい場合などになると、ダイクストラ法では探索に限度があります。

そこで、グラフ探索の基礎である深さ優先探索を使うことをおすすめします。

深さ優先探索は「移動できる頂点がなくなるまで移動することを繰り返し、行き止まりに当たったら1歩戻る」というシンプルな方法ですが、深さ優先探索を理解できれば、条件が複雑になっても柔軟に対応することができます。(特に再帰関数を使った深さ優先探索は様々な探索に応用できます)

まずは出発地点と到着地点を結ぶ全ての経路を調べるところから始めて、そこから乗り換え回数や路線などの情報を追加したり、探索範囲を絞ったりすることを段階的におこなっていくと良いと思います。(探索範囲を絞る方法についてはビームサーチや焼きなましなど色々)

補足

グラフ探索について解説しているサイトをまとめました。かなり分量がありますが、理解に役立つと思います。

深さ優先探索について

• DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 #AtCoder - Qiita
  https://qiita.com/drken/items/4a7869c5e304883f539b
• 深さ優先探索(Depth First Search)の基本 | アルゴリズムロジック
  https://algo-logic.info/dfs/
• よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録
  https://drken1215.hatenablog.com/entry/2020/05/04/190252

幅優先探索について

幅優先探索は深さ優先探索とセットで出てくることが多いです。

• スタックとキューを極める！ 〜 考え方と使い所を特集 〜 #競技プログラミング - Qiita
  https://qiita.com/drken/items/6a95b57d2e374a3d3292
• BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 #AtCoder - Qiita
  https://qiita.com/drken/items/996d80bcae64649a6580

ダイクストラ法について

必ずしもダイクストラ法を使う必要はないので見なくても良いです。

• ダイクストラ法を理解するのに一番わかりやすい方法を紹介 - フラミナル
  https://blog.framinal.life/entry/2020/03/31/085144
• ダイクストラ法とは？｜アルゴリズムを極めよう
  https://products.sint.co.jp/topsic/blog/dijkstras-algorithm

Comments

[Kamine]

詳しいご回答ありがとうございます。ご提示下さったコードは問題なく動作しました。

Answer 2

ではヒントだけ。

まず、「スタックオーバーフロー」がどういうことなのかを、プログラミングの参考書などで調べてみてください。また「インデックスが配列の境界外」の意味も調べてください。

以下気づいた点を述べます。

1. ご質問のコードはResult2()がいろいろな関数を介してMove()を呼び出し、Move()はResult2()を呼び出すという形になっています。「相互再帰」という、再帰呼び出しの一種です。
   再帰呼び出しを使ったコードでよくある失敗が、再帰の終了条件を明確にしていないというものです。そのため再帰呼び出しが終了せず、スタックオーバーフローが発生します。
   このような失敗を避けるためには、再帰呼び出しする関数では最初に「これこれの条件が成立したらそれ以上再帰せず関数を終了する」というコードを必ず記述するとよいです。
   今回の場合だと、質問に明示されていない暗黙の条件として「一度通った駅は二度と通らない」というものがあるはずです。ですから再帰の終了条件として「すでに調べた駅に到達したら、それ以上調べずに関数を終了する」というコードが関連の関数に必要ですが、それが抜けている (書くべき場所に書かれていない) と思われます。

2. 経路の探索と乗り換え回数のカウントの両方を一度にやろうとしているため、ミスが混入しやすいです。今後経由駅数などほかの条件を適用したい場合にコードの変更も難しいです。
   まずは一つの関数で、「出発駅と到着駅が与えられたときに、あり得る経路をすべて列挙する」(乗り換え数などの条件は加味しない) というコードを書いてみてはどうですか。もちろん再帰呼び出しを使ってもかまいません。

3. 一般の場合の経路探索では「組み合わせ爆発」が起きる可能性があります (参考: 「フカシギの数え方」)。都市開発ゲームということなので、プレイヤーがそのようなことをひき起こす路線を敷いてしまうこともありえますね。
   そのため、2. で実装した単純な経路列挙アルゴリズムは改良の余地があります。経路探索の途中で、あきらかに最良ではない経路 (すでにみつかった経路よりも乗り換え数が多くなる、など) がでてきたら探索を打ち切ってほかの候補を探す、などの工夫が必要です。

今はいきなり3. をやろうとしている節もありますが、2.のコードを書いてから3.の改良をやればコードの見通しもよくなり、うまくいくのではないでしょうか。

【追記】ちなみに、手元で書いてみたら少なくとも2.はできました。さらに3.の改良をするのも簡単そうです。

コード

なんかコードを載せた回答が出てしまったのでもういいや。2.のコードで私が書いたものも載せときますね。

package main

import (
	"bufio"
	"fmt"
	"os"
)

var stations = []string{
	"駅0",
	"駅1",
	"駅2",
	"駅3",
	"駅4",
	"駅5",
}

var lines = [][]int{
	{0, 1, 2},
	{3, 1, 4, 2},
	{4, 5},
}

var nextStations = [][]int{}

var results = [][]int{}

func main() {
	// 準備: 隣接駅のリストを作っておく
	for s := 0; s < len(stations); s++ {
		nextStations = append(nextStations, listNextStations(s))
	}

	// 出発駅と到着駅を入力
	scanner := bufio.NewScanner(os.Stdin)

	fmt.Print("出発駅……")
	scanner.Scan()
	start := scanner.Text()
	fmt.Print("到着駅……")
	scanner.Scan()
	goal := scanner.Text()

	s := -1
	g := -1
	for i, v := range stations {
		switch v {
		case start:
			s = i
		case goal:
			g = i
		}
		if 0 <= s && 0 <= g {
			break
		}
	}

	// 結果を得る
	findResults(s, g, []int{})

	fmt.Println(len(results), " routes")
	fmt.Println(results)
}

// 駅 s に隣接するすべての駅を列挙する
func listNextStations(s int) []int {
	var next = []int{}

	for _, line := range lines {
		for i, station := range line {
			if s == station {
				if 0 < i {
					next = append(next, line[i-1])
				}
				if i < len(line)-1 {
					next = append(next, line[i+1])
				}
			}
		}
	}

	return next
}

// 駅 s から最終目的の駅 g までの経路を探索し、
// 見つかったものを配列 results に加える。
// visited はこれまでに通ってきた駅の配列 (s が出発駅なら空)。
func findResults(s, g int, visited []int) {
	// 経路を一駅進める
	visited = append(visited, s)

	// 隣接する駅をすべて調べる
	for _, n := range nextStations[s] {
		// ゴールなら経路を記録して、その先はもう調べない
		if n == g {
			result := make([]int, len(visited)+1)
			copy(result, append(visited, n))
			results = append(results, result)
			continue
		}

		// すでに通った駅ならもう調べない
		var passed bool
		for _, v := range visited {
			if n == v {
				passed = true
				break
			}
		}
		if passed {
			continue
		}

		// 上記のいずれでもなければ、次の駅に進んで探索を続行
		findResults(n, g, visited)
	}
	// すべての隣接駅を調べ終わったら (再帰) 関数の呼び出しから戻る

	// 経路を一駅戻す
	visited = visited[:len(visited)-1]
}

言語はGoです。経路探索の主要部であるfindResults()関数では、luuguasさんも言及されている「深さ優先探索」を、再帰呼び出しを用いて行っています。

実行結果:

$ go run main.go
出発駅……駅0
到着駅……駅5
2  routes
[[0 1 2 4 5] [0 1 4 5]]
$ go run main.go
出発駅……駅1
到着駅……駅5
2  routes
[[1 2 4 5] [1 4 5]]
$ go run main.go
出発駅……駅2
到着駅……駅5
2  routes
[[2 1 4 5] [2 4 5]]
$ go run main.go
出発駅……駅3
到着駅……駅5
2  routes
[[3 1 2 4 5] [3 1 4 5]]
$ go run main.go
出発駅……駅3
到着駅……駅0
1  routes
[[3 1 0]]
$ go run main.go
出発駅……駅4
到着駅……駅0
2  routes
[[4 1 0] [4 2 1 0]]
# 以後は上記の逆順の結果になるだけなので省略。

Comments

[Kamine]

ご回答のほど、ありがとうございます。書かれたことを参考にプログラムを組み直してみることにします。

[Kamine]

すみません。回答の２．のコードで出た通りは何通りでしたか。また、２．の処理部分は何行のコードを書いたか教えていただければ幸いです。

[ikedas]

「何通り」とはどういうことを言っていますか。またコードの行数をお知りになりたい理由は何でしょうか。

[Kamine]

すみません、「出発駅と到着駅が与えられたときに、あり得る経路をすべて列挙する」を「あり得る経路をすべて列挙する」の部分だけで解釈してしまっていました。あり得る経路をすべて列挙したら何通りか聞きたかったのですが、そもそも解釈違いでしたので無視して構いません。
コードの行数につきましては、どのくらいのコードを書けば期待する動作が実現できるか、単純に気になったためです。

今後は文章をよく理解してから返信します。すみません。

[ikedas]

回答中のリンク先の動画はご覧になりましたか。あれで駅数が25になる路線図にあたるもの (動画中で「4 × 4」といっているもの) で試したところ、正しく8512通りとなりました。

2.のコードの行数は、駅名や路線データなどの値をセットしている分などもふくめて全体で100行くらい、そのうち実際に探索をする関数は30行たらずです (いずれもコメント行や空行は除く)。言語はC#ではないですが、C#で書いたとしてもそう大きくは変わらないでしょう。

[ikedas]

コードを載せました。

[Kamine]

ご回答とコードありがとうございます。リンク先の動画は見ました。