Graphen, Knoten, Kanten Ein Knoten ist ein Objekt oder Punkt eines Graphen. Eine Kante ist die Verbindung zwischen zwei Knoten. Ein Graph G = (V,E) besteht also aus einer Menge an Knoten V = {v1, v2, …, vn} sowie einer Menge an Kanten E = {e1, e2, …, en}. Jede Kante e = (vi, vj) … Read more
Definition des Kürzesten Weges Ein kürzester Weg in einen Graphen entspricht einem Weg von s (start) nach t (terminate) mit minimalen Gesamtkosten. Hierbei sind die Gesamtkosten die Summe der verwendeten Kantenkosten, also der Distanz von s nach t: d(s, t). Die Knoten s und t entstammen der Knotenmenge V aus dem Graphen G = (V, … Read more
In diesem Artikel geht um betriebliche Optimierungsprobleme und Algorithmen. Zudem werden Graphen, Pfade und Kreise wiederholt und die Komplexität besprochen. Zu den Algorithmen wird auf Heuristiken und Approximationsalgorithmen eingegangen, wobei dieses sich hauptsächlich auf das Travelling Salesman Problem (Problem des Handlungsreisenden) sowie das Rucksackproblem konzentrieren. Hier geht es vor allem um die Generierung einer gültigen … Read more
