Отзыв об алгоритме дерева Штейнера с ограничениями

Для задания мне нужно создать Дерево Штейнера. Однако это не типичное дерево Штейнера, поскольку структура графа, которую мы должны использовать, не позволяет вставлять новые вершины. Скорее, тестовые примеры определяют структуру графа из N вершин и M ребер, при этом конкретно помечая X вершин как целевые узлы. Это узлы, которые мы должны охватывать при использовании некоторых, ни одной или всех непомеченных вершин в графе.

Мое решение этой проблемы

  1. Примените алгоритм Дейкстры, чтобы найти кратчайший путь между всеми целевыми вершинами.
  2. For each of the shortest paths 1:n
    1. Extract all current selected path vertices into a set
    2. Извлечь все оставшиеся вершины в набор
    3. For all vertices of the current selected path 1:m
      1. Execute Dijkstra to find shortest path between current vertex and other path's vertices
      2. Если это создает связующее дерево, сохраните путь и длину в очереди приоритетов, отсортированных по значению длины.
  3. Всплеск приоритетной очереди и обратный путь

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

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


dijkstra graph-algorithm minimum-spanning-tree
person Jason    schedule 29.04.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

С некоторой помощью я разработал этот ответ для аналогичной проблемы, которая у меня была. Вместо добавления новых вершин, как в задаче пространственного дерева Штейнера, новыми точками Штейнера в этом графе являются вершины, лежащие на пути между отмеченными узлами. Для графа с N вершинами, M ребер, X требуют вершин и S найденных вершин (вершин на нашем пути):

  1. Вычислить все парные береговые пути (Floyd-Warshall, Johnson's, что угодно)
  2. for k in X
    1. remove k from X, insert k into S
    2. for v in (X + S) - Both sets
      1. find the shortest distance from k to v - path P
    3. for u in P (all vertices on the path)
      1. insert u into S
      2. если u существует в k, удалить u из k

Теперь к стене текста о том, что делает этот алгоритм. Мы выбираем вершину k в X, а затем находим минимальное расстояние до ближайшей другой вершины в целевом наборе X или в результирующем наборе S и называем его v. Затем мы следуем по пути узлов из {k, u} , вставляя их в наш набор результатов. Наконец, дважды проверьте и убедитесь, что все вершины в X, которые были на пути (не должно быть), удалены из X.

Любая новая вершина, которую вы хотите добавить, c, будет иметь минимальное расстояние до некоторого узла, уже имеющегося в вашем результирующем наборе S. Поскольку узлы, уже находящиеся в S, находятся на минимальном расстоянии друг от друга, отсюда следует, что c будет минимальным расстоянием от любой точки. в С до с. Например, если у вас есть три узла, A, B и C, если A и B уже находятся на минимальном расстоянии друг от друга, добавление C удовлетворяет требованию, что это минимальное расстояние от B, а путь минимального расстояния от А в С проходит через В.

Я провел некоторое исследование по проблеме дискретного дерева Штейнера (а именно это и есть), и это лучшее решение грубой силы, которое я нашел. Основная проблема будет заключаться в O(n^3) времени, необходимом для выполнения всех пар кратчайших путей, но тогда построение минимального дерева должно быть простым и быстрым, поскольку вам просто нужно найти информацию о расстоянии. Реализация, с которой я работал, хорошо описана в Википедии.

person NuclearAlchemist    schedule 02.05.2013