search

jensharder91 / -Lab-Efficient-Algorithms

0 stars 0 forks source link

Blatt 03 Aufgabe 8 #21

Open jensharder91 opened 6 years ago

jensharder91 commented 6 years ago

zur Aufgabe "Railway Network": Ich habe diese offenbar missverständlich/fehlerhaft formuliert. In der Aufgabenstellung heißt es: "What is the minimum travel time using a single railway connection that we can obtain?"

Gemeint ist dies in folgendem Sinne: Die maximale Länge einer single railway connection soll minimiert werden.

Man könnte es z.b. so formulieren: "What is the minimum travel time using an arbitrary (new established) single railway connection that we can obtain?"

jensharder91 commented 6 years ago

Idee: Triangulieren (planarer Graph) Dann MST auf den Dreiceckskanten.

Also eigentlich ganz normal MST, nur halt nicht auf dem kompletten vollständigen Graph, sondern nur auf ausgewählten Kanten.

Schwierigkeit: Triangulieren.. vllt hast du ne schöne Idee dazu?

jensharder91 commented 6 years ago

Habs wie besprochen implementiert... RUNTIME ERROR.. muss man nochmal schauen (Beispiel geht)

P4nd4b43r commented 6 years ago

ich habe eine Eingabe mir 500 Städten und 250 Verbindungen probiert. Die Antwort 30.000 erscheint mir irgendwie nicht richtig. Aber es lief fehlerfrei durch...

P4nd4b43r commented 6 years ago

Der Run-Error bei der Aufgabe RailwayNetworks lautet: Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:868) at java.util.TimSort.mergeAt(TimSort.java:485) at java.util.TimSort.mergeForceCollapse(TimSort.java:426) at java.util.TimSort.sort(TimSort.java:223) at java.util.TimSort.sort(TimSort.java:173) at java.util.Arrays.sort(Arrays.java:659) at java.util.Collections.sort(Collections.java:217) at sheet03.task_08_RailwayNetwork.RailwayNetwork.main(RailwayNetwork.java:58)