Was ist eine Zertifikat und was ist ein Zertifizierer?
Zertifikat: Eine Hilfsinformation oder Lösungsvorschlag, mit dem man eine Ja-Antwort auf ein Entscheidungsproblem beweisen kann. (z. B. eine Tour für TSP oder eine Belegung für SAT)
Zertifizierer: Ein Algorithmus, der in polynomieller Zeit prüft, ob das Zertifikat tatsächlich die Eingabe gültig löst.
Erkläre 3 SAT…
Ist als Eingabe eine aussagenlogisce Formel in 3KNF und die Frage ist ob die Formel erfüllbar ist, sodass diese 1 ergibt.
Besteht aus vielen Klauseln - mit jeweils 3 Literalen drin. Verbunden immer durch unds und in der Klausel sind die Literale mit oders verbunden.
Was bedeutet A ≤P B bei Reduktionen?
Problem A lässt sich in Polynomialzeit auf B reduzieren. Wenn B lösbar ist, ist auch A lösbar.
Was passiert, wenn ein NPC-Problem in P lösbar ist?
Dann gilt P = NP
Was ist ein Vertex Cover?
Eine Knotenmenge, die jede Kante eines Graphen mindestens einmal berührt.
Ein Vertex Cover eines Graphen G = (V, E) ist eine Menge S ⊆ V , sodass jede Kante des Graphen zu mindestens einem Knoten aus S inzident ist. Wir betrachten dann meistens: Gegeben sei ein Graph G = (V, E) und eine ganze Zahl k. Gibt es ein Vertex Cover S von G, sodass |S| ≤ k?
S ⊆ V bedeutet:
S ist eine Teilmenge von V → Jeder Knoten in S ist auch in V enthalten.
Was ist ein Independent Set?
Eine Knotenmenge ohne benachbarte Knoten.
Ein Independent Set eines Graphen G = (V, E) ist eine Teilmenge S ⊆ V , in der es keine zwei adjazenten Knoten gibt. In der Norm gilt dann die Problemstellung: Gegeben sei ein Graph G = (V, E) und eine ganze Zahl k. Gibt es ein Independent Set S von G, sodass |S| ≤ k? (k ist Teil des Inputs!)
Wie hängen Vertex Cover und Independent Set zusammen?
Sie sind Komplementärmengen zueinander.
Das ist dann gemäß dem Konversionslemma: Sei G = (V, E) ein Graph und S ⊆ V und V = V − S. S ist ein Independent Set von G genau dann, wenn C ein Vertex Cover von G ist. Aus einem Maximum Independent Set erhalten wir dann zum Beispiel ein Minimum Vertex Cover. In der folgenden Abbildung ist das Independent Set rot, das Vertex Cover ist schwarz
Also wichtig, aus dem maximum Independent Set bekommen wir ein minimum Vertex Cover und umgekehrt.
Was ist eine Clique in einem Graphen? Beschreibe das Clique Problem…
Eine Teilmenge von Knoten, bei der alle Knoten miteinander verbunden sind.
Das Cliquenproblem Eine Clique in einem ungerichteten Graphen G = (V, E) ist eine Teilmenge V ′ ⊆ V von Knoten, von denen je zwei Knoten durch eine Kante E verbunden sind. Mit anderen Worten ist jede Clique ein vollständiger Teilgraph von G. Die Größe ist die Anzahl der in ihr enthaltenen Knoten. Das Cliquenproblem ist das Optimierungsproblem, eine Clique maximaler Größe in einem Graphen zu bestimmen. Als Entscheidungsproblem formuliert fragen wir einfach, ob eine Clique gegebener Größe k im Graphen existiert. Die formale Definition lautet: CLIQUE = {⟨G, k⟩ : G ist ein Graph mit einer Clique der Größe k}. Dieses Problem ist ebenso NPC.
Was ist das SAT-Problem?
Gibt es eine Belegung von Variablen, sodass eine gegebene aussagenlogische Formel wahr wird?
Satisfiability (SAT) ist im Prinzip: Gegeben ist eine KNF-Formel ϕ. Gibt es eine Wahrheitsbelegung, die ϕ erfüllt? Davon gibt es einige Formen, wie etwa:
3-SAT: SAT, bei dem jede Klauseln genau 3 Literale enthält. • 3-CNF-SAT: Aussagenlogische Formel in konjunktiver Normalform, wobei eine Klausel genau 3 Literale enthält. • CIRCUIT-SAT: Das Erfüllbarkeitsproblem, nur eben für Schaltkreise. • MAX-SAT • MAX-3SAT . . . sind alle klarerweise NPC
Was ist ein Independent Set in einem Baum und warum is es einfacher als in allgemeinen Graphen?
Eine Menge von Knoten, in der keine zwei direkt verbunden sind. Weil Bäume keine Zyklen haben – das erlaubt lineare Algorithmen (z. B. via Postorder-Traversierung).
Traversierung mittels Postorder (erst Kinder, dann Eltern (links, rechts, wurzel)
Was ist ein Nicht-Blockierer?
Gegeben ist ein Graph G = (V, E) mit Kantengewichten (z. B. reale Zahlen). Ein Nicht-Blockierer ist eine Teilmenge von Kanten N ⊆ E, mit folgender Eigenschaft:
Für alle Knotenpaare u, v ∈ V existiert mindestens ein Pfad von u nach v, der keine einzige Kante aus N verwendet.
Mit anderen Worten: Wenn man alle Kanten in N löscht, bleibt der Graph immer noch zusammenhängend.
Beschreibe das Nicht-Blockierer Problem
Finde eine Teilmenge N ⊆ E mit maximalem Gesamtgewicht, sodass N ein Nicht-Blockierer ist.
Also:
Die entfernten Kanten (N) sollen möglichst wertvoll (teuer) sein
Aber: Der verbleibende Graph muss weiterhin zusammenhängend sein
Weil ein MST effizient in polynomieller Zeit berechnet werden kann (z. B. mit Kruskal oder Prim), kann man damit auch den maximalen Nicht-Blockierer effizient finden.
Was ist das Ziel beim Nicht-Blockierer-Problem?
Eine möglichst teure Teilmenge von Kanten finden, deren Entfernung den Graphen zusammenhängend lässt.
Beschreibe das HAM-Cycle Problem?
Gegeben sei ein ungerichteter Graph G. Existiert ein Kreis C in G, der alle Knoten von G genau einmal enthält? (Hamiltonkreisproblem mit gegebenem k) Ebenso NPC.
Beschreibe das Travelling Salesperson Problem und wie hängt es mit dem HAM-Cycle zusammen?
Man sucht eine Reihenfolge für den Besuch mehrerer Orte, sodass die gesamte Reisestrecke eiens Handlungsreisenden möglichst kurz ist (Minimierungsproblem). Außerdem muss der erste Ort gleich dem letzten Ort sein.
Man kann das Hamiltonkreisproblem auf das TSP reduzieren und somit zeigen, dass dies auch in NPC liegt. Es gilt also HAM − CY CLE ≤P T SP. Eine TSPInstanz besitzt also eine Tour (einer gewissen Länge) genau dann, wenn ein Graph G einen Hamiltonkreis besitzt.
Was ist besonders hinsichtlich P und NPC beim k-Color problem
Gegeben sei ein ungerichteter Graph G. Kann man die Knoten des Graphen mit k ≥ 3 Farben so einfärben, dass benachbarte Knoten nicht die gleiche Farbe haben? Wichtig: k-COLOR ist NPC für alle k ≥ 3, aber z.B. in P für k = 2(Stichwort bipartit)!
Beschreibe als Optimierungsproblem OPT-Color
Als Optimierungsproblem betrachten wir dies durch OPT-COLOR: Gegeben sei ein ungerichteter Graph G. Färbe die Knoten des Graphen mit einer minimalen Anzahl Farben so, dass benachbarte Knoten nicht die gleiche Farbe besitzen. Und das können wir für spezielle Fälle sogar lösen - das wären dann die Intervallgraphen. Hierbei stellen wir einen Graphen durch Intervalle dar, die sich nur überschneiden, falls die dazugehörigen Knoten indizent sind. Und so ist die halbe Arbeit schon erledigt, das Einfärben geht nun ganz leicht: All die Intervalle, die sich nicht überschneiden, können wir zu einer Ebene zusammenfassen - jede Ebene bekommt dann eine eigene Farbe
Hat die Reihenfolge der Teilproblemauswahl Einfluss auf die Korrektheit von Branch-and-Bound?
Nein. Die Korrektheit ist unabhängig von der Reihenfolge, nur die Effizienz kann sich ändern.
Muss ein Branch-and-Bound-Verfahren alle Teilprobleme betrachten, um die optimale Lösung zu finden?
Nein. Durch das Verwenden von Schranken können viele Teilprobleme ausgeschlossen (gepruned) werden.
Welche Rolle spielen die Heuristiken für obere (U′) und untere (L′) Schranken in Branch-and-Bound? Und was sind gute Schranken?
Können Best-First und Depth-First Strategien im Branch-and-Bound kombiniert werden?
Ja. Hybride Ansätze können die Vorteile beider Strategien vereinen.
Wann kann ein Teilproblem in einem Minimierungsproblem verworfen werden?
Wenn seine lokale untere Schranke L′L′L′ größer als die globale obere Schranke UUU ist.
Ist Branch-and-Bound immer effizienter als Brute-Force?
Nein. Im Worst-Case kann Branch-and-Bound genauso lange dauern wie vollständige Enumeration.
Wie ist die Worst-Case-Laufzeit von Branch-and-Bound mit max. 3 Verzweigungen pro Knoten und Tiefe n?
O(3ⁿ) – exponentiell, da jeder Knoten 3 neue erzeugen kann.
Wenn jedes Teilproblem 3 neue erzeugt und die Tiefe nnn beträgt, ist die Worst-Case-Laufzeit O(2ⁿ)?✅ Nein, sie ist O(3ⁿ) – exponentiell mit Basis der Verzweigungsrate.
Gilt: Ein NP-vollständiges Problem ist genau dann in Polynomialzeit lösbar, wenn P = NP?
Ja, das stimmt.
Erklärung: Ein Problem ist NP-vollständig, wenn:
Es in NP liegt (Lösungen können in Polynomialzeit überprüft werden), und
alle anderen Probleme in NP sich in Polynomialzeit auf dieses Problem reduzieren lassen.
Wenn also ein NP-vollständiges Problem in Polynomialzeit lösbar ist, dann wären alle Probleme in NP auch in P, also gilt P = NP. Umgekehrt: Wenn P = NP, sind natürlich auch alle NP-vollständigen Probleme in P lösbar.
Wird ein Problem B NP-schwer, wenn man es in Polynomialzeit auf ein NP-schweres Problem A reduziert?
Nein, das ist falsch.
Erklärung: Die Reduktionsrichtung ist entscheidend: Nur wenn man ein NP-schweres Problem auf B reduziert (A ≤P B), kann man sagen, dass B ebenfalls NP-schwer ist.
Die Aussage in der Frage dreht das um: B ≤P A (also B auf A) sagt nichts über die Schwierigkeit von B aus. Man kann triviale Probleme auf schwere reduzieren, ohne dass sie dadurch schwer werden.
👉 Richtige Richtung: Von schwer auf zu untersuchendes Problem.
Wenn SAT in Linearzeit gelöst werden kann, sind dann alle NP-vollständigen Probleme in Polynomialzeit lösbar?
Ja, das ist korrekt.
Erklärung: SAT ist ein NP-vollständiges Problem. Wenn SAT in Linearzeit lösbar wäre, dann wäre es in P ⇒ also P = NP.
Da alle NP-vollständigen Probleme sich in Polynomialzeit auf SAT reduzieren lassen, wären dann auch alle anderen NP-vollständigen Probleme polynomiell lösbar.
Was ist die Idee bzw. das Prinzip der Lokalen Suche?
Die lokale Suche beginnt mit einer gültigen (meist zufälligen oder heuristisch erzeugten) Lösung und verbessert diese schrittweise, indem sie Nachbarlösungen betrachtet und bei Verbesserung zu diesen übergeht.
Das Ziel ist, durch kleine lokale Änderungen eine möglichst gute (nicht unbedingt optimale) Lösung zu finden.
Was ist ein Unterschied zwischen heuristischen Verfahren und Approximationsalgorithmen?
Ein Approximationsalgorithmus gibt eine Lösung mit garantierter Güte im Vergleich zur optimalen Lösung — z. B. „höchstens doppelt so schlecht“.
Ein heuristisches Verfahren dagegen liefert zwar oft gute Lösungen, aber ohne Garantie, wie nah diese am Optimum sind.
Zusammengefasst:
Approximationsalgorithmen → lösungsqualität ist theoretisch abgesichert
Heuristiken → keine Garantie, aber oft praktisch gut
Aussage
Richtig?
Grund
1. Globale untere Schranke > lokale obere Schranke
✅
Teilproblem chancenlos
2. Lokale untere Schranke > globale untere Schranke
❌
klingt vielversprechend!
3. Lokale obere = lokale untere Schranke
keine Verzweigung mehr nötig
4. Lokale untere < globale untere Schranke
könnte immer noch gut sein
❌ Falsch
Begründung:
Allgemeine Graphen können Zyklen enthalten → das Problem ist dort NP-vollständig.
Nur weil es auf Bäumen geht, heißt das nicht, dass es auf allen Graphen geht.
Kein Rückschluss möglich von „leichtem Spezialfall“ auf „allgemeinen schweren Fall“.
✅ Richtiges Kreuz: Falsch
✅ Wahr
Ungewichtetes VC ist ein Spezialfall des gewichteten (alle Gewichte = 1).
Wenn der allgemeine Fall effizient lösbar ist, ist es der Spezialfall auch.
Tatsächlich ist ungewichtetes VC auf Bäumen sogar in linearer Zeit lösbar (per Matching oder dynamische Programmierung).
✅ Richtiges Kreuz: Wahr
Ein Pfad ist ein spezialfall eines Baumes (ein sehr einfacher Baum).
Die Lösung für Bäume gilt insbesondere auch für Pfade.
Pfade = Spezialfall ⇒ Problem bleibt lösbar, evtl. sogar noch effizienter.
Ein Binärbaum ist ebenfalls ein spezialfall eines Baumes.
Alles, was für Bäume allgemein gilt, gilt auch für Binärbäume.
Kein Widerspruch zur ursprünglichen Annahme → ganz klar korrekt.
Nr.
Wahr/Falsch
Kreuz
(i)
Jeder Intervallgraph ist 3-färbbar
✅ Falsch
(ii)
Reduktion 3-COLOR → 5-COLOR
(iii)
3-COLOR in NP für Intervallgraphen
(iv)
2-COLOR NP-vollständig auf Intervallgraphen
(v)
Jeder Baum ist 3-färbbar
Erklärung: Ein Intervallgraph ist perfekt, das heißt: → Chromatische Zahl = Größe der größten Clique
Ein Intervallgraph mit einer Clique von 4 braucht also auch 4 Farben → nicht immer 3-färbbar!
Erklärung: Man kann 3-COLOR auf 5-COLOR reduzieren – man fragt: „Wenn ich 3-färben kann, kann ich auch 5-färben.“ Und: Man kann testen, ob ein Graph, der 3-färbbar ist, auch mit 5 Farben färbbar ist – trivialerweise ja.
Die Frage ist: Gibt es eine Reduktion von 3-COLOR → 5-COLOR → Ja, z. B. durch Identitätsabbildung (Graph unverändert weiterreichen). → Jede Instanz von 3-COLOR ist auch Instanz von 5-COLOR
Erklärung: Alle Graphfärbungsprobleme mit konstanter Farbanzahl liegen in NP, weil man eine Färbung einfach als Zertifikat in polynomialer Zeit überprüfen kann.
Erklärung:
2-COLOR = Bipartitheitstest
Für allgemeine Graphen ist 2-COLOR in P
Für Intervallgraphen auch – sogar trivialer
→ Niemals NP-vollständig!
Erklärung: Stimmt – aber sogar stärker: → Jeder Baum ist 2-färbbar → Also natürlich auch 3-färbbar
Gegeben ein Graph GGG: Kann man ihn mit kkk Farben färben, sodass keine benachbarten Knoten die gleiche Farbe haben? Gebe eine Komplexitätsüberblick!
k
Problem
Komplexität
2-COLOR
Test auf Bipartitheit
in P (einfach!)
3-COLOR
NP-vollständig
schwer
4-, 5-, …-COLOR
ebenfalls NP-vollständig
auch schwer
Laufzeit
Gültig?
Begründung
O(n)
Wenn G≫nG \gg n, reicht das nicht mehr
O(G)
Wenn n≫Gn \gg G, reicht das nicht
O(min{n, G})
Untergrenze, keine sichere Obergrenze
O(n · G)
✅ (aber zu grob)
Gültige Schranke, aber nicht eng
O(n + G)
Tight bound für die Backtracking-Laufzeit
Kann ein Approximationsalgorithmus mit Gütegarantie 2 eine Lösung zurückgeben, die nur 2 % über dem Optimalwert liegt?
Ja.
Erklärung: Die Garantie bedeutet nur:
Das schließt auch alle Lösungen ein, die weniger stark abweichen – also z. B. 1.02 × v∗v^*v∗. Solche Lösungen dürfen vorkommen.
Liefert ein Approximationsalgorithmus mit Gütegarantie 1 immer eine optimale Lösung?
Gilt bei Maximierungsproblemen mit Gütegarantie
Ja
Erklärung: Die Definition der Güte bei Maximierung lautet:
A≥α⋅v∗A \geq \alpha \cdot v^*A≥α⋅v∗
Typisch ist α∈(0,1]\alpha \in (0,1]α∈(0,1]. Das bedeutet: Der Algorithmus liefert mindestens diesen Anteil am Optimum.
Welche Gütegarantie hat die Spannbaumheuristik für das euklidische TSP?
Die MST-Heuristik für euklidisches (metrisches) TSP hat eine Gütegarantie von 2.
Wird Branch-and-Bound bei Maximierungsproblemen besser, je größer die lokalen oberen Schranken sind?
❌ Nein
Erklärung: Kleine lokale obere Schranken helfen beim frühen Abschneiden unnötiger Teilprobleme. Große Schranken halten unnötig Optionen offen.
Führt eine schlechte Auswahl der nächsten Teilinstanz dazu, dass keine optimale Lösung mehr gefunden wird?
Nein
Erklärung: Die Auswahlstrategie beeinflusst nur die Laufzeit, nicht die Korrektheit. Die optimale Lösung geht nicht verloren, solange der Algorithmus korrekt arbeitet.
Kann man bei einem Minimierungsproblem ein Teilproblem verwerfen, wenn die globale untere Schranke größer als die lokale obere ist?
Erklärung: Das bedeutet, dass die Teilinstanz keine bessere Lösung liefern kann als die bisher bekannte → sie wird zu Recht ausgeschlossen.
Wird Branch-and-Bound bei Minimierungsproblemen effizienter, je kleiner die lokalen unteren Schranken sind?
Erklärung: Kleine Schranken bedeuten: „Dieses Teilproblem sieht vielversprechend aus“ → muss weiterverfolgt werden. Große Schranken → eher abschneidbar → effizienter.
Hat die Reihenfolge der Teilproblemauswahl Einfluss auf die Korrektheit (Optimalität) der Lösung bei Branch-and-Bound?
Erklärung: Die Reihenfolge beeinflusst nur die Laufzeit, nicht ob die optimale Lösung gefunden wird. Die Lösung bleibt korrekt, solange korrekt abgeschnitten wird.
Wird beim Best-First-Verfahren im Maximierungsproblem das Teilproblem mit der kleinsten Differenz zwischen U′′ und L′ ausgewählt?
Erklärung: Best-First wählt typischerweise das Teilproblem mit dem vielversprechendsten Wert, also der höchsten oberen Schranke U′. Die Differenz U′−L′ spielt dabei keine Rolle.
Ist eine Lösung eines ½-Approximationsalgorithmus für ein Maximierungsproblem höchstens oder mindestens halb so gut wie optimal?
Mindestens
Die Lösung ist nicht schlechter als die Hälfte des optimalen Werts – sie kann besser sein, aber nicht schlechter.
Garantiert eine 1-flip-basierte lokale Suche für MAX-SAT bei P = NP in Polynomialzeit eine optimale Lösung, unabhängig vom Startpunkt?
Erklärung:Auch wenn P = NP, heißt das nicht, dass eine bestimmte lokale Heuristik (wie 1-flip-Suche) zuverlässig zur optimalen Lösung führt.Sie kann in lokalen Optima steckenbleiben. P = NP garantiert nur, dass ein Algorithmus existiert, nicht dass dieser es ist.
Findet man mit First Improvement immer ein lokales Optimum, wenn man lange genug sucht?
Ja, First Improvement führt immer zu einem lokalen Optimum,wenn man lange genug sucht,vorausgesetzt der Suchraum ist endlich und jede Verbesserung wird korrekt ausgeführt.
Ändert sich bei Intervallgraphen etwas daran dasss das 3 Color Problem NP Complete ist?
Das 3-Coloring-Problem ist im Allgemeinen NP-vollständig. Für Intervallgraphen jedoch ist es in P, da sie zu den perfekten Graphen gehören. Bei perfekten Graphen entspricht die Chromatische Zahl der Größe der größten Clique (χ(G)=ω(G)χ(G)=ω(G)). Da sich die maximale Clique bei Intervallgraphen in polynomieller Zeit bestimmen lässt, kann man effizient prüfen, ob ein Intervallgraph 3-färbbar ist. Das Problem liegt somit nicht nur in NP, sondern auch in P.
Ist ein Baum 3 Färbbar?
Ein Baum ist 3-färbbar, weil er 2-färbbar ist– und 2-Färbung ist die minimal nötige Komplexität in dem Fall.Deshalb sagt man mit Betonung: „sogar 2-färbbar“
Merke: 2-Coloring entspricht der Frage:➜ „Ist der Graph bipartit?“ Ist es in P oder NP?
Ist in P im gegensatz zu 3Color (was NPC ist) …
Denn: Bipartitheit kann man in polynomieller Zeit prüfen, z. B. mit:
Breitensuche (BFS): Farben abwechselnd zuweisen
Wenn ein Konflikt auftritt (zwei benachbarte Knoten hätten dieselbe Farbe), ist der Graph nicht bipartit
Was sind Abbruchkriterien für lokale Suche wenn ein lokales Optimum erreicht wurde?
Abbruch erfolgt:
nach einer bestimmten Iterationsanzahl oder Zeit.
wenn eine ausreichend gute Lösung gefunden wurde.
wenn keine weitere Verbesserung über eine bestimmte Anzahl letzter Iterationen
erreicht wurde.
Was ist die Laufzeitkomplexität der r-opt lokalen Suche?
Was ist das Metropolis Kriterium bei Simmulated Annealing?
Was macht es? Es entscheidet, ob man auch mal eine schlechtere Lösung annehmen darf.
Warum? Damit die Suche nicht in einem schlechten lokalen Optimum stecken bleibt.
Wie funktioniert’s?
Wenn die neue Lösung besser ist → nimm sie auf jeden Fall! ✅
Wenn sie schlechter ist → nimm sie vielleicht – mit einer gewissen Zufallswahrscheinlichkeit
Wovon hängt das ab?
Wie viel schlechter die neue Lösung ist
Wie heiß die Suche gerade ist (Temperatur):
Am Anfang (hohe Temperatur) → mehr Risiko, schlechte Schritte erlaubt
Am Ende (niedrige Temperatur) → fast nur noch Verbesserungen erlaubt
Ziel: 👉 Schlaues „Herumprobieren“, um globale statt nur lokale Lösungen zu finden.
Was ist die Grundlegende Idee von Simulated Annealing?
Auch schlechtere Nachbarl¨ osungen werden mit einer bestimmten
Wahrscheinlichkeit akzeptiert
Was sind im Allgemeinen Approximation(salgorithmen)?
Erzeuge in polynomieller Zeit eine N¨ aherungsl¨ osung, die
eine G¨ utegarantie besitzt. Die G¨ ute eines Algorithmus sagt etwas ¨ uber die F¨ ahigkeit
aus, optimale L¨ osungen gut oder schlecht anzun¨ ahern.
Beschreibe den 2 Approx Algo für minimales Vertex Cover Problem und seine Laufzeit
oder halt O(n+m)
Was gilt für den Approx-Vertext Cover Algo für vollstädnig bipartite Graphen?
Ist eine Travelings Salesman Problem minimirung oder maximierungsproblem und was ist es genau?
Traveling Salesman Problem (TSP)
Gegeben: Städte + Distanzen
Ziel: Kürzeste Rundreise durch alle Städte, jede genau 1× besuchen, am Ende zurück
✅ Minimierungsproblem
📦 NP-schwer
Varianten: symmetrisch, asymmetrisch, mit Dreiecksungleichung (metrisch)
Wie kann ich die NP schwere von einem Symmetrischen TSP beweisen ? Überlege was Zertifikat und Zertifizierer sein könnten.
Beweis: s-TSP ist NP-schwer
Reduktion von Hamiltonkreis-Problem (NP-vollständig)
Baue TSP-Instanz mit Kosten:
1 für existierende Kante
2 sonst
Tour mit Gesamtkosten = ∣V∣∣V∣ ⇔ Hamiltonkreis vorhanden
Daraus folgt:
s-TSP ist NP-schwers-TSP ist NP-schwer
——
Zertifikat: Eine Permutation der Knoten, die die Reihenfolge der Städte angibt (z. B. (v1,v2,v3,...,vn,v1)(v1,v2,v3,...,vn,v1))
Zertifizierer: Ein Algorithmus, der prüft, ob – die Tour jeden Knoten genau einmal besucht, – eine gültige Rundreise bildet, – und deren Gesamtkosten ≤ k sind. Die Überprüfung erfolgt durch einfaches Addieren der Kantengewichte entlang der Tour, in polynomieller Zeit.
Welche Eigenschaften müssen passende Zertifizierer erfüllen?
Polynomielle Laufzeit: Der Zertifizierer muss das gegebene Zertifikat in polynomieller Zeit (in Bezug auf die Eingabegröße) überprüfen können.
Überzeugbarkeit (Korrektheit für Ja-Instanzen): Für jede Ja-Instanz muss es mindestens ein Zertifikat geben, das der Zertifizierer akzeptiert.
Nicht-Austrickbarkeit (Korrektheit für Nein-Instanzen): Für keine Nein-Instanz darf es ein Zertifikat geben, das den Zertifizierer zum Akzeptieren bringt.
Was ist die spanning Tree Heuristik, beschreibe wie sie funktioniert und was man machen muss…
Verwende einen Minimalen Spannbaum (MST), um eine günstige Struktur zu finden, die alle Knoten verbindet, und baue daraus eine TSP-Tour.
Berechne einen minimalen Spannbaum (MST) des gegebenen Graphen → z. B. mit Kruskal oder Prim
Verdopple alle Kanten im MST, sodass jeder Knoten geraden Grad hat → Ergebnis ist ein Eulergraph
Finde eine Eulertour (ein geschlossener Weg, der jede Kante genau einmal benutzt)
Laufe die Eulertour ab, aber überspringe bereits besuchte Knoten → Das ergibt eine gültige TSP-Tour
✅ Das geht wegen der Dreiecksungleichung – direktes Überspringen ist nie teurer als über Umwege.
Der Graph muss symmetrisch sein und die Dreiecksungleichung erfüllen
Die Tour, die herauskommt, ist höchstens doppelt so lang wie die optimale TSP-Tour
MST berechnen: O(∣E∣log∣V∣)O(∣E∣log∣V∣)
Eulerkreis: O(∣E∣)O(∣E∣)
Tour ablaufen & abkürzen: O(∣V∣)O(∣V∣)
→ Insgesamt: polynomiell
Wann existiert eine Eulertour?
Eulertour: Eine Rundtour, die jede Kante des Graphen genau einmal beinhaltet.
Theorem: Eine Eulertour existiert in einem ungerichteten Graphen genau dann wenn er
zusammenh¨ angend ist und jeder Knoten einen geraden Grad hat.
Hinweis: Durch die Verdopplung der Kanten in ST hat jeder Knoten geraden Grad.
Eine Eulertour existiert somit immer.
Wann gilt die Gütegarantie ≤ 2 für das TSP und warum ist die Dreiecksungleichung dafür wichtig?
Die Gütegarantie ≤2≤2 gilt beim metrischen TSP, z. B. bei euklidischen Distanzen, wenn die Dreiecksungleichung erfüllt ist.
Die Spanning-Tree-Heuristik nutzt das Abkürzen von Wegen – das funktioniert nur dann korrekt, wenn gilt:
Dreiecksungleichung: c(i,k)≤c(i,j)+c(j,k)Dreiecksungleichung: c(i,k)≤c(i,j)+c(j,k)
→ Ohne diese Bedingung wäre das Abkürzen u. U. teurer, und die Gütegarantie verfällt.
Zuletzt geändertvor 13 Tagen
