Сильно связный орграф минимальной стоимости

StackOverflow https://stackoverflow.com/questions/1536067

Вопрос

У меня есть орграф, который сильно связан (т.существует путь от i к j и от j к i для каждой пары узлов (i, j) в графе G).Я хочу найти из этого графа сильно связный граф, у которого сумма всех ребер будет наименьшей.

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

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

Редактировать

Более общее описание:Для данного графа G(V,E) найдите граф G'(V,E') такой, что если существует путь от v1 до v2 в G, то также существует путь между v1 и v2 в G' и сумма каждого ei в E' является наименьшим возможным.так что это похоже на поиск минимального эквивалентного графа, только здесь мы хотим минимизировать сумму весов ребер, а не сумму ребер.

Редактировать:

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

Это было полезно?

Решение

Ваша проблема известна как минимальный охват сильный под(ди)граф (MSSS) или, в более общем плане, минимальная стоимость, охватывающая под(ди)граф, и NP-сложно действительно.Смотрите также еще одну книгу: страница 501 и страница 480.

Я бы начал с удаления всех ребер, которые не удовлетворяют неравенству треугольника — вы можете удалить ребро a -> c, если переход a -> b -> c обходится дешевле.Это напоминает мне TSP, но не знаю, приведет ли это к чему-нибудь.

Мой предыдущий ответ заключался в использовании Алгоритм Чу-Лю/Эдмондса который решает Древовидность проблема;как отметили Казум и ШриватсаР, это не помогает.

Другие советы

Я бы попробовал это в виде динамического программирования.

0- поместить график в список

1- составьте список новых подграфов каждого графа в предыдущем списке, где вы удалите по одному ребру для каждого из новых подграфов.

2- удалить дубликаты из нового списка

3- удалить из нового списка все графы, которые не сильно связаны

4- сравнить лучший график из нового списка с текущим лучшим, если лучше, установить новый текущий лучший

5- если новый список пуст, лучшим решением является текущее решение, в противном случае используйте recurse/loop/goto 1.

В Лиспе это могло бы выглядеть так:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

Определения strongly-connected, list-subgraphs-1, digraph-equal, best, и better оставлены в качестве упражнения для читателя.

Эта проблема эквивалентна проблеме, описанной здесь: http://www.facebook.com/careers/puzzles.php?puzzle_id=1

Несколько идей, которые помогли мне решить знаменитую головоломку с фейсбуллом:

Этап предварительной обработки:

  1. Обрезка:удалите все ребра a-b, если есть дешевле или имеющие та же стоимость путь, например:а-в-б.

  2. Разложение графа:можно решать подзадачи, если на графике есть точки артикуляции

  3. Объедините вершины в одну виртуальную вершину, если имеется только одно исходящее ребро.

Шаг расчета:

  1. Получите приблизительное решение, используя направленный TSP с повторными посещениями.Используйте Флойда Уоршалла, а затем решите задачу о назначениях O (N ^ 3), используя венгерский метод.Если у нас получился один цикл - это направленное решение TSP, если нет - используйте ветвь и связанное TSP.После этого у нас есть верхняя граница значения — цикл минимальной стоимости.

  2. Точное решение – метод ветвей и границ.Мы удаляем вершины из кратчайшего цикла и пытаемся построить сильно связный граф с меньшими затратами, чем верхняя граница.

Вот и все, ребята.Если вы хотите протестировать свои решения — попробуйте здесь: http://codercharts.com/puzzle/caribbean-salesman

Похоже, вы хотите использовать Алгоритм Дейкстры

Похоже, что вам в основном нужно оптимальное решение для коммивояжера, где разрешено посещение узлов более одного раза.

Редактировать:

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

2-приближение минимальный сильно связный подграф получается объединением минимального входящего и минимального исходящего ветвления, корнем которых является одна и та же (но произвольная) вершина.

Ан разветвляющийся, также известен как древовидность, представляет собой ориентированное дерево с корнем в одной вершине, охватывающее все вершины.Внутреннее ветвление аналогично обратным ребрам.Их можно найти по Алгоритм Эдмондса во время О(ВЭ), и есть ускорения О (E журнал (V)) (см. вики-страница).Есть даже реализация с открытым исходным кодом.

Исходной ссылкой на результат 2-приближения является статья JaJa и Фредериксона, но бумага не находится в свободном доступе.

Существует даже приближение 3/2 Адриана Ветты. (PDF), но сложнее предыдущего.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top