Какой алгоритм я могу использовать, чтобы найти кратчайший путь между указанными типами узлов в графе?

Question

Это проблема:

У меня есть n точек (p1, p2, p3, .. pn), каждая из которых может подключаться к любой другой с определенной стоимостью x.

Каждая точка принадлежит одному из набора типов точек (например, «A», «B», «C», «D» ...).

Ввод метода - путь, по которому я хочу пойти, например, «A-B-C-A-D-B».

Выход - это кратчайший путь, соединяющий точки типа, которые я даю на входе, например, «p1-p4-p32-p83-p43-p12», где p1 - это тип A, p4 - тип B, p32. C-тип, p83 A-тип, p43 D-тип и p12 B-тип.

«Простое» решение состоит в расчете ВСЕХ возможных путей, но вычислительные затраты очень высоки!

Может кто-нибудь найти лучший алгоритм?

Как я сказал в заголовке, я не знаю, существует ли он!

Обновление:

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

В качестве входных данных у меня есть массив типов, и я должен ссылаться в этом порядке.

Это изображение Кента Фредрика (большое спасибо), которое описывает исходную ситуацию (красным разрешены ссылки)!

Пример из реальной жизни:

Человек хочет посетить церковь утром, пойти в ресторан и, наконец, посетить музей днем.

На карте 6 храмов, 30 ресторанов и 4 музея.

Он хочет, чтобы расстояние церковь-отдых-музей было минимально возможным.

Answer 1

Вы можете использовать алгоритм Флойда-Варшалла. Вот псевдокод, данный WikiPedia:

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
   (infinity if there is none).
   Also assume that n is the number of vertices and edgeCost(i,i)=0
*/

int path[][];

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
   from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
   edgeCost(i,j) or infinity if there is no edge between i and j.
*/

procedure FloydWarshall ()
    for k: = 1 to n
        for each (i,j) in {1,..,n}2
            path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Мне пришлось написать программу для курса по алгоритмам об этой же проблеме. Этот алгоритм работал как шарм! Гудлак.

Answer 2

Вот как я сейчас интерпретирую вашу проблему.

Красные стрелки - это я, вручную отслеживающий пути, которые соответствуют заданному ограничению порядка.

Стоимость не указана, но предполагается, что все ссылки несут затраты, а стоимость ссылок различается.

Если это точно описывает сценарий, который вы пытаетесь решить, скажите, пожалуйста, чтобы другие могли лучше ответить на вопрос.

Answer 3

Как упомянул Ян, вам просто нужен обычный скучный алгоритм кратчайшего пути (например, алгоритм Дейкстры или Флойда ); однако вам необходимо преобразовать входной граф так, чтобы выходной путь соответствовал вашему ограничению пути.

Учитывая ограничение пути: A - B - A

Создайте новый график G и вставьте все вершины из A в G с новыми метками, такими как a_01. Затем вставьте все вершины из B в G и соедините вершины A с вершинами B (ребра должны быть направлены к вновь вставленным узлам), копируя затраты из исходного графа. Затем вы повторите этот шаг с A (и любыми другими компонентами пути), соединяющими вновь вставленные вершины с вершинами в B. Таким образом, вы создаете график, в котором только существующие пути удовлетворяют ограничению пути. Затем вы можете использовать обычные алгоритмы кратчайшего пути.

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

Answer 4

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

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

Answer 5

Вот псевдокод с решением динамического программирования:

n - length of desired path
m - number of vertices
types[n] // desired type of ith node
vertice_types[m]
d[n][m] // our DP tab initially filled with infinities

d[0][0..m] = 0
for length from 1 to n 
  for b from 0 to m
    if types[length] == vertice_types[b]
      for a from 0 to m
        if types[length-1] == vertice_types[a]
          d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b))

минимальная стоимость пути min (d [n] [0..m])

Вы можете уменьшить размер таблицы d до 2 строк, но это затуманивает решение

Answer 6

При пересмотре вашего вопроса кажется, что вы запрашиваете один узел на букву - в этом случае это простое решение для динамического программирования: вычислите все кратчайшие пути длины 1, которые удовлетворяют началу вашей последовательности, между каждой парой узлов. Тогда, имея для k все такие пути для всех пар узлов, тривиально построить для k + 1.

Answer 7

1. Рассчитать все пары кратчайших путей в каждом блоке эквивалентности.
2. Теперь создайте граф, в котором НЕТ ребер между классами, но ребра которых между классами соответствуют кратчайшему пути в этом классе, что ведет к конкретному узлу другого класса.

Надеюсь, это понятно.

Это решение не особенно эффективно, но явно полиномиально.

Answer 8

Насколько я понимаю ваш вопрос, вам нужен кратчайший путь в ориентированном графе. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm должно дать вам представление.

С уважением, Ян