D120.de/forum

Ich habe diesen Thread erst jetzt zur Klausurvorbereitung entdeckt und möchte mich bei Sandra und den anderen dafür bedanken, Prof. Weihe davon überzeugt zu haben, die EGA-Vorlesung im letzten Winter doch zu halten. Ich habe Effiziente Graphenalgorithmen letztes Semester besucht und fand die Veranst...

Nein, eine optimale Lösung einer TSP-Instanz kann keinen Knoten (insbesondere nicht den Ausgangsknoten) mehr als einmal durchlaufen Zwar ist Ihre Aussage korrekt, aber m.E. irreführend: keine zulässige Lösung durchläuft irgendeinen Knoten mehr als einmal, weil das durch die Definition des TSP gener...

Danke für die Ausführungen. Ich fasse die Antwort auf meine (zugegebenermaßen schlecht formulierte) Frage zusammen: Nein, eine optimale Lösung einer TSP-Instanz kann keinen Knoten (insbesondere nicht den Ausgangsknoten) mehr als einmal durchlaufen, d.h. für keinen Knoten darf die Anzahl der ausgehen...

Meinem Verständnis nach darf man die Ebenen nicht auf die Abbildung auf Folie 334 beziehen, da dort die Schritte nicht rigoros ausgeführt, sondern teilweise übersprungen wurden. Genau genommen müsste die Grafik also wie folgt aufgebaut sein: gp(X,Y) |— gp(X,Y) :- P(X,Z),P(Z,Y) |— p(X,Z) | |— p(X,Z) ...

Folie 234: Summenindex muss j sein, nicht i.

tss hat geschrieben:(…) Anders ausgedrückt: Optimal wirds ohnehin, von daher muss die Bedingung gar nicht hinreichend sein, sie muss nur die unzulässigen Optima ausschließen.

Danke für die gute Erklärung!

Die Frage ist aber nicht, ob es mehrere optimale Lösungen geben darf, sondern ob innerhalb einer Rundreise ein Knoten mehrfach besucht werden darf. Bei euklidischer Metrik stellt sich dir Frage nicht, da eine Lösung bei der ein Knoten mehrfach besucht wird, nie optimal ist. … außer bei einigen path...

Auf Folie 257 ("Coupling the two…") wird die Behauptung aufgestellt, dass in einer optimalen Lösung die Kanten mit y[{v,w}]=1 genau die vereinigten Kanten der (t_1, t_i)-Pfade sind. Der Beweis auf der nächsten Folie zeigt aber – soweit ich das sehe – nur die eine Richtung (nämlich die, die genaugeno...

In unserer Lerngruppe haben wir diskutiert, ob die Lösung des TSP mehrere Rundtouren umfassen kann. Für das Standard-TSP in der Ebene (mit der euklidischen Distanz) haben wir uns schnell klargemacht, dass das wegen der Optimalität nicht geht (vgl. Savings-Algorithmus, der das ja ausnutzt). Für das v...

Auf Folie 147 ("More systematic procedure") wird – meinem Verständnis nach – Bezug genommen auf die Wahl des i_0 im letzten Schritt der vorhergehenden Folie. Während dort die Startzeit eines beliebigen Job aus der inclusion-minimalen Menge auf die Endzeit des Ressourcenengpasses hochgesetzt werden s...

Wie war nochmal die Projektion Bahnhof -> Hitting-Set? Soweit ich es verstanden habe, ist ein Zug die Menge der Bahnhöfe und somit Element von S. F ist dann die Menge aller Bahnhöfe. F' wäre somit die Menge der isolierten Bahnhöfe. Damit wird doch ein Hitting-Set-Problem draus, oder habe ich was üb...

Da ich dann n Phasen durchlaufe komme ich auf O(n^3m) bzw O(n^3) für den gesamten Algo. Ich sehe da auch gar keinen Widerspruch mehr seit du erwähnt hast das O(m) für das berechnen der Potentiale innerhalb der Schleife wegfällt. OK, dann hatte ich dich nicht richtig verstanden und wir sind uns eige...

Das macht jetzt wieder keinen Sinn finde ich. Was ist denn nun richtig und was nicht? Das sagst zu der gleichen Argumentation einmal ja und einmal nein. :( :? Falls es missverständlich war, hier noch mal der zweite Teil meines letzten Posts, anders formuliert: Bei dir ist ein n zu viel, deshalb kom...

Und andernfalls eine Komplexität von O(n^3m) weil ich throughput durchlauf O(m) … Mmmh… ja, das klingt einleuchtend. Anzahl throughput durchläufe O(n) Anzahl Blockierende Flüsse O(n) => O(n^2m) für den Blocking Flow Und das ganze dann noch mal die n Phasen ergibt O(n^3m) für den gesamten Algo? Nein...

Sandra hat geschrieben:Das Distanzlabel d(s)=0 ist doch reine Definitionssache, die natürlich schon in gewisser Weise auch sinnvoll ist.

Na ja, vor allem kann man bei d(s)=0 davon sprechen, dass die d(v) die Länge eines kürzesten Weges von s nach v beschreiben, und das ist ja schon recht praktisch…