Я попытался сделать простую реализацию алгоритма в Java. Я пришел к выводу, что алгоритм, который вы описали, работает даже для поиска нескольких путей. Или, возможно, вам удалось придумать более умный тестовый пример, чем я. (Пожалуйста, опубликуйте ваш лабиринт, чтобы я мог попробовать мой алгоритм на нем)
Моя реализация счетчика тупиков, вероятно, не самая эффективная, но она выполняет свою работу. Для каждого текущего ОТКРЫТОГО узла, который посещается, он проверяет 4 окружающих узла:
- Если хотя бы один сосед ОТКРЫТ, текущий узел не является тупиком
- Если более одного соседа - VISITED, текущий узел не является тупиком
- Если ВИДИТСЯ только один узел (тот, с которого мы пришли на предыдущем шаге), а другой сосед не ОТКРЫТ, текущий узел является тупиком
Это код Java, который я написал (будьте осторожны! Довольно долго). Альтернативой может быть, если вы хотите, сохранить путь в стеке, нажимая на узел каждый раз, когда он установлен на VISITED, и возвращая узел на место каждый раз, когда он снова устанавливается на OPEN. Каждый раз, когда достигается ЦЕЛЬ, стек, содержащий текущий путь, должен копироваться и сохраняться.
Если блок if, помеченный комментарием как "тупик-расследование-шаг", будет удален, эта реализация почти точно будет соответствовать описанной в вопросе.
</p>
<pre><code>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();
}
}
Приведенный выше алгоритм сообщает о четырех различных путях решения и двух тупиках в примерном лабиринте, который жестко закодирован в код.
Может быть, причина того, почему вы получаете слишком мало путей решения, может быть неверной интерпретацией того, что такое путь решения? Например, рассмотрим этот лабиринт:
######
## #
## # #
#S #
##E###
######
Этот лабиринт имеет только один допустимый путь решения. Это связано с тем, что вам разрешено посещать каждый узел только один раз, поэтому обход по круговому пути не является допустимым путем решения, поскольку это приведет к посещению узла к востоку от S и к северу от E дважды. Это определение пути решения подразумевается алгоритмом, который вы используете.
Если бы разрешить посещать один и тот же узел несколько раз, было бы бесконечно много решений, так как вы могли бы обходить круг 1, 2, 3 ... бесконечное количество раз.
Точно так же, как вы говорите, я увеличиваю pathLength каждый раз, когда я устанавливаю узел на VISITED, и уменьшаю длину пути каждый раз, когда я устанавливаю узел VISITED обратно на OPEN.
Для записи кратчайшей длины пути у меня также есть int-значение shorttestPath, которое я инициирую в Integer.MAX_VALUE. Затем, каждый раз, когда я достиг цели, я делаю это:
if(pathLength < shortestPath){
shortestPath = pathLength;
}
Что касается тупиков ... Я попытался подсчитать их вручную и подумал, что 9 кажется правильным. Вот лабиринт, размещенный Сарин , но с тупиками, отмеченными (от руки) D:
####################
#S # D# D#D D#
# # ## ## ### ###
# # # # #
## # # # ## #
# ### ##### #
# # #D #D # ###
# ### ### ## # #####
# D#D #D E#
####################
Можете ли вы найти больше?
Или я неправильно истолковал то, что вы имели в виду под тупиком?
Я думал, тупик означает: узел, к которому вы можете прийти только с одного направления.
Пример 1:
######
## ###
## ###
## ###
#S E#
######
У лабиринта выше есть один тупик.
Пример 2:
######
## ##
## ##
## ##
#S E#
######
Указанный лабиринт не имеет тупиков. Даже если вы находитесь в одном из доступных к северу узлов, все равно есть два соседних квадрата, не относящихся к СТЕНЕ.
У вас есть другое определение тупика?
</ EDIT2>