Javaでアルゴリズムの単純な実装を作成してみました。私の結論は、あなたが説明したアルゴリズムは、複数のパスを見つける場合でも機能するということでした。あるいは、あなたは私よりも賢いテスト ケースを思いついたのかもしれません。（迷路を投稿して、アルゴリズムを試すことができます）
行き止まりカウンターの私の実装は、おそらく最も効率的なものではありませんが、仕事は完了します。アクセスされた現在の OPEN ノードごとに、周囲の 4 つのノードがチェックされます。
- 少なくとも 1 つのネイバーが開いている場合、現在のノードは行き止まりではありません
- 複数のネイバーが VISITED である場合、現在のノードは行き止まりではありません
- 1 つのノードのみが VISITED (前のステップで取得したノード) であり、他のネイバーが開いていない場合、現在のノードは行き止まりです。
これは私が書いた Java コードです (かなり長いことに注意してください)。必要に応じて、パスをスタックに格納し、ノードが VISITED に設定されるたびにノードをプッシュし、OPEN に設定されるたびにノードをポップすることもできます。GOAL に到達するたびに、現在のパスを保持しているスタックをコピーして保存する必要があります。
「dead-end-investigation-step」というコメントでマークされた if ブロックを削除すると、この実装は質問で説明されている実装とほぼ同じになります。
package test;
import java.util.HashSet;
import java.util.Set;
public class MazeSolver {
final static int OPEN = 0;
final static int WALL = 1;
final static int GOAL = 2;
final static int VISITED = 3;
static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } };
// This is what the field looks like:
//
// 0 1 1 0 1
// 0 0 0 0 0
// 0 1 1 0 1
// 0 1 0 0 0
// 0 0 0 1 0
// 1 1 0 2 0
static int width = field.length;
static int height = field[0].length;
static int xStart = 0;
static int yStart = 0; // Initiated to start position: (x = 0, y = 0)
static int nrSolutions = 0; // Records number of solutions
// Used for storing id:s of dead end nodes.
// The integer id is (x + y * width)
static Set<Integer> deadEnds = new HashSet<Integer>();
public static void main(String[] arg) {
System.out.println("Initial maze:");
printField();
findPath(xStart, yStart);
System.out.println("Number of solutions: " + nrSolutions);
System.out.println("Number of dead ends: " + deadEnds.size());
}
private static void findPath(int x, int y) {
if (x < 0 || y < 0 || x >= width || y >= height) { // Step 1
return;
} else if (field[x][y] == GOAL) { // Step 2
nrSolutions++;
System.out.println("Solution nr " + nrSolutions + ":");
printField();
return;
} else if (field[x][y] != OPEN) { // Step 3
return;
} else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step
int uniqueNodeId = x + y * width;
deadEnds.add(uniqueNodeId); // Report as dead end
return;
}
field[x][y] = VISITED; // Step 4
findPath(x, y - 1); // Step 5, go north
findPath(x + 1, y); // Step 6, go east
findPath(x, y + 1); // Step 7, go south
findPath(x - 1, y); // Step 8, go west
field[x][y] = OPEN; // Step 9
// Step 10 is not really needed, since the boolean is intended to
// display only whether or not a solution was found. This implementation
// uses an int to record the number of solutions instead.
// The boolean return value would be (nrSolutions != 0)
}
private static boolean isDeadEnd(int x, int y) {
int nrVisitedNeighbours = 0;
if (y > 0) { // If northern neighbour exists
if (field[x][y - 1] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x][y - 1] != WALL) {
return false;
}
}
if (x < width - 1) { // If eastern neighbour exists
if (field[x + 1][y] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x + 1][y] != WALL) {
return false;
}
}
if (y < height - 1) { // If southern neighbour exists
if (field[x][y + 1] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x][y + 1] != WALL) {
return false;
}
}
if (x > 0) { // If western neighbour exists
if (field[x - 1][y] == VISITED) {
nrVisitedNeighbours++;
} else if (field[x - 1][y] != WALL) {
return false;
}
}
if (nrVisitedNeighbours > 1) { // Circular path scenario
return false;
}
return true; // The exhaustive result of this check: this is a dead
// end
}
private static void printField() {
for (int yy = 0; yy < field[0].length; yy++) {
for (int xx = 0; xx < field.length; xx++) {
System.out.print(field[xx][yy] + " ");
}
System.out.println();
}
System.out.println();
}
}
上記のアルゴリズムは、コードにハードコードされている迷路の例に 4 つの異なるソリューション パスと 2 つの行き止まりを報告します。
<EDIT>
ソリューション パスが少なすぎる理由は、ソリューション パスとは何かを誤解しているからでしょうか? たとえば、次の迷路を考えてみましょう。
######
## #
## # #
#S #
##E###
######
この迷路には、有効なソリューション パスが 1 つしかありません。これは、各ノードに 1 回しかアクセスできないためです。円形パスを周回すると、S の東と E の北のノードに 2 回アクセスすることになるため、有効なソリューション パスではありません。ソリューション パスのこの定義は、使用するアルゴリズムによって暗示されます。
同じノードに複数回アクセスできるようにすると、円 1、2、3 ... を無限に何度も回ることができるため、無限に多くのソリューションが存在することになります。
</編集>
<EDIT2>
おっしゃる通り、ノードを VISITED に設定するたびに pathLength を増やし、VISITED ノードを OPEN に戻すたびにパスの長さを減らします。
最短パスの長さを記録するために、Integer.MAX_VALUE に対して開始する shortestPath int 値もあります。次に、目標に到達するたびに、次のことを行います。
if(pathLength < shortestPath){
shortestPath = pathLength;
}
行き止まりについては… 手で数えてみたら、9が正しいと思いました。これはSareenによって投稿された迷路ですが、行き止まりには (手で) D のマークが付けられています。
####################
#S # D# D#D D#
# # ## ## ### ###
# # # # #
## # # # ## #
# ### ##### #
# # #D #D # ###
# ### ### ## # #####
# D#D #D E#
####################
もっと見つけられますか？それとも行き止まりの意味を誤解したのですか？行き止まりとは、一方向からしかたどり着けない結節のことだと思っていました。
例 1:
######
## ###
## ###
## ###
#S E#
######
上の迷路には行き止まりが 1 つあります。
例 2:
######
## ##
## ##
## ##
#S E#
######
上記の迷路には行き止まりがありません。最も北にあるアクセス可能なノードの 1 つにいる場合でも、隣接する非 WALL マスが 2 つあります。
デッドエンドの別の定義はありますか?
</EDIT2>