Логика позади стекового алгоритма лабиринта

Question

Логика позади стекового алгоритма лабиринта

Я довольно плохо знаком с программированием на C ++ и работаю над алгоритмом решения лабиринтов. Мне нужно использовать явный стек, чтобы отслеживать ходы, без рекурсии.

В основном я отвечаю за алгоритм «Солвер», я могу проверить, доступно ли движение или заблокировано, и могу ли я сделать это, или я могу отменить ход. Ходы влево, вправо и вперед. Уже есть код, который заботится о рисовании и обновлении лабиринта.

То, что я мог бы использовать, — это лишь некоторая помощь в понимании основного алгоритма обхода лабиринта. Я смотрел на множество различных программ для этого, но я просто не могу понять это. Лабиринт, который я решаю, создается случайно, без петель.

Вот что я не могу обернуть вокруг себя: скажем, у меня прямой участок стены, но из стены также выходит ветвь. Скажем, я решил пойти по этой другой ветке, но в итоге это зашло в тупик. Я поместил все ходы, которые я сделал, в стек. Как узнать, сколько ходов мне нужно, чтобы выскочить из стека, чтобы узнать, что я вернулся на исходный перекресток, чтобы я мог взять другую ветку вместо заблокированной?

Спасибо за любую помощь!

3

algorithm c++depth-first-search maze

Решение

Другие решения

Для начала добавьте все возможные ходы из начальной позиции. Затем просто следуйте этому алгоритму:

На каждой итерации пытайтесь вытолкнуть один кадр из стека. Если стек был пуст, вы перепробовали все возможные ходы.

Теперь посмотрите на позицию, которую вы вытолкнули из стека. Это ваша текущая позиция.

Добавьте все ходы из позиции, которую вы вытолкнули, что приводит к неисследованным позициям в стек. Если какой-либо из них является целью, вы готовы.

Остальное позаботится о себе. Подумайте об этом, попробуйте несколько случаев на бумаге, вы увидите. 🙂

2

У вас не так много решений: в основном, исследовать лабиринт без петель — это все равно что поиск в глубину на покрывающее дерево, каждое пересечение является узлом.

Вы можете построить дерево по ходу работы и использовать эту информацию, чтобы пройти через него, но это будет утомительно и не очень эффективно.

Распространенный метод поиска в глубину сначала состоит в том, чтобы поместить все проверяемые узлы в стек, вытянуть один и нажать еще раз, пока не достигнете цели. Но вы получаете много узлов, и, как только вы нашли целевой узел, вы не можете использовать стек, чтобы узнать, какой путь вы выбрали, а это значит, что вам нужно хранить эту информацию в другом месте.

Вероятно, лучше сохранить решение стека и помечать узлы в вашем стеке, чтобы указать ветку, и в каком направлении (т.е. какое поддерево) ветви было исследовал (или какие пути остались). Если вы делаете исследование всегда в тот же порядок, этот тег может быть просто числом:

0 слева
1 для фронта
2 за право
3 для возврата

или еще лучше перечисление.

Когда найден тупик, просто раскрутите стек, пока не найдете один из этих узлов, и попробуйте новое направление. Если все направления были опробованы, другими словами, если направления не осталось, размотайте снова.

enum Branch {
LEFT,
FORWARD,
RIGHT,
BACKTRACK
};

struct BacktrackException{
};

template <typename MazeMove>
struct StackNode {
MazeMove move;
Branch branch;
StackNode(MazeMove m): move(m), branch(LEFT) {}
MazeMove nextBranch(){
switch(branch){
case LEFT:
if (move.can_left()){
branch = FORWARD;
return move.left();
}
case FORWARD:
if (move.can_forward()){
branch = RIGHT;
return move.forward();
}
case RIGHT:
if (move.can_right()){
branch = BACKTRACK;
return move.right();
}
default:
throw BacktrackException();
}
}
};

Приведенный выше код предоставляет оболочку для возможного класса «MazeMove», используемого со стеком, который отслеживает предпринятое направление. Метод nextBranch возвращает следующий возможный ход или генерирует исключение.

Преимущество заключается в том, что ваш стек не забит непроверенными ходами. Вы нажимаете StackNode каждый раз, когда вы достигаете новой позиции и раскручиваете ее, когда все ее варианты были опробованы. Когда вы достигнете выхода из лабиринта, ваш стек будет содержать только необходимые ходы.

1

Как узнать, сколько ходов мне нужно, чтобы выскочить из стека, чтобы узнать, что я вернулся на исходный перекресток, чтобы я мог взять другую ветку вместо заблокированной?

Вы не — вы всегда возвращаетесь точно один шаг. Затем проверьте все (оставшиеся) альтернативы, затем вернитесь на шаг вперед … и т. Д. Это называется возвраты.

Кстати, это одинаково, используете ли вы рекурсию или нет. Использование рекурсии просто делает стек неявным, а обработка стека автоматически.

0

Источник

Accepted Answer

Вот что я не могу обернуть вокруг себя: скажем, я решил пойти по другой ветке, но в итоге это зашло в тупик. Я поместил все ходы, которые я сделал, в стек. Как узнать, сколько ходов мне нужно, чтобы выскочить из стека, чтобы узнать, что я вернулся на исходный перекресток, чтобы я мог взять другую ветку вместо заблокированной?

Все, что вам нужно сделать, это всегда делать выбор в заранее определенном порядке.

Ходы влево, вправо и вперед.

Если вы всегда будете делать этот выбор в таком порядке, вы будете знать, что уже сделали, когда вернетесь.

Каждый шаг Вы вернетесь назад, проверьте эти ходы снова. Если вы удаляете право выбор, вы будете знать, что вы пытались оставил а также право, но еще не пробовал вперед.

5