Минимальная стоимость сильно связанного орграфа

Question

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

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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 оставлены в качестве упражнения для читателя.

Answer 3

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

Answer 4

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

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

1. Сокращение: удалите все края ab, если есть более дешевый или имеющий тот же самый путь стоимости, например: acb.

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

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

Шаг расчета:

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

Answer 7

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