Negative Summe in gerichtetem Graphen

10/01/2012 - 11:14 von Jan Fricke | Report spam
Hallo NG,
ich suche einen (einfache) Algorithmus für folgendes Problem:

Gegeben ist ein gerichteter Graph mit N Knoten, wobei jeder Kante eine
reelle Zahl zugeordnet ist.

Gesucht ist ein Zyklus, für den die Summe der Zahlen an den Kanten
positiv ist, oder die Entscheidung, dass es keinen solchen gibt.


Naiver Ansatz: Ich schreibe die Zahlen in eine Matrix A_1, nicht
verbundene Ecken bekommen einen hinreichend negativen Wert.

Dann bilde ich iterativ A_(n+1) aus A_n durch

c(i,j) = max(b(i,k) + a(k,j)),
k

wobei a(i,j), b(i,j) bzw. c(i,j) die Eintràge von A_1, A_n bzw. A_(n+1)
sind. Wenn es nach spàtestens N Iterationen noch keinen positiven
Eintrag gab, dann wird es nie einen geben. Wenn man einen positiven
Eintrag hat, dann irgendein Backtracking?



Viele Grüße Jan
 

Lesen sie die antworten

#1 Jens Voß
10/01/2012 - 12:51 | Warnen spam
Hallo Jan,

ich suche einen (einfache) Algorithmus für folgendes Problem:

Gegeben ist ein gerichteter Graph mit N Knoten, wobei jeder Kante eine
reelle Zahl zugeordnet ist.

Gesucht ist ein Zyklus, für den die Summe der Zahlen an den Kanten
positiv ist, oder die Entscheidung, dass es keinen solchen gibt.

Naiver Ansatz: Ich schreibe die Zahlen in eine Matrix A_1, nicht
verbundene Ecken bekommen einen hinreichend negativen Wert.

Dann bilde ich iterativ A_(n+1) aus A_n durch

        c(i,j) = max(b(i,k) + a(k,j)),
                  k

wobei a(i,j), b(i,j) bzw. c(i,j) die Eintràge von A_1, A_n bzw. A_(n+1)
sind. Wenn es nach spàtestens N Iterationen noch keinen positiven
Eintrag gab,



Ich vermute, mit "Eintrag" meinst Du hier einen auf
der Diagonalen?

dann wird es nie einen geben. Wenn man einen positiven
Eintrag hat, dann irgendein Backtracking?



Kann man doch schon beim Bestimmen der Maxima machen:
Wenn A_1 und A_n wie oben sind, speichere in d(i,j)
einfach dasjenige k, für das die Summe b(i,k) + a(k,j)
maximal wird setze B_n := ( d(i,j) ). Aus den Indizes
in den B_k kann dann der Zyklus abgelesen werden.

Ansonsten, schöne Idee.

Gruß,
Jens

Ähnliche fragen