Problem 3 - Schritt 4: minimaler Schnitt

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von leviathan »

So, gerade das ganze laufen lassen und festgestellt, dass doch alles in Ordnung ist - die randomTests() terminieren auch. Nach einer Weile. Einer ganzen, ganzen Weile... Ob das Problem jetzt in meinem Code oder eher doch im Profiler ist, werde ich dann versuchen festzustellen.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

kutschke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 16. Apr 2009 10:39

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von kutschke »

Hi!
Was benutzt du denn als Datenstruktur in der BFS? Eine Warteschlange wäre optimal, um die zu besuchenden Knoten zu speichern...

ice-breaker
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 216
Registriert: 14. Okt 2008 17:56

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von ice-breaker »

also mit TPTP brauchen die Tests natürlich eine ganze Ecke länger, TPTP hängt sich in die Java VM und wird eben andauernd mit Infos gefüttert.
Ich würde euch auch empfehlen die Agent.exe oder so nicht zu killen, wenn die auf einmal CPU oder Speicher frisst ohne Ende, das killt TPTP und es kommt die Meldung von daniel_b, ich habe es nur geschafft es zu fixxen, indem ich Eclipse gelöscht habe und ein brandneues genommen habe und da wieder TPTP installiert habe.

Vockilein
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 16. Apr 2009 18:29

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von Vockilein »

Ahahah bei mir gehts immer noch nicht. Ich kann in der Monitor Auswahl auch nur Java 1.5 pre auswählen.

Jemand ne Idee was da schief läuft? Ich hab das neuste Eclipse heute draufgemacht.

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von robert.n »

Vockilein hat geschrieben:Ahahah bei mir gehts immer noch nicht. Ich kann in der Monitor Auswahl auch nur Java 1.5 pre auswählen.

Jemand ne Idee was da schief läuft? Ich hab das neuste Eclipse heute draufgemacht.
Einfach eclipse paar mal neu starten und hoffen, dass auf einmal Java 1.5 or NEWER drinsteht... war bei mir genauso und ich weiß leider nicht, warum es plötzlich funktioniert hat. Geändert habe ich eigentlich nichts.

dalinger
Neuling
Neuling
Beiträge: 5
Registriert: 23. Mai 2009 20:01

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von dalinger »

Ich wollte kurz etwas zum Profiler sagen. Es ist möglich den Profiler HPROF über Eclipse zu starten. Dazu schreibt man z. B.
-Xrunhprof:cpu=samples,depth=8
in die vm arguments der jeweiligen run configuration. Unter Ubuntu 8.04 mit dazugehörigem Eclipse klappt das jedenfalls.

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von b00m3r »

Hallo zusammen,
könnt ihr mir mal verständlich erklären was das Zielbild der Aufgabe ist?

Ich verstehe den letzten Hinweis auf dem Blatt nicht so ganz!

Grüße

Benutzeravatar
Michael_R
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 172
Registriert: 4. Apr 2008 17:58
Wohnort: Frankfurt

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von Michael_R »

Die Kanten die Du auflisten sollst sind alle Kanten aus dem Original Graphen, die von Knoten aus der Menge A zu Knoten aus der Menge B führen.

In Menge A sind alle Knoten drin die nach Anwendung von Edmonds-Karp noch von der Quelle aus erreichbar sind.

In Menge B sind alle Knoten die im Original Graphen von der Quelle erreichbar waren, aber nach Anwendung von Edmonds-Karp nichtmehr erreichbar sind.

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von b00m3r »

Um diese Beschreibung mal mit Leben zu füllen versuche ich mal ein Beispiel.
Ich beziehe mich jetzt auf TestNr.1 testOneEdge()
Der Graph laute
A;
A -> B: 5.0;
B;
B -> A: 5.0;

Vor Anwendung des EK
5
A ---->B
<-----
5

Nach der Anwendung sieht der Graph folgermaßen aus:

A;
A -> B: 0.0;
B;
B -> A: 10.0;

Residualgraph
0
A ---->B
<-----
10

Das heißt in Menge A befindet sich nur noch {A} und in Menge B befindet sich {A,B}

Den MinCut bilden nun alle Kanten von den erreichbaren zu den nicht mehr erreichbaren Knoten!
MinCut Edge(A, B, 5)

Ist das so richtig ?

Benutzeravatar
Michael_R
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 172
Registriert: 4. Apr 2008 17:58
Wohnort: Frankfurt

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von Michael_R »

fast

In Menge B sind alle Knoten die im Original Graphen von der Quelle erreichbar waren, aber nach Anwendung von Edmonds-Karp nichtmehr erreichbar sind.
Knoten A ist daher nicht in Menge B

