Максимальный вес связного подграфа в ориентированном ациклическом графе

Question

Я работаю над проблемой исследования, связанной с логическими схемами (которые могут быть представлены как DAG).Каждый узел в группе доступности базы данных имеет заданный вес, который может быть отрицательным.Моя цель - найти связанный подграф таким образом, чтобы сумма весов узлов была максимальной.

Проблема подграфа с максимальным весом при заданных весах ребер, по-видимому, является NP-сложной, но я надеюсь, что направленно-ациклическая природа и тот факт, что я имею дело с весами узлов, а не весами ребер, делает проблемунесколько прощеМожет кто-нибудь указать мне правильное направление, как начать атаковать эту проблему?

Спасибо

Answer 1

проблема, которую вы упомянули, является NP-трудной, смотрите: «Обнаружение регуляторных и сигнальных цепей в сетях молекулярного взаимодействия» Трей Идекер, Оуэн Озье, Бенно Швиковски и Эндрю Ф. Сигел, Биоинформатика, том 18, с.233-240, 2002

и дополнительная информация к этому документу: http://prosecco.ucsd.edu/ISMB2002/nph.pdf

Answer 2

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

1)Lets say that your nodes have weights wn1,wn2,wn3,....wnN; where N is # of nodes.

2)Lets also say that the edges can be represented by e1,e2,e3,...eE; E- # of edges.

The weight of the edge ei:nj->nk can be defined as F(wnj,wnk), the function being
arbitrary. For simplicity we can assume wei=wnj+wnk.

Now if we assume that all node weights are independent and non-identical, then we
can say the same about the edge weights. As a DAG with non-identical edge weights
is NP hard, your problem too is. 

Having said that, I think you should proceed in the following way:
1)Look for similarity in node weights for your particular problem. If there are any,
try to look up the literature for similar problems. 

2)If they are hard to find, I suggest you translate your node weight problem to edge 
weight one, and see how the similarity in node weights translates to edge weights
problem and see what simplification can you apply to this problem, again from 
literature.

Надеюсь, это поможет.

Answer 3

Вы упомянули, что связно этот связанный подграф должен быть "максимальным". Для этого жадно выбирайте вершину и увеличивайте ее до тех пор, пока вы не сможете расти. это гарантирует максимальность. Однако если вы имеете в виду «максимум», то проблема может быть в NP_Complete. Также позвольте мне напомнить, что взвешенные по узлам графы являются более общими, чем граничные взвешенные графы. Каждый алгоритм, построенный для первого, применим к более позднему, но не всегда верен. Это очень легко увидеть. Попробуйте сами. То, что я понимаю проблему, я чувствую, что это в P. Если это правильно, то Подсказка для этого состоит в том, чтобы использовать некоторые специальные свойства для DAG (которые вы должны знать со времени исследования, и это кажется проблемой для заметок) Для общих графов это сводится к деревьям Штейнера, так что это NP-Cmplete (также для плоских графов).

Answer 4

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

Второй подход, начиная с каждого конечного узла, добавляет «теги» к каждому ребру, который отслеживает идентификаторы всех задействованных узлов, иобщий вес.Нет необходимости отмечать узел, так как каждый узел гарантированно посещается только один раз для каждой цепочки, начинающейся на листьях.Например, учитывая следующий ациклический ориентированный граф (направленный сверху вниз), где каждый узел весит 1:

                         A     G
                        / \   /
                       /   \ /
                      B     C
                      |    / \
                      D   E   F
                           \ /
                            H

Граница между A и B будет помечена {{D, B, A}, 3}у края между A и C будет два тега {{H, E, C, A}, 4} и {{H, F, C, A}, 4}.

После этой предварительной обработкинайдите путь наибольшего веса для каждого корневого узла.Информация находится в тегах их исходящих ребер.