Ich arbeite an einem Forschungsproblem mit Logikschaltungen (die als DAGs dargestellt werden können). Jeder Knoten in der DAG hat eine bestimmte Gewichtung, die negativ sein kann. Mein Ziel ist es, einen verbundenen Subgraphen so zu finden, dass die Summe der Knotengewichte maximal ist.
Das mit den Kantengewichten verbundene maximale Gewicht-Subgraph-Problem ist anscheinend NP-hart, aber was ich hoffe, ist, dass die gerichtete azyklische Natur und die Tatsache, dass ich Knotengewichte anstelle von Kantengewichten behandle, das Problem etwas leichter macht. Kann mir jemand in die richtige Richtung zeigen, wie ich dieses Problem angehen soll?
Danke
Das von Ihnen erwähnte Problem ist NP-schwer, siehe: "Aufdeckung regulatorischer und signalisierender Schaltkreise in molekularen Interaktionsnetzwerken" von Trey Ideker, Owen Ozier, Benno Schwikowski und Andrew F. Siegel, Bioinformatics, Bd. 18, S. 233-240, 2002
und die ergänzenden Informationen zu diesem Papier: Ссылка
Erster Ansatz, Weisen Sie jeder Kante die Umkehrung der Gewichtung des Startknotens zu und wenden Sie einen Algorithmus für den kürzesten Pfad an, wie Bellman -Ford . Der Algorithmus von Dijkstra funktioniert nicht, da einige Kanten negativ sein können.
Der zweite Ansatz, der an jedem Blattknoten beginnt, fügt "Tags" zu jeder Kante hinzu, die die IDs aller beteiligten Knoten und das Gesamtgewicht verfolgt. Es ist nicht notwendig, den Knoten zu markieren, da jeder Knoten garantiert nur einmal für jede Kette besucht wird, die auf den Blättern beginnt. Zum Beispiel mit dem folgenden azyklisch gerichteten Graphen (von oben nach unten gerichtet), bei dem jeder Knoten 1:
gewichtet %Vor%Die Kante zwischen A und B wird markiert {{D, B, A}, 3}, die Kante zwischen A und C hat zwei Tags {{H, E, C, A}, 4} und {{ H, F, C, A}, 4}.
Suchen Sie nach dieser Vorverarbeitung den größten Gewichtungsweg für jeden Stammknoten. Die Information befindet sich in den Tags ihrer Ausgangskanten.
Sie haben erwähnt, dass der zusammenhängende Subgraph "maximal" sein sollte. Wählen Sie dazu gierig einen Eckpunkt und wachsen Sie, bis Sie nicht wachsen können. Dies sichert die Maximalität. Wenn Sie jedoch "Maximum" meinen, könnte das Problem NP_Complete sein. Lassen Sie mich auch daran erinnern, dass Knoten-gewichtete Graphen allgemeiner sind als Kanten-gewichtete Graphen. Jeder Algorithmus, der für den ersteren erstellt wird, ist später anwendbar, aber umgekehrt ist dies nicht immer der Fall. Das ist sehr leicht zu sehen. Probier es selbst aus. Was ich verstehe das Problem, ich fühle, dass es in P ist. Wenn das richtig ist, dann ist der Tipp dafür, eine spezielle Eigenschaft für DAGs zu verwenden (die Sie seit Ihrer Forschung wissen, und dies scheint ein Vortragsnotiz-Problem). Für allgemeine Graphen ist dies auf Steinerbäume reduzierbar, so dass es NP-Cmplete (tatsächlich auch für planare Graphen) ist.
Ich denke, Ihr Problem ist NP schwer, wenn das maximale Gewicht verbunden Subgraphenproblem gegeben Randgewichte NP schwer ist. Sie können das Knotengewichtproblem auf das Kantengewichtproblem reduzieren.
%Vor%Ich hoffe, das hilft.
Tags und Links algorithm graph-theory theory directed-acyclic-graphs