b00m3r
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 10. Okt 2005 11:02

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von b00m3r »

Ich denke das Gerüst was ich gebastelt habe stimmt.
Hab die zwei Mengen A und B programmiert und die MinimalCutlogik sollte stimmen. 5 von 10 Tests laufen schonmal.Aber hab eben festgestellt das ich noch ein Problem habe mit dem SenkKnoten in der reachableSet. Die Funktion edmondskarp verlangt ja eine Quelle und eine Senke in der reachableSet bekommt man jedoch nur eine Quelle übergeben. Ich rufe reachableSet mit der Startknotenliste auf, sodass ich jeden Startknoten mitnehme. Wie bekomm ich das jetzt für die Senken hin.Momentan betrachte ich jeden Knoten im Graphen einmal als Senke. Was natürlich quatsch ist. Wie habt ihr das gelöst?

Also das Problem ist konkret wie kann ich auf die Zielknotenliste in der reachableSet zugreifen? Wie habt ihr das elegant gelöst.


EDIT habs Problem gelöst haben ja so ne tolle funktion gehabt addSuper... :)

dumbo2
Neuling
Neuling
Beiträge: 9
Registriert: 20. Mai 2009 20:05

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von dumbo2 »

Also ich komm hier irgendwie nicht weiter. Meine Tests laufen alle durch, bis auf Random und Big.

Bei random hängt er bei 588, aber gibt keine Fehlermeldung zurück, sondern bleibt einfach stehen und frist CPU und Speicher.

Die anderen Tests (edmondKarp, augmentingPath, BFS) laufen jeweils unter 1sec durch. Ich iteriere, wenn ich Listen habe nur über LinkedLists, Vergleiche(contains) werden nur auf Sets gemacht. mincut läuft so ab:

graph nehmen, supersource/sink einbauen
graph clonen
edmondkarp auf geclonten graph
erreichbare Knoten für den geclonten graph

dann für jeden erreichbaren knoten(a)
für jeden nachbarn(b) von (a)
wenn (b) nicht in erreichbaren Knoten Set
füge kante a->b in ergebnisliste


Hab auch nochmal TPTP 50sec laufen lassen, aber so wirklich schlau werd ich nicht draus.
Also nur mincutTest random:
-------------------------Cumulative Time----Calls
mincut-----------------16---------------------588
bfs--------------------- 2,23------------------32710
augmentingpath------3,11------------------31536
edmondkarp-----------9,7-------------------1175
reachable--------------0,04------------------587
addsupersourcesink--0,25------------------588

Auffällig ist wohl, dass EdmondKarp 2 mal aufgerufen wird, aber in mincut selber tue ich es definitiv nur einmal. Es müsste also auch nur 587/588 sein. Reachable haengt bei 587, weil es EdmondKarp tut, zumindest der zweite Aufruf.
Ich verstehs wirklich nicht, naja, mal sehen was nach dem Weitertüfteln bei rauskommt.

Gruß Olli

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von robert.n »

augmentingPath/BFS wird sehr oft aufgerufen... vllt. kommst du in edmondsKarp() in eine Endlosschleife, weil er nie aufhört zunehmende Wege zu finden? edmondsKarp() wird übrigens AFAIK von den Testcases nochmal aufgerufen...

der_andy
Neuling
Neuling
Beiträge: 6
Registriert: 7. Jun 2009 01:52

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von der_andy »

Leider hab ich ebenfalls das Problem, dass die Tests Random, sowie Big mit der Fehlermeldung:
"is a minimum cut expected:<534.5353689520231> but was:<368.40680038679596>" (Random) bzw.
"is a minimum cut expected:<122.90144875328525> but was:<87.55557550738746>" (Big)
fehlschlagen! Ich hab schon alle Forenbeiträge zu diesem Thema durchgearbeitet, doch leider konnte ich dieses Problem nicht beheben. Alle anderen Test's laufen einwandfrei durch.
Hat vielleicht jemand das selbe Problem aktuell bzw. gelöst?

Gruß Andy

dumbo2
Neuling
Neuling
Beiträge: 9
Registriert: 20. Mai 2009 20:05

Re: Problem 3 - Schritt 4: minimaler Schnitt

Beitrag von dumbo2 »

Bah, könnte meinen Kopf gegen die Wand schlagen.

Mein Fehler war, dass ich in EdmondKarp die Variablen tempFlow und flow zur Berechnung des maximalen Flusses in einem Pfad nach dem verändern des Graphen nicht reseted hab, bei mir auf Double.pos_inf .

Nun laufen alle Tests in 5,9 sec durch!

Schönen Sonntag noch und danke für die Hilfe.

Gruß Olli

Antworten

Zurück zu „Archiv“