Wie kann man nach negativen Kreisen überprüfen?
Also i) Wenn der Weg von v-t kürzer wird durch das hinzufügen von einer Kante mehr also n statt n -1, v … Dann gibt es einen Kreis W in diesem Kantenzug K. Dieser W hat dann auch negative Kosten.
ii Falls G ein negativen Kreis hat- dann gibt es eine Kante (u,v) sodass der Weg mit n-1 größer ist wie der Weg n-1 + diese Kante Cvu.
In welcher Laufzeit kann entschieden werden ob es einen negativen Kreis in einem Graphen gibt?
O(nm)
Jedoch kann dies Verbessert werden, indem nur in einem Array kürzester Pfad verwaltet wird der bisher gefunden wurde. Wenn nach einer Iteration kein neuer Eintrag- abbruch. Entsprechend ist Worst case O(nm) - aber in der Praxis schneller und die Speicherkapazität O(n+m)
Was gibt es über Approx von symmetrischen TSP zu sagen ?
Das symmetrische TSP ist nicht approximierbar.
Ausnahme - Metrisches TSP: Ein TSP heißt metrsich, wenn für die Distanzmatrix C die Dreiecksungleichung gilt . . . in summa summarum heißt das, dass sich zwischen Knoten keine Umwege auszahlen, sondern immer der direkte Weg optimal ist.
Auch das Euklidische TSP ist metrisch, da hierbei die Knoten Punkten in der euklidi- schen Ebene entsprechen und die Distanzen euklidische Distanzen sind.
Schließlich besitzt das metrische TSP eine Gütegarantie von 2.
Max ist ein …
Max ist ein liker und von 0 bis 1.
Welche Laufzeit hat der 2- Approximationsalgorithmus für Minimum Vertex Cover und wie geht er ..
Man nimmt eine beliebige Kante (u,v) e E und fügt es zum Cover hinzu. Dnach löscht man alle seine inzidenten Kanten also zu u und v.
Laufzeit ist O(n+m) mit einer Adjazenzliste.
Was ist der Approx Vertex Cover mit logarithmischer Gütegarantie ?
Einfach der bei dem man immer den größten Grad nimmt und dann entfernt .
Was ist die Laufzeit für die Spanning Tree Heuristik ?
Vorallem aufgrund des bestimmens des MST mit Laufzeit =(n^2)
Erkläre den Algo von Hierholzer und seine Laufzeit
O(n+m)
Wie funktioniert Lastverteilung Algo und wie ist die Laufzeit? Und Gütegarantie?
Erste Jobs auf die Maschinen Verteilen und danach dann einfach immer den nächsten Job der Maschine geben die die geringste Belastung/kürzeste Belastung hat. So soll die makespan klein gehalten werden.
Läuft in O(n log m)
Gütegarantie von 2
Wie funktioniert Center Selection? Was ist die Gütegarantie?
Wähle die k Mittelpunkte C so zu wählen, sodass die maximale Dinstanz von einem Standort zu einem nächsten Mittelpunkt minimal gehalten wird.
Also wiederhole k-1 mal,
wähle Standort mit maximaler Distanz (si,C)
Füge si zu C hinzu
Gütegarantie 2, besser geht es gar nicht falls P ungleich NP.
Fazit zu Heuristiken:
Intuitiv und schnell, aber meistens keine guten Lösungen. Und wenn doch, wie beim Insertion Hueristik von TSP - dann gibt es keine Garantie!
Merke: Durch Nachbarschaftsstrukturen können wir bestimmen welche Lösungen lokal optimal sind. (Wir suchen ja aber eigentlich nach globalen Optima) Also durch größer Nachbarschaftsstruktern, iterierte lokale Suchen oder Kombinationen können wir das versuchen.
Was ist das problem bei Random Neigbour und lokaler suche?
In der Norm wird die lokale Suche beendet, wenn man nichts mehr verbessern kann
- dadurch sehen wir, dass wir ein lokales Optimum erreicht haben.
Achtung: Bei zB Random Neighbor kann man das nicht immer gleich erkennen - al-
ternativ terminiert man auch nach einer bestimmten, festgelegten Iterationsanzahl
oder Zeit, oder auch wenn man schon eine Lösung hat, die gut genug ist.
Was ist die Laufzeit bei z.B. alternatier Nachbarschaft mit zwei löschen und eins Hinzufügen) ?
Bei einfacher wäre es nur das V ohne drei
Wie groß ist die Größte der Nachbarschaft 2-opt von TSP. Wie sieht es mit r-opt erweitung aus?
0(n^2) für eine Iteration. Im Worst case aber für ein lokales Optimum O(n!)
Bei r-opt Nachbarschaft ist es 0(n^r) wobei ab 4-opt schon nicht mal mehr praktikabel ist.
Was ist die Flip Nachbarschaft ?
Beim Max-Cut-Problem geht es darum, die Knoten eines ungerichteten Graphen in zwei Gruppen (eine Partition) aufzuteilen, sodass möglichst viele Kanten zwischen den beiden Gruppen verlaufen – also durch den sogenannten „Cut“ geschnitten werden. Eine gängige Heuristik zur Lösung dieses Problems basiert auf einer lokalen Verbesserung: Man beginnt mit einer gültigen Initiallösung, also einer beliebigen Aufteilung der Knoten in zwei Mengen. Anschließend wird iterativ geprüft, ob sich der Cut vergrößert, wenn man einzelne Knoten von einer Seite der Partition auf die andere verschiebt. Ist das der Fall, wird die Verschiebung durchgeführt, bis keine weitere Verbesserung mehr möglich ist und ein lokales Optimum erreicht wurde. Diese Methode garantiert eine Approximationsgüte von 1/2, das heißt, der gefundene Cut ist mindestens halb so groß wie ein optimaler Max-Cut.
Welche Schrittfunktion wird im Allgemeinen bei SA gewählt? Und was ist besonders an SA?
Random Neighbour. Auch schlechtere Lösungen werden mit einer bestimmten Wahrscheinlichkeit akzeptiert. Geringfügig schlechtere Lösungen werden mit höhere Wahrschienlichkeit akzeptiert, als viel schlechtere- und das auch nur anfänglich. Die Wahrscheinlichkeit das schlechtere Lösungen genommen werden, konvergiert dann relativ rasch.
In einem Satz, was ist die Tabu Suche? Und welche Schrittfunktion?
Basiert auf einem Gedächtnis über den bisherigen Optimierungsverlauf, verbietet den wiederbesuch früherer Lösungen um Zyklen zu vermeiden. Best Improvement.
Wie wähle ich die Tabulisten-Länge
Zu kurz: Entstehen schnell Zyklen
Zu Lang: Kann man in Sackgassen kommen und ist Speicheraufwendig, verbietet zu viele Lösungen und beschränkt die Suche stark.
Was ist die Ractive Tabu Search
Adative Anpassung der Tabulisten-Länge.
Was ist das Aspirationskriterium
Überschreibt den Tabu Status einer potenitellen Lösung, wodurch man sie wieder wählen darf.
Was passiert bei zu niedrigem Selektionsdruck?
Zu niedrig, erhalten wir mehr oder weniger eine Zufallssuche.
Zu Hoch dann Verlust an Vielfalt und das Verhalten konvergiert sehr schnell zu einem lokalen optimum.
Zuletzt geändertvor 4 Tagen
