Кратчайший путь стоимости
Я должен найти кратчайший путь от точки D до R. Это фиксированные точки.
Это пример ситуации:
Коробка также содержит стены, через которые вы не можете пройти через них, если не сломаете их. Каждый разрыв стены стоит, скажем, точки «а», где «а» — положительное целое число.
Каждый ход, в котором нет стены, стоит вам 1 очко.
Миссия состоит в том, чтобы найти из всех путей с минимальными затратами путь с минимальным количеством сломанных стен.
Поскольку ширина ящика может доходить до 100 ячеек, использовать возврат не имеет значения. Это слишком медленно. Единственное решение, которое я придумал, это:
- Идите на восток или юг, если нет стен
- Если на юге есть стена, проверьте, есть ли на западе стена. Если на западе есть стена, сломайте южную стену. Если на западе нет стены, идите на запад, пока не найдете южную камеру без стены. Повторите этот процесс с югом и востоком, пока вы не превысите стоимость сломанной стены в этом порядке. Если путь с запада идет в то же место, как если бы я сломал южную стену, и стоит столько же или меньше, чем точки «а», тогда используйте этот путь, иначе затормозите южную стену.
- Если ничто из вышеперечисленного не встречается, затормозите южную или восточную стену, в зависимости от границы коробки.
Повторяйте шаги 1, 2, 3 до тех пор, пока «пассажир» не прибудет в точку R. Между этими 3 шагами существуют отношения «иначе-если».
Можете ли вы придумать лучший алгоритм проблемы? Я программирую на C ++.
Решение
Используйте Dijkstra, но для затрат дайте ему 1 за ход, который не сломает стену, и (+ 0,00001) за сломанную стену. Тогда Дейкстра даст вам то, что вы хотите, путь, который разбивает наименьшее количество стен среди всех путей с минимальными затратами.
Концептуально, представьте себе путешественника, который может перепрыгнуть через стены — при этом отслеживая стоимость — и может также разделиться на двух одинаковых путешественников, когда они сталкиваются с выбором двух путей, чтобы взять их обоих (возьмите это, Роберт Фрост! ). За один раз перемещается только один путешественник, который понес самую низкую стоимость. Тот движется и пишет на полу: «Я достиг здесь по цене только х». Если я нахожу такую заметку уже там, если я попал туда дешевле, я стираю старую заметку и пишу свою; если тот другой путешественник доберется туда дешевле, я совершу самоубийство.
Другие решения
«Сначала стоимость, а затем сломанные стены» можно представить в виде пары (c, w), которую сравнивают лексикографически. c — стоимость, w — количество сломанных стен. Это снова делает его «одной вещью» (в некотором смысле), так что это вещь, которую вы можете поместить в алгоритмы и т. Д., Которая ожидает просто «стоимость» (как абстрактная вещь, которая может добавить другие затраты или сравнить на другие расходы).
Таким образом, мы можем просто использовать A *, с эвристикой Манхэттенского расстояния (возможно, есть что-то более умное, которое не полностью игнорирует стены, но это сработает — недооценка расстояния допустима). Стоимость движения, конечно, не будет игнорировать стены. Соседи будут все прилегающие площади. Все расходы будут в паре, которую я описал выше.
Это можно легко смоделировать как взвешенный график, а затем применить Алгоритм кратчайшего пути Дейкстры к этому. Каждый квадрат — это узел. Он связан с узлами квадратов, к которым он прилегает. Вес соединений равен 1 или «а», в зависимости от того, есть стена или нет. Это даст вам минимальную стоимость. Возможно, что минимальная стоимость и минимальное количество разломов стен могут отличаться.
Вот общий алгоритм (вам придется делать реализацию самостоятельно):
Преобразовать матрицу в взвешенный график:
- Для каждой записи в матрице создайте
Vertex, - Для каждого
Vertexсоздать массивEdgesпо одному на каждого соседнегоVertex, - Для каждого
Edgeопределите вес в соответствии со стоимостью разрушения стены между двумяVerticesчтоEdgeподключается.
Затем запустите алгоритм Дейкстры (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) на графике, начиная с Vertex D, В результате вы получите кратчайший (самый дешевый) путь из Vertex D к любому другому Vertex на графике, в том числе Vertex R,