Прохождение каждой возможной ячейки в 2D-массиве

Question

Я не уверен, что назвать этой проблемой, но я уверен, что у нее есть имя. В противном случае найти ответ было бы проще.

Учитывая "карту" клеток, таких как:

O - - - 
- X - - 
- X X - 
- - - - 

где O = исходное положение, X = препятствие и - = заходило. Я хочу пройти эту карту (которую я сохранил как 2D-массив) и посещать как можно больше ячеек, не касаясь посещенной ячейки.

Мой алгоритм выглядит следующим образом:

1. Если я могу пойти направо, ехать прямо.
2. Иначе, если я могу спуститься вниз, спуститесь.
3. Else, если я могу пойти влево, идите налево.
4. Else, если я могу подняться вверх, поднимитесь.
5. Если я застрял, вернуться назад и отметьте, что ячейка «unvisitable», и вернуться к 1.

Так две проблемы:

• Для больших карт, количество препятствий, и где они размещаются часто заставляет мой алгоритм не доходить до многих ячеек. Я пробовал разные порядки 1-4 (т. Е. Всегда поднимался, если мог, и т. Д.), Но это, очевидно, зависит от данной карты.
• Я не знаю, когда остановиться. Если мой алгоритм достигает «конца», т. Е. Я действительно посещал каждую возможную ячейку, он не останавливается и просто возвращается назад к началу.

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

Answer 1

Существует название: самая длинная проблема пути: https://en.wikipedia.org/wiki/Longest_path_problem

В графической форме, сделать края от свободной ячейки к заблокированной ячейке имеют бесконечный вес и все остальные имеют вес 1 (или другая константа). Там нет «эффективного» (в алгоритмических терминах сложности) решения этой проблемы (если вы найдете тот, который вы будете знамениты!)

Для решения ваших две проблем:

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

2. Для вашего текущего алгоритма вы можете остановиться, когда вы вернулись к стартовому квадрату, а затем больше не двигайтесь. В противном случае ваш алгоритм выглядит корректно. Порядок шагов 1-4 не будет иметь никакого значения в конце. Чтобы узнать, какой путь является самым длинным, вам все равно придется попробовать их всех (с помощью этого подхода).

Редактировать: Я не уверен, что понял шаг 5, когда прочитал его раньше; текущий квадрат НЕ должен быть отмечен недостижимым, даже если вы застряли (если вы на этом квадрате, то вы его посетили), но окружающие квадраты (кроме того, из которого вы пришли). Пока вы не отмечаете текущий квадрат, который невозможен, алгоритм обратного отслеживания должен найти самый длинный путь правильно.

Answer 2

Ваш алгоритм не работает из-за подобные случаями:

O - - - 
X - - X 

, потому что ваш алгоритм будет первым пройти весь путь прямо

O 1 2 3 
X - - X 

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

O 1 4 5 
X 2 3 X 

---

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

, вероятно, более простой способ смотреть на это так:

• Следите за текущей позиции и все шаги вы предприняли, чтобы попасть туда.
• Для каждой позиции вы в конце концов попытаетесь выполнить шаг в каждом направлении в правом порядке (R), вниз (D), влево (L), вверх (U).
• Когда вы пробовали все направления для определенной позиции (т. Е. Вы пытались U), сделайте обратный шаг назад, выполнив последний шаг, который вы сделали.

---

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

C - - - Stack: [] 
X - - X Backtracked move: - 

Шаг вправо

# C - - Stack: [R] 
X - - X Backtracked move: - 

Шаг вправо

# # C - Stack: [R, R] 
X - - X Backtracked move: - 

Шаг вправо

# # # C Stack: [R, R, R] 
X - - X Backtracked move: - 

Попробуйте вправо, вниз, влево и вверх, обратите внимание, что вы застряли и backtrack, т. е. принять обратное право (le футы)

# # C - Stack: [R, R] 
X - - X Backtracked move: R 

Последний обратный ход был правильным, так что теперь попробуйте следующий ход, т. е., Шаг вниз

# # # - Stack: [R, R, D] 
X - C X Backtracked move: - 

Попробуйте прямо, попробуйте вниз, шаг влево

# # # - Stack: [R, R, D, L] 
X C# X Backtracked move: - 

Застрял снова, так что вернуться назад

# # # - Stack: [R, R, D] 
X - C X Backtracked move: L 

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

Перемотка вперед к первому интересному следующему шагу:

# C - - Stack: [R] 
X - - X Backtracked move: R 

Последний один был прав, так продолжать вниз.

# # - - Stack: [R, D] 
X C - X Backtracked move: - 

Вы, вероятно, получите точку сейчас, так что я просто быстро пересылкой путь:

# # # C Stack: [R, D, R, U, R] 
X # # X Backtracked move: - 

И возвратов весь путь:

C - - - Stack: [] 
X - - X Backtracked move: R 

Последний шаг был правильно, так что попробуйте вниз, влево и вверх. И вы сделали.

По пути вы отслеживаете самый длинный путь, который вы видели, и это ваш ответ.