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

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

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

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

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

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

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

Шаг расчета:

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

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

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

Answer 7

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

Edit:

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