Кратчайший путь затрат

Мне нужно найти кратчайший путь из точки D в R. Это фиксированные точки. Это пример ситуации:

введите здесь описание изображения

В ящике также есть стены, через которые вы не сможете пройти, если не сломаете их. Каждое разрушение стены стоит вам, скажем, «а» очков, где «а» — положительное целое число. Каждый ход, не связанный со стеной, стоит вам 1 очко.

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

Поскольку ширина поля может достигать 100 ячеек, использование поиска с возвратом не имеет значения. Это слишком медленно. Единственное решение, которое я придумал, это одно:

  1. Идите на восток или юг, если нет стен
  2. Если на юге есть стена, проверьте, есть ли стена на западе. Если на западе есть стена, сломайте южную стену. Если на западе нет стены, идите на запад, пока не найдете южную камеру без стены. Повторите этот процесс с югом и востоком, пока не превысите стоимость сломанной стены в этом порядке. Если путь с запада ведет в то же место, как если бы я сломал южную стену, и стоит столько же или меньше очков «а», то используйте этот путь, иначе сломайте южную стену.
  3. Если ничего выше не встречается, разбейте южную или восточную стену, в зависимости от границы коробки.

Повторяйте шаги 1, 2, 3, пока «пассажир» не прибудет в точку R. Между этими тремя шагами существуют отношения «иначе-если».

Можете ли вы придумать лучший алгоритм решения задачи? Программирую на С++.


c++ algorithm shortest-path np
person Robert Lucian Chiriac    schedule 23.02.2014    source источник
comment
Что именно вы подразумеваете под поиском пути с минимальной стоимостью и минимумом сломанных стен? Что-то вроде из всех путей минимальной стоимости, с наименьшим количеством сломанных стен?   -  person harold    schedule 23.02.2014
comment
Да, из всех путей минимальной стоимости выберите тот, в котором меньше всего сломанных стен.   -  person Robert Lucian Chiriac    schedule 23.02.2014
comment
Знаю ли я, где находятся все стены, когда выхожу из D? Или я обнаруживаю их только тогда, когда достигаю их?   -  person Beta    schedule 23.02.2014
comment
Вам не нужно их открывать. Вы их уже знаете.   -  person Robert Lucian Chiriac    schedule 23.02.2014
comment
В чем причина отрицательного голосования?   -  person Robert Lucian Chiriac    schedule 23.02.2014

Ответы (4)


arrow_upward
3
arrow_downward

Используйте Дейкстру, но по стоимости дайте 1 за ход, который не ломает стену, и (a+0,00001) за разрушение стены. Тогда Дейкстра даст вам то, что вы хотите, путь, который ломает наименьшее количество стен среди всех путей с минимальными затратами.

Концептуально представьте себе путешественника, который может перепрыгивать через стены, сохраняя при этом стоимость, а также может разделиться на двух одинаковых путешественников, столкнувшись с выбором из двух путей, чтобы выбрать их обоих (возьми это, Роберт Фрост! ). Одновременно перемещается только один путешественник, тот, кто пока что понес наименьшие затраты. Тот движется и пишет на полу: «Я добрался сюда всего за х». Если я найду такую ​​заметку уже там, если я попал туда дешевле, я стираю старую заметку и пишу свою; если этот другой путешественник доберется туда дешевле, я покончу жизнь самоубийством.

person Beta    schedule 23.02.2014
comment
:( оптимизация на истощение - person im so confused; 23.02.2014
comment
Откуда берется лишний 0,00001? Это для того, чтобы отслеживать, сколько стен было перепрыгнуто? - person Robert Lucian Chiriac; 23.02.2014
comment
@RobertEagle: да, таким образом, в соревновании между двумя путями с одинаковой реальной стоимостью проиграет тот, в котором больше стен. (И прыгать через стены вместо того, чтобы ломать их, чтобы один путешественник не мог извлечь выгоду из сноса, выполненного другим.) - person Beta; 23.02.2014
comment
Что эффективнее? Используя Roy-Floyd (это дает вам возможность узнать путь), A * или его подмножество, Dijkstra? - person Robert Lucian Chiriac; 25.02.2014
comment
@RobertEagle: Это достаточно просто, чтобы каждый путешественник помнил свой путь. Я не знаком с Рой-Флойдом. Насколько A* будет полезен, зависит от того, как a соотносится с размером лабиринта. - person Beta; 25.02.2014

arrow_upward
1
arrow_downward

Двухчастное «сначала стоимость, затем сломанные стены» может быть представлено в виде пары (c, w), которая сравнивается лексикографически. c — стоимость, w — количество сломанных стен. Это снова делает его «одной вещью» (в некотором смысле), так что это вещь, которую вы можете поместить в алгоритмы и т. д., которые ожидают просто «затраты» (как абстрактную вещь, к которой она может добавить другую стоимость или сравнить на другую стоимость).

Таким образом, мы можем просто использовать A* с эвристикой манхэттенского расстояния (возможно, есть что-то умнее, чем не игнорирует стены полностью, но это сработает — недооценка расстояния допустима). Стоимость движения, конечно, не будет игнорировать стены. Соседями будут все соседние квадраты. Все расходы будут той парой, которую я описал выше.

person harold    schedule 23.02.2014
comment
Упоминание об использовании эвристики придает этому ответу больше доверия, чем другим ИМО. - person E_net4 the curator; 23.02.2014

arrow_upward
0
arrow_downward

Это можно легко смоделировать как взвешенный граф, а затем применить к нему алгоритм кратчайшего пути Дейкстры. Каждый квадрат является узлом. Он связан с узлами квадратов, к которым он примыкает. Вес соединений равен 1 или «а» в зависимости от того, есть стена или нет. Это принесет вам минимальные затраты. Возможно, что минимальная стоимость и минимальное количество разрывов стен могут отличаться.

person azurelogic    schedule 23.02.2014

arrow_upward
0
arrow_downward

Вот общий алгоритм (вам придется реализовать его самостоятельно):

Преобразуйте матрицу во взвешенный график:

  • Для каждой записи в матрице создайте Vertex.
  • Для каждого Vertex создайте массив Edges, по одному для каждого соседнего Vertex.
  • Для каждого Edge определите вес в соответствии со стоимостью разрушения стены между двумя Vertices, которые соединяет Edge.

Затем запустите алгоритм Дейкстры (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) на графике, начиная с Vertex D. На выходе у вас будет кратчайший (самый дешевый) путь от Vertex D до любого другого Vertex на графе, включая Vertex R.

person barak manos    schedule 23.02.2014