Учитывая изображение ниже, мне нужно определить наиболее оптимальную последовательность на доске (зеленая линия). Синие / красные линии представляют возможные, но не лучшие ходы.
Вот правила:
- Вы можете перейти к любой плитке, которая является такой же, и является вашим соседом (диагональ действительна)
- После того, как вы посетили плитку, вы не сможете посетить ее снова.
Я думал о том, чтобы пройтись по каждому узлу и посмотреть на его соседей, а затем рекурсивно пройти. Как только я найду возможный ход, я смогу поместить его в структуру. Когда все возможные ходы найдены, я просто выбираю ход с наибольшим количеством узлов. Это становится более трудным, когда узел имеет более одного соседа, который соответствует.
Итак, есть ли алгоритм, который я могу использовать? Я думал о каком-то наводнении, но это не соответствует правилам № 2.
По запросу, вот видео с похожим игровым процессом. http://youtube.com/watch?v=eumnCTG0AE8
Ответы:
Вы можете рассматривать каждую группу связанных идентичных символов (и я имею в виду, что вы можете переходить от одного символа к другому) как отдельный график . Для каждого такого графа применяется поиск в глубину (DFS), начиная с каждого узла в графе, который еще не является частью самого длинного пути для этого графа . Каждый раз, когда вы заходите в тупик при применении DFS, проверяйте, не длиннее ли пройденный вами путь, чем глобальный максимум, который вы уже нашли. Если это так, сохраните его как новый самый длинный путь.
Вы заметите, что в предыдущем параграфе я упоминал о применении DFS несколько раз для каждого графика. Одного DFS, запущенного на графике, будет недостаточно. Рассмотрим этот конкретный случай:
Если бы случайно вы сначала запустили DFS на этом графике в самом верхнем узле, вы бы обнаружили, что самый длинный путь - это вертикальная линия, но это было бы неправильно. Это происходит каждый раз, когда вы запускаете алгоритм DFS в узле, который находится где-то внутри результирующего пути или не является его частью. В этом конкретном примере вам нужно также запустить алгоритм DFS с самого левого узла во второй строке. Это найдет правильный путь. Вообще говоря, вам нужно будет запускать алгоритмы DFS в каждом узле, который в настоящее время не является частью самого длинного пути для этого графа, как указано выше.
Абсолютным худшим сценарием для этого алгоритма будет доска, заполненная или в основном заполненная символом одного типа, однако это вряд ли произойдет в игре. Также будьте осторожны с тем, как хранить самые длинные пути для каждого графика. Если вы не оптимизируете этот бит, вам может быть лучше просто вызвать DFS для каждого узла на сцене. Предполагая, что вы не работаете с очень большими платами и что скорость не такая уж большая проблема, это решение должно быть достаточно быстрым.
С технической точки зрения, разбивая вашу доску на отдельные графики, вы получаете несколько « проблем с длинным путем ». Как мы видим из вашего примера, у вас могут быть циклы на вашем графике (например, наличие всех символов снаружи стадии одного типа), что означает, что в этой конкретной задаче вам нужно найти самый длинный путь в нескольких циклических неориентированных графах, что нельзя сделать за полиномиальное время .
Если вы обнаружите, что это слишком медленно, см. Этот ответ в StackOverflow для получения дополнительной информации о том, как оптимизировать отдельные «проблемы с длинным путем».
источник