19 Wunderbare Welt der Algorithmen

19 Wunderbare Welt der Algorithmen

Disclaimer: Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an grafdan@ethz.ch.

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich hier.

Einführung

Bisher haben wir grundlegende Algorithmen gesehen wie Sortieren, Suchen oder die Berechnung des Medians. Ausserdem haben wir grundlegende Datenstruckturen gesehen: Heaps, AVL-Bäume, Fibonacci-Heaps, usw. Zudem haben wir Entwurfsideen gesehen. Hauptsächlich Induktion, aber auch Varianten davon wie das dynamische Programmieren und Divide & Conquer.

Wir wollen heute diese vielen kleinen Algorithmen und Ideen, die wir schon gesehen haben, etwas in den grösseren Kontext einordnen. Wir begeben uns also auf eine Reise in die "Wunderbare Welt der Algorithmen".

Die Probleme, die wir schon angeschaut haben, haben gemeinsam, dass sie schöne, schnelle Lösung erlauben, namentlich Lösungen, die in Polynomzeit laufen. Die Menge all dieser in Polynomzeit lösbarer Probleme nennen wir $P$ .

$P$ ist eingebettet in der Problemklasse $N P$ , die Menge der Probleme, deren Lösungen in Polynomzeit verifizierbar sind. Kennen wir ein Problem, bei dem es einfach ist eine Lösung zu verifizieren aber nicht unbedingt eine solche Lösung zu finden? Die Entscheidungsvariante des Traveling Salesman Problem (TSP) ist so ein Problem. Die Frage "Gibt es eine Rundreise der Länge höchstens 230?" ist nicht leicht zu beantworten. Aber wenn wir eine Rundreise bekommen, können wir leicht überprüfen, ob sie alle Knoten besucht und ihre Länge 230 nicht überschreitet. Das $N$ in $N P$ steht für nicht-deterministisch. Wir können $N P$ auch verstehen als alle Probleme, die sich mit einer Programminstruktion entweder-oder lösen lassen. Mit einer entweder-oder-Instruktion kann das Programm die beste aus mehreren Möglichkeiten auswählen, wobei die Instruktion an sich weiss was beste heisst. So eine Instruktion lässt sich in der Realität natürlich nicht realisieren, aber sie gibt uns ein starkes Konzept, das uns erlaubt schwierige Problem rasch zu lösen. Das Rucksackproblem ist so eines. Mit entweder-oder-Instruktionen können wir ganz rasch die beste Teilmenge der Gegenstände für den Rucksack auswählen. Somt ist das Rucksackproblem in $N P$ .

Die grösste Menge aller Probleme enthält auch alle unlösbaren Probleme. Ein Beispiel für ein solches nicht entscheidbares Problem ist das Halteproblem: Terminiert ein gegebenes Programm?^[1]

Heute wollen wir sehen, dass das algorithmische Denken

Online Algorithmen

Wir haben uns schon mit online Algorithmen beschaftigt, z.B. 'Move-To-Front'. Wir wollen heute uns 'streaming', 'verteilen' und 'Approximation' beschäftigen. Wir stellen uns eine Zaun und eine Kuh (Q) vor, wobei die Kuh weiss, dass es ein Loch (b) in dem Zaun gibt. Was wird die Kuh in dieser Situation tun? Die optimale Lösung wäre direkt zu diesem Loch zu gehen, aber die Kuh weiss nicht wo das Loch ist, deshalb kann sie nicht direkt zum Loch gehen.

Wir ueberlegen uns, dass wir zuerst 50 Schritten nach links gehen und nacher von der Mitte her 50 Schritten nach rechts. Dann gehen wir wieder von derMitte her 52 Schritten nach links. Wir wir in der amortieserter Analyse gelernt haben, dass nur um 2 neuen Schritten zu entwickeln und dafuer 50 Schritten wieder opfern macht kein Sinn, weil es die Effizienz der Algorithmus stoert.

Die effiziente Algorithmus wird naturlich 50 Schritten nach links , dann 100 Schritten nach rechts usw.

<----d-->
------------------------
b
		Q

2(1+2+4+…+2(d-1))+d < 9d

wobei wir eine konstante competitieve Ratio gefunden haben. Diese konstante Faktor erlaubt uns die Schatzung zu machen, dass diese online Algorithmus konstant ???

CNN-Car

Wir haben ein Strassennetz wo an Kreuzungen Umfälle geschehen. Die CNN hat ein Auto und will von der aktuellen Position möglichst schnell den nächsten Umfall "sehen". Die CNN will dabei nicht unbedingt am Unfallort sein, es reicht wenn sie den Unfall entlang einer geraden Linie sieht.

