Минимальная стоимость сильно соединила диграф
В Python я написал бы Ваш код как:
actions = {
1: doOne,
2: doTwo,
3: doThree,
}
actions[i]()
5 ответов
Ваша проблема известна как минимальный охват сильного подграфа (di) (MSSS) или, в более общем смысле, подграфа с минимальными затратами (di) и составляет NP-жесткий . См. Также другую книгу: стр. 501 и стр. 480 .
Я бы начал с удаления всех ребер, которые не удовлетворяют неравенству треугольника - вы можете удалить ребро a -> c, если идти a -> b -> c дешевле. Это напоминает мне TSP, но я не знаю, приведет ли это к чему-либо.
Моим предыдущим ответом было использование алгоритма Чу-Лю / Эдмондса , который решает проблему Arborescence ; как указали Казум и ШривацаР, это не помогает.
Похоже, то, что вы в основном хотите, является оптимальным решением для коммивояжера, когда разрешено посещать узлы более одного раза.
Редактировать:
Хмм. Не могли бы вы решить эту проблему, выполняя итерацию по каждому узлу i, а затем выполняя минимальное остовное дерево всех ребер, указывающих на этот узел i, объединенных с другим минимальным остовным деревом всех ребер, указывающих в сторону . 1148423] с этого узла?
Я бы попробовал это способом динамического программирования.
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))))
Определения сильно связанных , list-subgraphs-1 , digraph-equal , best и лучше оставлены в качестве упражнения для читателя.
Эта проблема эквивалентна описанной здесь: http://www.facebook.com/careers/puzzles.php?puzzle_id=1