Combinatorial Problems Flashcards
Welche 2 Darstellungsarten für den Lösungsraum kennen Sie aus der Vorlesung?
Ungerichteter Graph mit Knoten als potentielle Lösungen und Kanten als Transitionen von einer Lösung zu einer benachbarten Lösung
Baum, bei dem die Wurzel das Initialproblem darstellt, die nachfolgenden Äste jeweils Teilprobleme bilden und die Blätter die Lösungen darstellen.
Zusammenhang zwischen Combinatorial Optimization Problems und NP-hard Problems erklären mit jeweils zwei Beispielen.
COP sind Problemstellen, wo mathematische Techniken zum Finden einer Optimallösung in einer endlichen Anzahl an Schritten angewendet werden. Der Lösungsraum ist zu groß für eine ausführliche Suche.
Oftmals sind COP auch NP-hard, da deterministische Algorithmen mehr als Polynomialzeit brauchen um eine optimale Lösung zu finden.
Beispiele für CP: Knapsack und TSP
Beispiele für NP-Hard: TSP und VRP
Wieviele Lösungen für ein asymmetrisches TSP gibt es?
Die Anzahl der Lösungen für symmetrische TSP sind ((n-1)FAKULTÄT)/2. Dies rührt aus n Knoten, die miteinander verbunden werden können, nach jedem Schritt ein Knoten weniger zur Verfügung steht und sich die Anzahl der zu untersuchenden Kanten aufgrund des symmetrischen Problems (also die Kanten haben in beide Richtungen das selbe Gewicht) halbiert.
Für asymmetrische TSP sind demnach (n-1)FAKULTÄT Lösungen vorhanden.
Die Komplexität eines MST bei der Berechnung über das Prim Verfahren
Die Komplexität eines MST bei der Berechnung über das Prim-Verfahren beträgt O(|V|²), wenn als Adjazenzmatrix (Nachbarschaftsmatrix) angegeben.
Selbes gilt für Kruskal.
Laut Internet O(E*log(V))
Was ist der Unterschied zwischen Problem Space Search und Solution Space Search? Mit Grafik!
The problem space search starts with our problem and decomposes it into subproblems (and eventually into possible solutions), whereas the solution space search lists all potential solutions from the get-go as nodes and their preference values.
GRAFIK ZEICHNEN.
Wie stellt man die Komplexität in Landau-Schreibweise dar?
Beispiel: 1000n+n^2+0,0001*2^n wäre O(2^n)
Es geht immer um den stärksten Term der Funktion. Ähnlich des Grenzwertes.
Wie verhindert der Miller-Tucker-Zemlin Algorithmus Subtouren beim TSP?
Die zur Auswahl stehende Kante wird nur zum Weg hinzugefügt, wenn der Zähler von u_j größer ist als u_i, somit darf j vorher noch nicht besucht worden sein.
Wichtig! X_ij ist nur eins, wenn j direkt auf i folgt, sonst 0.
