Кратчайший путь в лабиринте с потерей здоровья

Question

Предположим, у вас есть подземелье, представленное 2D-матрицей.У вас есть начальная точка S (x1, y1) и конечная точка E (x2, y2).По пути в некоторых клетках есть число, которое вычитает ваш счет здоровья.Другие клетки - это препятствия, через которые вы не можете пройти.Вы начинаете с 5 очков здоровья, и вам нужно найти кратчайший путь от S до E, где вы не умрете в пути.

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

Answer 1

Стандартный подход к таким проблемам иногда называют «наслоением графа».Вы делаете 5 копий исходного графа (в данном случае пронумерованных от 0 до 4), где получение вершины v в графе n означает получение соответствующей вершины в исходном графе послестрадания n смертей.

Если ребро в исходном графе стоит вам жизни, то оно соединяет вершину в каждом графе i с вершиной в графе i + 1 , и в противном случае он соединяет вершины в той же версии графа, как и оригинал.

После построения этого графа используйте алгоритм Дейкстры, чтобы найти кратчайший путь к конечной вершине в любомслой.

Answer 2

Просто используйте A *, более того, соответственно уменьшайте здоровье при каждом движении, но учитывайте каждое движение, при котором здоровье достигнет 0, как если бы этот случай был препятствием.

Редактировать: для удобства я приложу ссылку на статьи об A *: это и это и это

Пояснительное примечание: Может быть сложно увидеть, A * сначала пытается жадно, но затем возвращается и в конечном итоге находит кратчайший возможный маршрут. Здесь я не предполагаю, что случай навсегда помечен как препятствие, а просто локально считается эквивалентным препятствию для текущего выбора, если он вызывает смерть. После нахождения первого пути этот расширенный A * не должен останавливаться, а должен использовать длину этого пути в качестве верхней границы и обратной трассировки в дереве решений, проверяя все открытые пути. Это будет работать.