Dieses Problem ist mit einer konstanten competitive ratio lösbar. Wenn wir dieses Problem offline losen wollen, dann wiessen auch die Sequence der Unfallen, aber wenn wir das Online losen wollen, dann wird es sicher schwieriger , weill wir nur wisssen wo die naechste Unfall passiert ist und wir wollen natuerlich dafuer eine optimale Losung bzw. eine Algorithmus finden.

Streaming Algorithmen

Wir werden überflutet von eine Folge von Zahlen. Die Zahlen kommen so schnell, dass wir uns nicht alle merken können. Wir wollen lediglich ein Element finden, das mehr als die Hälfte aller Male vorkommt. Gibt es also eine Mehrheit im Zahlenstrom, so wollen wir dieses Mehrheitselement finden. Gibt es keine Mehrheit im Zahlenstrom, dann dürfen wir irgendwas ausgeben.

Wir merken uns zwei Dinge: ein Element und eine Anzahl.
Das Element repräsentiert den aktuellen Kandidaten und der Zähler zeigt wie sicher wir uns damit (noch) sind. Sehen wir den Kandidaten erneut, so erhöhen wir den Zähler. Kommt eine andere Zahl im Strom, so setzen wir den Zähler herab. Erreicht der Zähler null, so nehmen wir die neue Zahl als neuen Kandidaten. Am Ende des Datenstroms geben wir den aktuellen Kandidaten aus.

Warum funktioniert das? Nehmen wir ein Paar von Zahlen (Kandidate, nicht Kandidat) aus der Eingabe weg, so ändert die Mehrheit nicht und genau das macht der Zähler.

Verteilte Algorithmen

Spannbaum

Wir stellen uns einen Graphen von Rechnern vor, wobei die Knoten die Rechner sind und die Kanten die Kommunikationskanäle zwischen den Rechnern. Wie können sich diese verteilten Rechner auf einen gemeinsamen Spannbaum einigen?

In diesem Modell können wir nicht leicht einen der Spannbaumalgorithmen, die wir schon kennen, laufen lassen. Jeder Knoten hat nur Zugriff auf seine Nachbarn, es gibt also keine zentrale Instanz, die alles koordinieren kann. Wir nehmen aber an, dass es einen speziellen Startknoten gibt, auf den sich die Rechner geeinigt haben.

Nun funktioniert folgender Algorithmus: Der Startknoten fragt seine Nachbarn: "Bist du mein Nachbar im Spannbaum?" Jeder gefragte Knoten antwortet genau dann mit Ja, wenn er noch nie gefragt wurde. Ab dann sagt dieser Knoten Nein auf alle weiteren anfragen und beginnt auch selber seine Nachbarn abzufragen. Sobald also einige Knoten Ja sagten, wird an mehreren Orten im Graphen gleichzeitig rumgefragt und der Spannbaum breitet sich wellenartig durch den Graphen aus. Dadurch dass jeder Knoten nur einmal Ja sagt, stellen wir sicher, dass der entstehende Spannbaum keine Zyklen enthält. Da jeder Knoten ausser dem Startknoten genau einmal Ja sagt, wählen wir insgesamt $n - 1$ Kanten und erhalten somit einen Spannbaum. Dieser Algorithmus ist bekannt als Chang's Echo.

Zwei Generäle

Siehe Two Generals Problem (Wikipedia)
Die Beiden Generäle wollen gleichzeitig angreifen, d.h sie müssen den Angriff irgendwie koordinieren.

G_1		G_2
    \		/
	F

Sie können sich aber nie sicher sein, dass sie Beide am selben Zeitpunkt angreifen, denn die letzte Nachricht könnte immer korrupt sein.

Approximationsalgorithmen für TSP

Wir suchen Algorithmen für schwere Probleme, die in Polynomialzeit laufen und möglichst gute Näherungen für die Probleme liefern.

Erinnern wir uns an TSP: Gegeben ein vollständiger Graph $G = (V, E) = (V, (\binom{V}{2}))$ mit Kantenkosten $c : E \to R^{+}$
Gesucht ist eine Rundreise $v_{1}, v_{2}, \dots, v_{n}$ sodass $\sum_{i = 1}^{n - 1} c (v_{i}, v_{i + 1}) + c (v_{n}, v_{1})$ minimal ist.

Im Allgemeinen kennt man keine guten Approximationsalgorithmen für TSP. Im speziellen Fall, bei dem die Kostenfunktion $c$ die Dreiecksungleichung erfüllt, also $c (u, v) \leq c (u, t) + c (t, v)$ . Dieses metrische TSP (oder auch $△$ TSP genannt) erlaubt nun eine approximative Lösung.

