Die Suche ergab 21 Treffer

von ymy
25. Aug 2008 16:22
Forum: Algorithmische Modellierung
Thema: Weitere Vorlesungen?
Antworten: 11
Zugriffe: 3144

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...
von ymy
22. Aug 2008 15:32
Forum: Algorithmische Modellierung
Thema: Mehrere Rundtouren als Lösung des TSP?
Antworten: 11
Zugriffe: 1669

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...
von ymy
22. Aug 2008 14:45
Forum: Algorithmische Modellierung
Thema: Mehrere Rundtouren als Lösung des TSP?
Antworten: 11
Zugriffe: 1669

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...
von ymy
22. Aug 2008 14:35
Forum: Algorithmische Modellierung
Thema: Unverständliche Ebenenzählung
Antworten: 1
Zugriffe: 448

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) ...
von ymy
21. Aug 2008 12:06
Forum: Algorithmische Modellierung
Thema: Fehler im Skript
Antworten: 2
Zugriffe: 547

Re: Fehler im Skript

Folie 234: Summenindex muss j sein, nicht i.
von ymy
21. Aug 2008 11:56
Forum: Algorithmische Modellierung
Thema: Steiner-Baum-Problem als ILP
Antworten: 3
Zugriffe: 865

Re: Steiner-Baum-Problem als ILP

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!
von ymy
20. Aug 2008 18:11
Forum: Algorithmische Modellierung
Thema: Mehrere Rundtouren als Lösung des TSP?
Antworten: 11
Zugriffe: 1669

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...
von ymy
19. Aug 2008 11:39
Forum: Algorithmische Modellierung
Thema: Steiner-Baum-Problem als ILP
Antworten: 3
Zugriffe: 865

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...
von ymy
19. Aug 2008 10:04
Forum: Algorithmische Modellierung
Thema: Mehrere Rundtouren als Lösung des TSP?
Antworten: 11
Zugriffe: 1669

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...
von ymy
19. Aug 2008 09:48
Forum: Algorithmische Modellierung
Thema: Resolving resource conflicts (Folie 147)
Antworten: 1
Zugriffe: 406

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...
von ymy
19. Aug 2008 09:35
Forum: Algorithmische Modellierung
Thema: Aufgabe 4.4 - Begriff "isolated"
Antworten: 4
Zugriffe: 974

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...
von ymy
2. Mär 2008 19:19
Forum: Effiziente Graphenalgorithmen
Thema: Komplexität 3 Inder Algo
Antworten: 10
Zugriffe: 877

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...
von ymy
2. Mär 2008 18:56
Forum: Effiziente Graphenalgorithmen
Thema: Komplexität 3 Inder Algo
Antworten: 10
Zugriffe: 877

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...
von ymy
2. Mär 2008 17:16
Forum: Effiziente Graphenalgorithmen
Thema: Komplexität 3 Inder Algo
Antworten: 10
Zugriffe: 877

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...
von ymy
2. Mär 2008 17:07
Forum: Effiziente Graphenalgorithmen
Thema: Detecting negative cycles
Antworten: 5
Zugriffe: 818

Re: Detecting negative cycles

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…

Zur erweiterten Suche