Die Suche ergab 21 Treffer
- 25. Aug 2008 16:22
- Forum: Algorithmische Modellierung
- Thema: Weitere Vorlesungen?
- Antworten: 11
- Zugriffe: 3493
Re: Weitere Vorlesungen?
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...
- 22. Aug 2008 15:32
- Forum: Algorithmische Modellierung
- Thema: Mehrere Rundtouren als Lösung des TSP?
- Antworten: 11
- Zugriffe: 1883
Re: Mehrere Rundtouren als Lösung des TSP?
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...
- 22. Aug 2008 14:45
- Forum: Algorithmische Modellierung
- Thema: Mehrere Rundtouren als Lösung des TSP?
- Antworten: 11
- Zugriffe: 1883
Re: Mehrere Rundtouren als Lösung des TSP?
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...
- 22. Aug 2008 14:35
- Forum: Algorithmische Modellierung
- Thema: Unverständliche Ebenenzählung
- Antworten: 1
- Zugriffe: 508
Re: Unverständliche Ebenenzählung
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) ...
- 21. Aug 2008 12:06
- Forum: Algorithmische Modellierung
- Thema: Fehler im Skript
- Antworten: 2
- Zugriffe: 604
Re: Fehler im Skript
Folie 234: Summenindex muss j sein, nicht i.
- 21. Aug 2008 11:56
- Forum: Algorithmische Modellierung
- Thema: Steiner-Baum-Problem als ILP
- Antworten: 3
- Zugriffe: 952
Re: Steiner-Baum-Problem als ILP
Danke für die gute Erklärung!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.
- 20. Aug 2008 18:11
- Forum: Algorithmische Modellierung
- Thema: Mehrere Rundtouren als Lösung des TSP?
- Antworten: 11
- Zugriffe: 1883
Re: Mehrere Rundtouren als Lösung des TSP?
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...
- 19. Aug 2008 11:39
- Forum: Algorithmische Modellierung
- Thema: Steiner-Baum-Problem als ILP
- Antworten: 3
- Zugriffe: 952
Steiner-Baum-Problem als ILP
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...
- 19. Aug 2008 10:04
- Forum: Algorithmische Modellierung
- Thema: Mehrere Rundtouren als Lösung des TSP?
- Antworten: 11
- Zugriffe: 1883
Mehrere Rundtouren als Lösung des TSP?
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...
- 19. Aug 2008 09:48
- Forum: Algorithmische Modellierung
- Thema: Resolving resource conflicts (Folie 147)
- Antworten: 1
- Zugriffe: 463
Resolving resource conflicts (Folie 147)
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...
- 19. Aug 2008 09:35
- Forum: Algorithmische Modellierung
- Thema: Aufgabe 4.4 - Begriff "isolated"
- Antworten: 4
- Zugriffe: 1096
Re: Aufgabe 4.4 - Begriff "isolated"
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...
- 2. Mär 2008 19:19
- Forum: Effiziente Graphenalgorithmen
- Thema: Komplexität 3 Inder Algo
- Antworten: 10
- Zugriffe: 1036
Re: Komplexität 3 Inder Algo
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...
- 2. Mär 2008 18:56
- Forum: Effiziente Graphenalgorithmen
- Thema: Komplexität 3 Inder Algo
- Antworten: 10
- Zugriffe: 1036
Re: Komplexität 3 Inder Algo
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...
- 2. Mär 2008 17:16
- Forum: Effiziente Graphenalgorithmen
- Thema: Komplexität 3 Inder Algo
- Antworten: 10
- Zugriffe: 1036
Re: Komplexität 3 Inder Algo
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...
- 2. Mär 2008 17:07
- Forum: Effiziente Graphenalgorithmen
- Thema: Detecting negative cycles
- Antworten: 5
- Zugriffe: 961
Re: Detecting negative cycles
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…Sandra hat geschrieben:Das Distanzlabel d(s)=0 ist doch reine Definitionssache, die natürlich schon in gewisser Weise auch sinnvoll ist.