Wichtig::BUG KRUSKAL ALGORITHM

sch3rvv1n
Erstie
Erstie
Beiträge: 17
Registriert: 22. Apr 2015 10:58

Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von sch3rvv1n »

Hallo,
Ich habe einen Bug gefunden. Wenn man eine Menge erstellt und die Elemente da reinzieht und danach versteht dass ein Element falsch in die Menge reingezogen ist, nimmt man das Element raus und zieht das in eine andere Menge rein. Das Problem ist, dass das Element nicht aus der vorherigen Menge gelöscht wird sondern dort erhalten bleibt und es wird irgendwie dupliziert. Passt ihr darauf auf, wenn ihr ein Element rausnehmen wollt, soll die Menge einmal gelöscht und wieder erzeugt werden, dass die in die Menge reingezogenen Elemente gelöscht werden. Wenn man das nicht so tut, löst man die Aufgabe z.B. richtig aber danach wird gezeigt, dass die Lösung falsch ist, weil ein element gleichzeitig in zwei Mengen liegt. Das unten stehende Bild zeigt den Bug.

Grüße
Dateianhänge
Bildschirmfoto 2015-07-14 um 02.45.45.PNG
Bildschirmfoto 2015-07-14 um 02.45.45.PNG (61.37 KiB) 641 mal betrachtet

Nullmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 139
Registriert: 21. Apr 2015 20:59

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von Nullmann »

Danke für den Hinweis! Für die Foo-Programmierer ist wahrscheinlich noch der Seed interessant.

Ich für meinen Teil habe anzumeckern, dass die Löschfunktion bei mir überhaupt nicht funktioniert. Weder löscht diese Mengen, noch löscht sie Knoten aus einer Menge, wenn welche enthalten sind. Auch, wenn das kein kritischer Bug ist, da leere Mengen zum Glück ignoriert werden.
Das hinzufügen klappt gut, ist aber teilweise bei der Drag-Funktion etwas frickelig. Da hat das bei den Hashfunktionen z.B. um einiges besser geklappt, mit den Umrandungen.

Ganz komfortabel wäre es natürlich, wenn es noch eine Funktion geben würde wie "verteile alle restlichen Knoten auf einzelne Mengen". Bei einem (relativ) kleinem Bildschirm und z.B. 8 Mengen, muss man beim Drag 'n Drop während des Draggens ziemlich lange nach unten scrollen.
Könnte man zudem zusätzlich auch die Knoten grün zeichnen, wenn diese verbunden sind? Manchmal sind die Kanten ziemlich schwer zu erkennen (siehe Bild).

Zudem verstehe ich inhaltlich nicht ganz, wieso man eine Kantenreihenfolge vorgegeben bekommen hat? Normalerweise sortiert man ja diese aufsteigend nach Kantengewichten und geht diese Kanten dann durch (Oder, wie im Video, man subtrahiert mit dem größten Kantengewicht und sortiert dann absteigend. Wobei mir da weder erschliesßt, wieso man das macht und wieso man explizit die 13 benutzt, obwohl 12 das größte Kantengewicht ist).
Habe ich da einen Denkfehler oder wieso wurde das so umgesetzt?
Für uns ist diese Variante natürlich die Einfachere, da man nicht selbst schauen muss, welche Kante als nächstes genommen werden muss.
Dateianhänge
kruskal kanten.png
kruskal kanten.png (5.58 KiB) 596 mal betrachtet
Zuletzt geändert von Nullmann am 14. Jul 2015 11:07, insgesamt 2-mal geändert.

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von Alexj1988 »

sch3rvv1n hat geschrieben:Hallo,
Ich habe einen Bug gefunden. Wenn man eine Menge erstellt und die Elemente da reinzieht und danach versteht dass ein Element falsch in die Menge reingezogen ist, nimmt man das Element raus und zieht das in eine andere Menge rein. Das Problem ist, dass das Element nicht aus der vorherigen Menge gelöscht wird sondern dort erhalten bleibt und es wird irgendwie dupliziert. Passt ihr darauf auf, wenn ihr ein Element rausnehmen wollt, soll die Menge einmal gelöscht und wieder erzeugt werden, dass die in die Menge reingezogenen Elemente gelöscht werden. Wenn man das nicht so tut, löst man die Aufgabe z.B. richtig aber danach wird gezeigt, dass die Lösung falsch ist, weil ein element gleichzeitig in zwei Mengen liegt. Das unten stehende Bild zeigt den Bug.

Grüße
Wurde Aufgenommen, Danke für den Hinweis

mfg Alex

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von Alexj1988 »

Nullmann hat geschrieben:Zudem verstehe ich inhaltlich nicht ganz, wieso man eine Kantenreihenfolge vorgegeben bekommen hat?
Bei gleichen Kantengewichten müssten die Benutzer dann noch nach zusammengesetzten Namen sortieren, wobei beim zusammen setzten der Namen dadrauf geachtet wird, das der chronologisch führende name zuerst kommt.

Bsp: Kante (c, a, 7) , (b, a, 7) wird zu (ac, 7) , (ab,7) und dannach müsste des sortiert werden was zu folgendem führt: (ab,7) , (ac, 7)

Der knackpunkt der Aufgabe soll aber auf dem eigentlichen Algo liegen und nicht auf dem Sortierproblem; dafür gibt es andere Aufgaben. Daher wird die Sequenz zur Vereinfachung mit Angegeben.


mfg Alex

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von headhumper »

Alexj1988 hat geschrieben:Der knackpunkt der Aufgabe soll aber auf dem eigentlichen Algo liegen
Gilt das für alle Aufgaben :?:

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von Alexj1988 »

headhumper hat geschrieben:
Alexj1988 hat geschrieben:Der knackpunkt der Aufgabe soll aber auf dem eigentlichen Algo liegen
Gilt das für alle Aufgaben :?:
Bei den Algorithmen, die zu rechenintensiv sind, eher auf invariante des Algos.

mfg Alex

blmo
Neuling
Neuling
Beiträge: 2
Registriert: 15. Jul 2015 19:34

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von blmo »

Bei mir werden die Mengen bei der Abgabe des öfteren nicht richtig erkannt/zusammen gemischt. Nach einem ganzen Haufen verzweifelter Fehlversuche, hab ich angefangen Screenshots vor der Abgabe zu machen. Besonders gerne werden ein-elementige Mengen in eine der mehr-elementigen Mengen gemischt.
_1.png
_1.png (17.15 KiB) 421 mal betrachtet
bb.png
bb.png (37.53 KiB) 420 mal betrachtet
Seed: d0970714757783e6cf17b26fb8e2298f

Alexj1988
Mausschubser
Mausschubser
Beiträge: 69
Registriert: 23. Sep 2011 00:28

Re: Wichtig::BUG KRUSKAL ALGORITHM

Beitrag von Alexj1988 »

blmo hat geschrieben:Bei mir werden die Mengen bei der Abgabe des öfteren nicht richtig erkannt/zusammen gemischt. Nach einem ganzen Haufen verzweifelter Fehlversuche, hab ich angefangen Screenshots vor der Abgabe zu machen. Besonders gerne werden ein-elementige Mengen in eine der mehr-elementigen Mengen gemischt.
_1.png
bb.png
Seed: d0970714757783e6cf17b26fb8e2298f
Das passiert atm, wenn Elemente von einer Menge in die andere verschoben werden, dabei eine Einzelmenge gelöscht wird etc.

Thomas ist schon an der Sache dran.

Danke für den Hinweis.

mfg Alex

Antworten

Zurück zu „Archiv“