Я попробовал сделать простую реализацию алгоритма на java. Я пришел к выводу, что описанный вами алгоритм работает даже для поиска нескольких путей. Или, возможно, вам удалось придумать более умный тестовый пример, чем я. (Пожалуйста, опубликуйте свой лабиринт, чтобы я мог опробовать на нем свой алгоритм)
Моя реализация тупикового счетчика, вероятно, не самая эффективная, но она выполняет свою работу. Для каждого посещаемого текущего ОТКРЫТОГО узла он проверяет 4 окружающих узла:
- Если хотя бы один сосед ОТКРЫТ, текущий узел не тупик
- Если более одного соседа посещено, текущий узел не является тупиком
- Если только один узел посещен (тот, из которого мы пришли на предыдущем шаге) и ни один другой сосед не открыт, текущий узел является тупиком.
Это код Java, который я написал (осторожно! Довольно долго). Альтернативой может быть, если вы хотите, сохранить путь в стеке, нажимая узел каждый раз, когда он установлен в состояние VISITED, и выталкивая узел каждый раз, когда он возвращается в состояние OPEN. Каждый раз, когда достигается ЦЕЛЬ, стек, содержащий текущий путь, должен быть скопирован и сохранен.
Если блок if, помеченный комментарием как "dead-end-research-step", удален, эта реализация почти полностью совпадает с той, которая описана в вопросе.
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();
}
}
Вышеупомянутый алгоритм сообщает о четырех различных путях решения и двух тупиках к примеру лабиринта, который жестко запрограммирован в коде.
‹EDIT› Может быть причиной того, что вы получаете слишком мало путей решения, является неправильное толкование того, что такое путь решения? Например, рассмотрим этот лабиринт:
######
## #
## # #
#S #
##E###
######
В этом лабиринте есть только один допустимый путь решения. Это связано с тем, что вам разрешено посещать каждый узел только один раз, поэтому обход кругового пути не является допустимым путем решения, поскольку это приведет к посещению узла к востоку от S и к северу от E дважды. Это определение пути решения подразумевается используемым алгоритмом.
Если бы кто-то разрешил посещать один и тот же узел несколько раз, было бы бесконечно много решений, так как вы могли бы пройти по кругу 1, 2, 3 ... до бесконечного количества раз. ‹/EDIT›
‹EDIT2›
Точно так, как вы говорите, я увеличиваю pathLength каждый раз, когда устанавливаю узел в состояние VISITED, и уменьшаю длину пути каждый раз, когда устанавливаю узел VISITED обратно в положение OPEN.
Чтобы записать длину кратчайшего пути, у меня также есть значение shorttestPath int, которое я инициирую в 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›
person
Alderath
schedule
10.08.2009
