回答編集履歴
4
加筆
answer
CHANGED
|
@@ -19,6 +19,7 @@
|
|
|
19
19
|
|
|
20
20
|
【追記】ちなみに、手元で書いてみたら少なくとも2.はできました。さらに3.の改良をするのも簡単そうです。
|
|
21
21
|
|
|
22
|
+
コード
|
|
22
23
|
---
|
|
23
24
|
なんかコードを載せた回答が出てしまったのでもういいや。2.のコードで私が書いたものも載せときますね。
|
|
24
25
|
```go
|
|
@@ -144,7 +145,9 @@
|
|
|
144
145
|
visited = visited[:len(visited)-1]
|
|
145
146
|
}
|
|
146
147
|
```
|
|
148
|
+
言語はGoです。経路探索の主要部であるfindResults()関数では、luuguasさんも言及されている「深さ優先探索」を、再帰呼び出しを用いて行っています。
|
|
149
|
+
|
|
147
|
-
|
|
150
|
+
実行結果:
|
|
148
151
|
```
|
|
149
152
|
$ go run main.go
|
|
150
153
|
出発駅……駅0
|
3
コードを載せますが、せめてC#に書き直すのだけは自分でやってね。
answer
CHANGED
|
@@ -17,4 +17,164 @@
|
|
|
17
17
|
|
|
18
18
|
今はいきなり3. をやろうとしている節もありますが、2.のコードを書いてから3.の改良をやればコードの見通しもよくなり、うまくいくのではないでしょうか。
|
|
19
19
|
|
|
20
|
-
【追記】ちなみに、手元で書いてみたら少なくとも2.はできました。さらに3.の改良をするのも簡単そうです。
|
|
20
|
+
【追記】ちなみに、手元で書いてみたら少なくとも2.はできました。さらに3.の改良をするのも簡単そうです。
|
|
21
|
+
|
|
22
|
+
---
|
|
23
|
+
なんかコードを載せた回答が出てしまったのでもういいや。2.のコードで私が書いたものも載せときますね。
|
|
24
|
+
```go
|
|
25
|
+
package main
|
|
26
|
+
|
|
27
|
+
import (
|
|
28
|
+
"bufio"
|
|
29
|
+
"fmt"
|
|
30
|
+
"os"
|
|
31
|
+
)
|
|
32
|
+
|
|
33
|
+
var stations = []string{
|
|
34
|
+
"駅0",
|
|
35
|
+
"駅1",
|
|
36
|
+
"駅2",
|
|
37
|
+
"駅3",
|
|
38
|
+
"駅4",
|
|
39
|
+
"駅5",
|
|
40
|
+
}
|
|
41
|
+
|
|
42
|
+
var lines = [][]int{
|
|
43
|
+
{0, 1, 2},
|
|
44
|
+
{3, 1, 4, 2},
|
|
45
|
+
{4, 5},
|
|
46
|
+
}
|
|
47
|
+
|
|
48
|
+
var nextStations = [][]int{}
|
|
49
|
+
|
|
50
|
+
var results = [][]int{}
|
|
51
|
+
|
|
52
|
+
func main() {
|
|
53
|
+
// 準備: 隣接駅のリストを作っておく
|
|
54
|
+
for s := 0; s < len(stations); s++ {
|
|
55
|
+
nextStations = append(nextStations, listNextStations(s))
|
|
56
|
+
}
|
|
57
|
+
|
|
58
|
+
// 出発駅と到着駅を入力
|
|
59
|
+
scanner := bufio.NewScanner(os.Stdin)
|
|
60
|
+
|
|
61
|
+
fmt.Print("出発駅……")
|
|
62
|
+
scanner.Scan()
|
|
63
|
+
start := scanner.Text()
|
|
64
|
+
fmt.Print("到着駅……")
|
|
65
|
+
scanner.Scan()
|
|
66
|
+
goal := scanner.Text()
|
|
67
|
+
|
|
68
|
+
s := -1
|
|
69
|
+
g := -1
|
|
70
|
+
for i, v := range stations {
|
|
71
|
+
switch v {
|
|
72
|
+
case start:
|
|
73
|
+
s = i
|
|
74
|
+
case goal:
|
|
75
|
+
g = i
|
|
76
|
+
}
|
|
77
|
+
if 0 <= s && 0 <= g {
|
|
78
|
+
break
|
|
79
|
+
}
|
|
80
|
+
}
|
|
81
|
+
|
|
82
|
+
// 結果を得る
|
|
83
|
+
findResults(s, g, []int{})
|
|
84
|
+
|
|
85
|
+
fmt.Println(len(results), " routes")
|
|
86
|
+
fmt.Println(results)
|
|
87
|
+
}
|
|
88
|
+
|
|
89
|
+
// 駅 s に隣接するすべての駅を列挙する
|
|
90
|
+
func listNextStations(s int) []int {
|
|
91
|
+
var next = []int{}
|
|
92
|
+
|
|
93
|
+
for _, line := range lines {
|
|
94
|
+
for i, station := range line {
|
|
95
|
+
if s == station {
|
|
96
|
+
if 0 < i {
|
|
97
|
+
next = append(next, line[i-1])
|
|
98
|
+
}
|
|
99
|
+
if i < len(line)-1 {
|
|
100
|
+
next = append(next, line[i+1])
|
|
101
|
+
}
|
|
102
|
+
}
|
|
103
|
+
}
|
|
104
|
+
}
|
|
105
|
+
|
|
106
|
+
return next
|
|
107
|
+
}
|
|
108
|
+
|
|
109
|
+
// 駅 s から最終目的の駅 g までの経路を探索し、
|
|
110
|
+
// 見つかったものを配列 results に加える。
|
|
111
|
+
// visited はこれまでに通ってきた駅の配列 (s が出発駅なら空)。
|
|
112
|
+
func findResults(s, g int, visited []int) {
|
|
113
|
+
// 経路を一駅進める
|
|
114
|
+
visited = append(visited, s)
|
|
115
|
+
|
|
116
|
+
// 隣接する駅をすべて調べる
|
|
117
|
+
for _, n := range nextStations[s] {
|
|
118
|
+
// ゴールなら経路を記録して、その先はもう調べない
|
|
119
|
+
if n == g {
|
|
120
|
+
result := make([]int, len(visited)+1)
|
|
121
|
+
copy(result, append(visited, n))
|
|
122
|
+
results = append(results, result)
|
|
123
|
+
continue
|
|
124
|
+
}
|
|
125
|
+
|
|
126
|
+
// すでに通った駅ならもう調べない
|
|
127
|
+
var passed bool
|
|
128
|
+
for _, v := range visited {
|
|
129
|
+
if n == v {
|
|
130
|
+
passed = true
|
|
131
|
+
break
|
|
132
|
+
}
|
|
133
|
+
}
|
|
134
|
+
if passed {
|
|
135
|
+
continue
|
|
136
|
+
}
|
|
137
|
+
|
|
138
|
+
// 上記のいずれでもなければ、次の駅に進んで探索を続行
|
|
139
|
+
findResults(n, g, visited)
|
|
140
|
+
}
|
|
141
|
+
// すべての隣接駅を調べ終わったら (再帰) 関数の呼び出しから戻る
|
|
142
|
+
|
|
143
|
+
// 経路を一駅戻す
|
|
144
|
+
visited = visited[:len(visited)-1]
|
|
145
|
+
}
|
|
146
|
+
```
|
|
147
|
+
言語はGoです。実行結果:
|
|
148
|
+
```
|
|
149
|
+
$ go run main.go
|
|
150
|
+
出発駅……駅0
|
|
151
|
+
到着駅……駅5
|
|
152
|
+
2 routes
|
|
153
|
+
[[0 1 2 4 5] [0 1 4 5]]
|
|
154
|
+
$ go run main.go
|
|
155
|
+
出発駅……駅1
|
|
156
|
+
到着駅……駅5
|
|
157
|
+
2 routes
|
|
158
|
+
[[1 2 4 5] [1 4 5]]
|
|
159
|
+
$ go run main.go
|
|
160
|
+
出発駅……駅2
|
|
161
|
+
到着駅……駅5
|
|
162
|
+
2 routes
|
|
163
|
+
[[2 1 4 5] [2 4 5]]
|
|
164
|
+
$ go run main.go
|
|
165
|
+
出発駅……駅3
|
|
166
|
+
到着駅……駅5
|
|
167
|
+
2 routes
|
|
168
|
+
[[3 1 2 4 5] [3 1 4 5]]
|
|
169
|
+
$ go run main.go
|
|
170
|
+
出発駅……駅3
|
|
171
|
+
到着駅……駅0
|
|
172
|
+
1 routes
|
|
173
|
+
[[3 1 0]]
|
|
174
|
+
$ go run main.go
|
|
175
|
+
出発駅……駅4
|
|
176
|
+
到着駅……駅0
|
|
177
|
+
2 routes
|
|
178
|
+
[[4 1 0] [4 2 1 0]]
|
|
179
|
+
# 以後は上記の逆順の結果になるだけなので省略。
|
|
180
|
+
```
|
2
できた
answer
CHANGED
|
@@ -16,3 +16,5 @@
|
|
|
16
16
|
そのため、2. で実装した単純な経路列挙アルゴリズムは改良の余地があります。経路探索の途中で、あきらかに最良ではない経路 (すでにみつかった経路よりも乗り換え数が多くなる、など) がでてきたら探索を打ち切ってほかの候補を探す、などの工夫が必要です。
|
|
17
17
|
|
|
18
18
|
今はいきなり3. をやろうとしている節もありますが、2.のコードを書いてから3.の改良をやればコードの見通しもよくなり、うまくいくのではないでしょうか。
|
|
19
|
+
|
|
20
|
+
【追記】ちなみに、手元で書いてみたら少なくとも2.はできました。さらに3.の改良をするのも簡単そうです。
|
1
微加筆
answer
CHANGED
|
@@ -10,7 +10,7 @@
|
|
|
10
10
|
今回の場合だと、質問に明示されていない暗黙の条件として「一度通った駅は二度と通らない」というものがあるはずです。ですから再帰の終了条件として「すでに調べた駅に到達したら、それ以上調べずに関数を終了する」というコードが関連の関数に必要ですが、それが抜けている (書くべき場所に書かれていない) と思われます。
|
|
11
11
|
|
|
12
12
|
2. 経路の探索と乗り換え回数のカウントの両方を一度にやろうとしているため、ミスが混入しやすいです。今後経由駅数などほかの条件を適用したい場合にコードの変更も難しいです。
|
|
13
|
-
まずは一つの関数で、「出発駅と到着駅が与えられたときに、あり得る経路をすべて列挙する」というコードを書いてみてはどうですか。もちろん再帰呼び出しを使ってもかまいません。
|
|
13
|
+
まずは一つの関数で、「出発駅と到着駅が与えられたときに、あり得る経路をすべて列挙する」(乗り換え数などの条件は加味しない) というコードを書いてみてはどうですか。もちろん再帰呼び出しを使ってもかまいません。
|
|
14
14
|
|
|
15
15
|
3. 一般の場合の経路探索では「組み合わせ爆発」が起きる可能性があります (参考: 「[フカシギの数え方](https://youtu.be/Q4gTV4r0zRs)」)。都市開発ゲームということなので、プレイヤーがそのようなことをひき起こす路線を敷いてしまうこともありえますね。
|
|
16
16
|
そのため、2. で実装した単純な経路列挙アルゴリズムは改良の余地があります。経路探索の途中で、あきらかに最良ではない経路 (すでにみつかった経路よりも乗り換え数が多くなる、など) がでてきたら探索を打ち切ってほかの候補を探す、などの工夫が必要です。
|