Erste Idee: Greedy
Wir fangen an einem beliebigen Knoten an. In jedem Schritt nehmen wir die billigste Kante, die zu einem noch nicht besuchten Knoten führt. Übungsaufgabe: Zeigen Sie, dass diese Strategie katastrophal schlecht sein kann, d.h., dass die Greedy-Lösung im Vergleich zum Optimum um einen beliebigen Faktor teurer sein kann.

Zweite Idee: Spannbaum
Wir suchen den minimalen Spannbaum im Graphen. Der Minimale Spannbaum ist noch keine Rundreise, aber fast.
Wir verdoppeln die Kanten, sodass wir im Stil einer Tiefensuche jeden Knoten besuchen und dabei jede Kante genau einmal benützen. Dabei besuchen wir aber möglicherweise denselben Knoten mehrfach, was wir in einer TSP-Rundreise nicht dürfen. In solchen Fällen wählen wir statt Mehrfachbesuchen einfach die Abkürzung direkt zum nächsten Knoten, den wir noch nicht besucht haben. Die Dreiecksungleichung garantiert uns nun, dass dieses Abkürzen auch effektiv nicht mehr kostet. Also zusammengefasst:

verdoppple MST-Kanten
Reise mit Abkürzungen

Beim genauen Betrachten sehen wir, dass wir keinen Graphen sondern einen Multigraphen erzeugt haben, aber für den Moment ist das kein Problem. Es stellt sich die Frage, wann wir in einem Multigraphen eine Rundreise finden können, die jede Kante genau einmal benutzt. Das ist eines der ältesten Probleme der Graphentheorie und geht zurück auf Leonhard Euler, der einen Spaziergang über alle sieben Brücken in Königsberg machen wollte:

Euler zeigt, dass ein solcher sogenannter Eulerkreis genau dann exisitert wenn, wenn der Grad von allen Knoten gerade ist.

Algorithmus von Hierholzer für Eulerkreise

Wie konstruieren wir einen Eulerkreis in einem Euler-Graphen?
Wir starten irgendwo und laufen durch den Graphen bis wir wieder am Ausgangsort enden (Wir können nirgends sonst stecken bleiben, think about it!). Mit diesem beliebigen Kreis haben wir noch nicht zwingend alle Kanten gefunden. Haben wir noch unbesuchte Kanten, so können wir unseren bisherigen Kreis irgendwo aufbrechen, wo noch unbesuchte Kanten liegen, und dort nach dem selben Prinzip einen weiteren Kreis finden und einbauen. Dieses Vereinigen von kantendisjunkten Zyklen zu einer Eulertour lässt sich effizient implementieren, in Zeit linear zur Graphgrösse.

Zurück zur TSP-Approximation:

Approximationsgüte Wie gut funktioniert das Verdoppeln des minimalen Spannbaumes? Löschen wir aus der optimalen TSP-Rundreise eine beliebige Kante raus, so erhalten wir einen Spannbaum. Also gilt:
$M S T \leq o p t T S P$

Daher folgt für unsere Approximationslösung
$Aproximierte Losung \leq 2 \cdot M S T \leq 2 \cdot o p T S P$

Algorithmus von Christofides

Was wir mit der Verdoppelung erreichen wollten war ein Euler-Graph. Können wir das auch anders und billiger erreichen?

Beim Spannbaum haben wir Blätter mit Grad eins, d.h ein MST kann kein Euler-Graph sein. Die Knoten mit ungeradem Grad sind die "Problemknoten". Es Gibt immer eine gerade Anzahl Knoten mit ungeradem Grad. Wir bilden nun paare von solchen Knoten. Jetzt haben alle Knoten geraden Grad, das heisst es ist ein Euler-Graph.
Die Güte dieses Algorithmus hängt natürlich davon ab, wie teure Kanten ich für die Paarbildung nehme. Das ist ein minimum cost perfect matching. Eine Matching ist eine Teilmenge der Kanten so dass Paare gebildet werden. Keine zwei Kanten dürfen denselben Knoten beanspruchen. Ein perfect matching enthält alle Knoten.

$(u, w), (w, z) \in M ⟹ | {u, v, w, z} | = 4$

Ein perfektes matching lässt sich in polynomieller Zeit finden.

Wir machen hier minimum cost perfect mathing auf die Problemknoten. Jetzt waere die Frage natuerlich wir viel kostet dieses Schritt?

Wir wissen, dass unser opimalen Rundreise Algorithmus alle Knoten besuchen. Fur den Problem Knoten machen wir Abkuerzungen auf die Problemknoten, und dann schauen wie viel das kostet

$T S P_{p r o b l e m} \leq o p t T S P$

$mincostpM \leq \frac{1}{2} \cdot T S P_{p r o b l e m}$

TODO Skizze von alternierenden Matchings

Damit gilt: Christofides $\leq 1.5 \cdot o p t T S P$