[informatik-bonn] Re: AW: AW: Blatt14

  • From: candlejack@xxxxxxxxxxxxx (Jochen Kläß)
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: 03 Feb 2003 23:53:39 +0100

"Andreas Wedel" <andreas@xxxxxxxxxxxxxxxxxxxx> writes:

> Die Lösung ist folgende, kann das sein? Wir optimieren zuerst so, dass
> wir eine Kante, z.B. von n nach x zuerst in Richtung (n-x) durchlaufen
> und danach den Pfad so wählen, dass wir in Richtung (x-n) optimieren.
> Damit ist der Fluss im ersten Schritt im zweiten ein Rückfluss und wir
> subtrahieren einen Wert. Unser Algorithmus dürfte nicht
> terminieren.........
> Oder???????????????
Vorsicht,
ich theoretisiere das mal durch
wir fangen an bei f=0
verbessern über einen Pfad der (n-x) enthält, angenommen c(n-x) sei
die kleinste Kapazität auf dem Pfad => f=sigma
jetzt die Verbesserung über (x-n), wieder mit c(x-n) kleinste
Kapazität => f= 2sigma, jetzt haben wir schon 2 Pfade durch die
jeweils sigma fliesst

Ehrlichgesagt keine Ahnung, ob das jetzt dagegenspricht das der
Terminiert oder nicht, aber irgendwie hab ich jetzt nicht so die Lust
genau diese Kombination an möglichen Reihenfolgen und Pfaden zu
suchen. Bei diesem riesigen Netzwerk kann ich genauso hoffen im Lotto
zu gewinnen.

ps. Wenn mir morgen einer mit sigma kommt, kann ich für nix mehr garantieren.

Other related posts: