回答編集履歴
8
処理済みをスキップしたら動作したので、そちらに合わせて回答を修正
test
CHANGED
|
@@ -20,14 +20,55 @@
|
|
|
20
20
|
`current.moves`は、**初期状態の空白の位置**から、目的の状態にするための移動経路になります。
|
|
21
21
|
つまり、`current.spaceIndex`ではなく、`initialState.spaceIndex`から開始しないといけません。
|
|
22
22
|
|
|
23
|
-
あと、現在のコードだと、
|
|
23
|
+
あと、現在のコードだと、すでに処理済みのパターンが何度も処理されるので非効率です。
|
|
24
|
-
|
|
24
|
+
`unordered_set`で処理済みのものを覚えておいて、再度出現したら飛ばすようにしましょう。
|
|
25
25
|
```c++
|
|
26
|
+
#include <cstdint>
|
|
27
|
+
#include <unordered_set>
|
|
28
|
+
|
|
29
|
+
auto hash(const State& state) {
|
|
30
|
+
std::uint64_t ret = 0;
|
|
31
|
+
for (int i = 0; i < 16; ++i)
|
|
32
|
+
ret |= std::uint64_t(state.panel[i]) << (i * 4);
|
|
33
|
+
return ret;
|
|
34
|
+
}
|
|
35
|
+
|
|
36
|
+
void solvePuzzle() {
|
|
37
|
+
State initialState;
|
|
38
|
+
for (int i = 0; i < 16; i++) {
|
|
39
|
+
initialState.panel[i] = panel[i];
|
|
40
|
+
if (panel[i] == 15) {
|
|
41
|
+
initialState.spaceIndex = i;
|
|
42
|
+
}
|
|
43
|
+
}
|
|
44
|
+
initialState.cost = calculateCost(initialState);
|
|
45
|
+
|
|
46
|
+
std::priority_queue<State> openList;
|
|
47
|
+
std::unordered_set<std::uint64_t> used;
|
|
48
|
+
openList.push(initialState);
|
|
49
|
+
used.insert(hash(initialState));
|
|
50
|
+
|
|
51
|
+
std::vector<int> dx = { -1, 1, 0, 0 };
|
|
52
|
+
std::vector<int> dy = { 0, 0, -1, 1 };
|
|
53
|
+
|
|
54
|
+
while (!openList.empty()) {
|
|
55
|
+
State current = openList.top();
|
|
56
|
+
openList.pop();
|
|
57
|
+
|
|
58
|
+
if (current.cost == 0) {
|
|
59
|
+
for (int move : current.moves) {
|
|
60
|
+
int x = initialState.spaceIndex % 4;
|
|
61
|
+
int y = initialState.spaceIndex / 4;
|
|
62
|
+
int newX = x + dx[move];
|
|
63
|
+
int newY = y + dy[move];
|
|
64
|
+
change(newX, newY);
|
|
65
|
+
initialState.spaceIndex = newY * 4 + newX;
|
|
66
|
+
Sleep(500); // 一つずつ動かすための待機時間
|
|
67
|
+
}
|
|
68
|
+
break;
|
|
69
|
+
}
|
|
70
|
+
|
|
26
71
|
for (int move = 0; move < 4; move++) {
|
|
27
|
-
// 追加ここから
|
|
28
|
-
if (!current.moves.empty() && move == (current.moves.back() ^ 1))
|
|
29
|
-
continue;
|
|
30
|
-
// 追加ここまで
|
|
31
72
|
int x = current.spaceIndex % 4;
|
|
32
73
|
int y = current.spaceIndex / 4;
|
|
33
74
|
int newX = x + dx[move];
|
|
@@ -40,18 +81,26 @@
|
|
|
40
81
|
next.panel[next.spaceIndex] = 15;
|
|
41
82
|
next.cost = calculateCost(next);
|
|
42
83
|
next.moves.push_back(move);
|
|
84
|
+
auto h = hash(next);
|
|
85
|
+
if (used.count(h) <= 0) {
|
|
43
|
-
openList.push(next);
|
|
86
|
+
openList.push(next);
|
|
87
|
+
used.insert(h);
|
|
88
|
+
}
|
|
44
89
|
}
|
|
45
90
|
}
|
|
91
|
+
}
|
|
92
|
+
}
|
|
46
93
|
```
|
|
47
94
|
|
|
48
|
-
|
|
95
|
+
一応、これらの修正で動作はするようになりますが、最短手より大幅に手数が増えてしまいます。
|
|
49
|
-
こちらで紹介されている28手の問題を試してみましたが、手
|
|
96
|
+
こちらで紹介されている28手の問題を試してみましたが、このコードだと138手となり、5倍近くの手数が必要となりました。
|
|
50
97
|
|
|
51
98
|
[15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる](https://teratail.com/questions/80295)
|
|
52
99
|
|
|
53
|
-
|
|
100
|
+
それが嫌なら、ネットで別の方法を探してください。
|
|
54
101
|
|
|
55
102
|
一例として、英語版Wikipediaの「A* search algorithm」内にある「[Weighted A*](https://en.wikipedia.org/wiki/A*_search_algorithm#Bounded_relaxation)」を紹介しておきます。
|
|
56
103
|
A*アルゴリズムを実装したうえで、ヒューリスティック関数の返す値を2～3倍にするだけです。
|
|
104
|
+
3倍で試したところ、上記問題も38手まで縮めることができました。
|
|
105
|
+
|
|
57
|
-
|
|
106
|
+
※最初の回答では、修正しても時間がかかりすぎると説明したが、実際には処理済みをスキップすることで動作したため、回答を大幅に修正した。
|
7
文言変更
test
CHANGED
|
@@ -53,5 +53,5 @@
|
|
|
53
53
|
現在のアルゴリズムでは、どうあがいても無理なので、ネットで別の方法を探してください。
|
|
54
54
|
|
|
55
55
|
一例として、英語版Wikipediaの「A* search algorithm」内にある「[Weighted A*](https://en.wikipedia.org/wiki/A*_search_algorithm#Bounded_relaxation)」を紹介しておきます。
|
|
56
|
-
A*アルゴリズムを実装したうえで、ヒューリスティック関数の返す値を
|
|
56
|
+
A*アルゴリズムを実装したうえで、ヒューリスティック関数の返す値を2～3倍にするだけです。
|
|
57
57
|
求まる回答は最短手にはなりませんが、最短手が70を超えるような難しい問題でも現実的な時間で解くことができます。
|
6
ソース追加箇所が分かりづらいので修正
test
CHANGED
|
@@ -24,8 +24,10 @@
|
|
|
24
24
|
空白の最後の移動を見て、逆方向に移動しないようにすることで、このようなケースを避けることができます。
|
|
25
25
|
```c++
|
|
26
26
|
for (int move = 0; move < 4; move++) {
|
|
27
|
+
// 追加ここから
|
|
27
|
-
if (!current.moves.empty() && move == (current.moves.back() ^ 1))
|
|
28
|
+
if (!current.moves.empty() && move == (current.moves.back() ^ 1))
|
|
29
|
+
continue;
|
|
28
|
-
|
|
30
|
+
// 追加ここまで
|
|
29
31
|
int x = current.spaceIndex % 4;
|
|
30
32
|
int y = current.spaceIndex / 4;
|
|
31
33
|
int newX = x + dx[move];
|
5
改善方法を追記
test
CHANGED
|
@@ -20,7 +20,30 @@
|
|
|
20
20
|
`current.moves`は、**初期状態の空白の位置**から、目的の状態にするための移動経路になります。
|
|
21
21
|
つまり、`current.spaceIndex`ではなく、`initialState.spaceIndex`から開始しないといけません。
|
|
22
22
|
|
|
23
|
+
あと、現在のコードだと、空白を左に動かした直後に右に動かして元に戻るケースなども処理してしまうので非効率です。
|
|
24
|
+
空白の最後の移動を見て、逆方向に移動しないようにすることで、このようなケースを避けることができます。
|
|
25
|
+
```c++
|
|
26
|
+
for (int move = 0; move < 4; move++) {
|
|
27
|
+
if (!current.moves.empty() && move == (current.moves.back() ^ 1)) // 追加
|
|
28
|
+
continue; // 追加
|
|
29
|
+
int x = current.spaceIndex % 4;
|
|
30
|
+
int y = current.spaceIndex / 4;
|
|
31
|
+
int newX = x + dx[move];
|
|
32
|
+
int newY = y + dy[move];
|
|
33
|
+
|
|
34
|
+
if (newX >= 0 && newX < 4 && newY >= 0 && newY < 4) {
|
|
35
|
+
State next = current;
|
|
36
|
+
next.spaceIndex = newY * 4 + newX;
|
|
37
|
+
next.panel[current.spaceIndex] = next.panel[next.spaceIndex];
|
|
38
|
+
next.panel[next.spaceIndex] = 15;
|
|
39
|
+
next.cost = calculateCost(next);
|
|
40
|
+
next.moves.push_back(move);
|
|
41
|
+
openList.push(next);
|
|
42
|
+
}
|
|
43
|
+
}
|
|
44
|
+
```
|
|
45
|
+
|
|
23
|
-
ただし、
|
|
46
|
+
ただし、これらを修正しても、数十手の問題になってくると時間がかかりすぎて厳しいです。
|
|
24
47
|
こちらで紹介されている28手の問題を試してみましたが、手元のマシンで1分待っても解けませんでした。
|
|
25
48
|
|
|
26
49
|
[15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる](https://teratail.com/questions/80295)
|
|
@@ -28,5 +51,5 @@
|
|
|
28
51
|
現在のアルゴリズムでは、どうあがいても無理なので、ネットで別の方法を探してください。
|
|
29
52
|
|
|
30
53
|
一例として、英語版Wikipediaの「A* search algorithm」内にある「[Weighted A*](https://en.wikipedia.org/wiki/A*_search_algorithm#Bounded_relaxation)」を紹介しておきます。
|
|
31
|
-
A*アルゴリズムを実装したうえで、ヒューリスティック関数の値を固定で数倍にするだけです。
|
|
54
|
+
A*アルゴリズムを実装したうえで、ヒューリスティック関数の返す値を固定で数倍にするだけです。
|
|
32
55
|
求まる回答は最短手にはなりませんが、最短手が70を超えるような難しい問題でも現実的な時間で解くことができます。
|
4
解法の例を追記
test
CHANGED
|
@@ -26,3 +26,7 @@
|
|
|
26
26
|
[15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる](https://teratail.com/questions/80295)
|
|
27
27
|
|
|
28
28
|
現在のアルゴリズムでは、どうあがいても無理なので、ネットで別の方法を探してください。
|
|
29
|
+
|
|
30
|
+
一例として、英語版Wikipediaの「A* search algorithm」内にある「[Weighted A*](https://en.wikipedia.org/wiki/A*_search_algorithm#Bounded_relaxation)」を紹介しておきます。
|
|
31
|
+
A*アルゴリズムを実装したうえで、ヒューリスティック関数の値を固定で数倍にするだけです。
|
|
32
|
+
求まる回答は最短手にはなりませんが、最短手が70を超えるような難しい問題でも現実的な時間で解くことができます。
|
3
別の方法を探すように促す
test
CHANGED
|
@@ -24,3 +24,5 @@
|
|
|
24
24
|
こちらで紹介されている28手の問題を試してみましたが、手元のマシンで1分待っても解けませんでした。
|
|
25
25
|
|
|
26
26
|
[15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる](https://teratail.com/questions/80295)
|
|
27
|
+
|
|
28
|
+
現在のアルゴリズムでは、どうあがいても無理なので、ネットで別の方法を探してください。
|
2
ソルバーしか見ていないとの注記を追加
test
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
|
+
※DXライブラリ使用ソースをビルドできる環境が手元にないので、以下の回答ではソルバー部分しかチェックしていません。
|
|
2
|
+
|
|
1
3
|
問題は以下のソースにあります。
|
|
2
4
|
|
|
3
5
|
```c++
|
1
文言修正
test
CHANGED
|
@@ -18,7 +18,7 @@
|
|
|
18
18
|
`current.moves`は、**初期状態の空白の位置**から、目的の状態にするための移動経路になります。
|
|
19
19
|
つまり、`current.spaceIndex`ではなく、`initialState.spaceIndex`から開始しないといけません。
|
|
20
20
|
|
|
21
|
-
ただし、そ
|
|
21
|
+
ただし、そこを修正しても、数十手の問題になってくると時間がかかりすぎて厳しいです。
|
|
22
22
|
こちらで紹介されている28手の問題を試してみましたが、手元のマシンで1分待っても解けませんでした。
|
|
23
23
|
|
|
24
24
|
[15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる](https://teratail.com/questions/80295)
|