DAA - Kurzanleitung

Ein Algorithmus besteht aus einer Reihe von Arbeitsschritten zur Lösung eines Problems bei der Durchführung von Berechnungs-, Datenverarbeitungs- und automatisierten Argumentationsaufgaben. Ein Algorithmus ist eine effiziente Methode, die in endlicher Zeit und Raum ausgedrückt werden kann.

Ein Algorithmus ist der beste Weg, um die Lösung eines bestimmten Problems auf sehr einfache und effiziente Weise darzustellen. Wenn wir einen Algorithmus für ein bestimmtes Problem haben, können wir ihn in einer beliebigen Programmiersprache implementierenalgorithm is independent from any programming languages.

Algorithmus-Design

Zu den wichtigen Aspekten des Algorithmusdesigns gehört die Erstellung eines effizienten Algorithmus zur effizienten Lösung eines Problems mit minimalem Zeit- und Raumaufwand.

Um ein Problem zu lösen, können verschiedene Ansätze verfolgt werden. Einige von ihnen können hinsichtlich des Zeitverbrauchs effizient sein, während andere Ansätze speichereffizient sein können. Es ist jedoch zu beachten, dass sowohl der Zeitverbrauch als auch die Speichernutzung nicht gleichzeitig optimiert werden können. Wenn wir einen Algorithmus benötigen, um in kürzerer Zeit ausgeführt zu werden, müssen wir in mehr Speicher investieren, und wenn wir einen Algorithmus benötigen, um mit weniger Speicher ausgeführt zu werden, müssen wir mehr Zeit haben.

Schritte zur Problementwicklung

Die folgenden Schritte sind zur Lösung von Rechenproblemen erforderlich.

• Problem Definition
• Entwicklung eines Modells
• Spezifikation eines Algorithmus
• Einen Algorithmus entwerfen
• Überprüfen der Richtigkeit eines Algorithmus
• Analyse eines Algorithmus
• Implementierung eines Algorithmus
• Programmtests
• Documentation

Eigenschaften von Algorithmen

Die Hauptmerkmale von Algorithmen sind wie folgt:

• Algorithmen müssen einen eindeutigen Namen haben

• Algorithmen sollten explizit definierte Ein- und Ausgänge haben

• Algorithmen sind mit eindeutigen Operationen gut geordnet

• Algorithmen halten in endlicher Zeit an. Algorithmen sollten nicht unendlich laufen, dh ein Algorithmus muss irgendwann enden

Pseudocode

Pseudocode bietet eine allgemeine Beschreibung eines Algorithmus ohne die mit Klartext verbundene Mehrdeutigkeit, aber auch ohne die Notwendigkeit, die Syntax einer bestimmten Programmiersprache zu kennen.

Die Laufzeit kann allgemeiner geschätzt werden, indem Pseudocode verwendet wird, um den Algorithmus als einen Satz grundlegender Operationen darzustellen, die dann gezählt werden können.

Unterschied zwischen Algorithmus und Pseudocode

Ein Algorithmus ist eine formale Definition mit einigen spezifischen Merkmalen, die einen Prozess beschreibt, der von einer Turing-vollständigen Computermaschine ausgeführt werden kann, um eine bestimmte Aufgabe auszuführen. Im Allgemeinen kann das Wort "Algorithmus" verwendet werden, um jede Aufgabe auf hoher Ebene in der Informatik zu beschreiben.

Andererseits ist Pseudocode eine informelle und (oft rudimentäre) vom Menschen lesbare Beschreibung eines Algorithmus, die viele detaillierte Details enthält. Das Schreiben eines Pseudocodes unterliegt keiner Einschränkung der Stile und sein einziges Ziel besteht darin, die Schritte des Algorithmus auf hoher Ebene in natürlicher Sprache auf sehr realistische Weise zu beschreiben.

Im Folgenden finden Sie beispielsweise einen Algorithmus für die Einfügesortierung.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

Hier ist ein Pseudocode, der beschreibt, wie der oben im Algorithmus Insertion-Sort erwähnte abstrakte Prozess auf hoher Ebene realistischer beschrieben werden könnte.

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

In diesem Tutorial werden Algorithmen in Form eines Pseudocodes vorgestellt, der in vielerlei Hinsicht C, C ++, Java, Python und anderen Programmiersprachen ähnelt.

Bei der theoretischen Analyse von Algorithmen ist es üblich, ihre Komplexität im asymptotischen Sinne zu schätzen, dh die Komplexitätsfunktion für beliebig große Eingaben zu schätzen. Der Begriff"analysis of algorithms" wurde von Donald Knuth geprägt.

Die Algorithmusanalyse ist ein wichtiger Teil der Theorie der rechnerischen Komplexität, die eine theoretische Schätzung der erforderlichen Ressourcen eines Algorithmus zur Lösung eines bestimmten Rechenproblems liefert. Die meisten Algorithmen arbeiten mit Eingaben beliebiger Länge. Die Analyse von Algorithmen ist die Bestimmung der Menge an Zeit- und Raumressourcen, die zur Ausführung erforderlich sind.

Normalerweise wird die Effizienz oder Laufzeit eines Algorithmus als eine Funktion angegeben, die die Eingangslänge mit der Anzahl der Schritte in Beziehung setzt, bekannt als time complexityoder Speichervolumen, bekannt als space complexity.

Die Notwendigkeit der Analyse

In diesem Kapitel werden wir die Notwendigkeit der Analyse von Algorithmen und die Auswahl eines besseren Algorithmus für ein bestimmtes Problem erörtern, da ein Rechenproblem durch verschiedene Algorithmen gelöst werden kann.

Indem wir einen Algorithmus für ein bestimmtes Problem betrachten, können wir beginnen, die Mustererkennung zu entwickeln, damit ähnliche Arten von Problemen mit Hilfe dieses Algorithmus gelöst werden können.

Algorithmen unterscheiden sich oft stark voneinander, obwohl das Ziel dieser Algorithmen dasselbe ist. Zum Beispiel wissen wir, dass eine Reihe von Zahlen mit verschiedenen Algorithmen sortiert werden kann. Die Anzahl der von einem Algorithmus durchgeführten Vergleiche kann für dieselbe Eingabe mit anderen variieren. Daher kann die zeitliche Komplexität dieser Algorithmen unterschiedlich sein. Gleichzeitig müssen wir den von jedem Algorithmus benötigten Speicherplatz berechnen.

Bei der Analyse des Algorithmus wird die Fähigkeit des Algorithmus zur Problemlösung im Hinblick auf die erforderliche Zeit und Größe (die Größe des Speichers für die Speicherung während der Implementierung) analysiert. Das Hauptanliegen der Analyse von Algorithmen ist jedoch die erforderliche Zeit oder Leistung. Im Allgemeinen führen wir die folgenden Analysetypen durch:

• Worst-case - Die maximale Anzahl von Schritten, die für eine Instanz der Größe ausgeführt werden a.

• Best-case - Die Mindestanzahl von Schritten, die für eine Instanz der Größe ausgeführt werden a.

• Average case - Eine durchschnittliche Anzahl von Schritten, die für eine Instanz der Größe ausgeführt wurden a.

• Amortized - Eine Folge von Operationen, die auf die Eingabe der Größe angewendet werden a gemittelt über die Zeit.

Um ein Problem zu lösen, müssen wir sowohl die zeitliche als auch die räumliche Komplexität berücksichtigen, da das Programm möglicherweise auf einem System ausgeführt wird, auf dem der Speicher begrenzt ist, aber ausreichend Speicherplatz verfügbar ist, oder umgekehrt. In diesem Zusammenhang, wenn wir vergleichenbubble sort und merge sort. Die Blasensortierung erfordert keinen zusätzlichen Speicher, die Zusammenführungssortierung erfordert jedoch zusätzlichen Speicherplatz. Obwohl die zeitliche Komplexität der Blasensortierung im Vergleich zur Zusammenführungssortierung höher ist, müssen wir möglicherweise die Blasensortierung anwenden, wenn das Programm in einer Umgebung ausgeführt werden muss, in der der Speicher sehr begrenzt ist.

Um den Ressourcenverbrauch eines Algorithmus zu messen, werden verschiedene Strategien verwendet, wie in diesem Kapitel erläutert.

Asymptotische Analyse

Das asymptotische Verhalten einer Funktion f(n) bezieht sich auf das Wachstum von f(n) wie n wird groß.

Wir ignorieren normalerweise kleine Werte von n, da wir normalerweise daran interessiert sind, abzuschätzen, wie langsam das Programm bei großen Eingaben sein wird.

Eine gute Faustregel lautet: Je langsamer die asymptotische Wachstumsrate ist, desto besser ist der Algorithmus. Obwohl es nicht immer wahr ist.

Zum Beispiel ein linearer Algorithmus $f(n) = d * n + k$ ist immer asymptotisch besser als eine quadratische, $f(n) = c.n^2 + q$.

Lösen von Wiederholungsgleichungen

Eine Wiederholung ist eine Gleichung oder Ungleichung, die eine Funktion in Bezug auf ihren Wert bei kleineren Eingaben beschreibt. Wiederholungen werden im Allgemeinen im Divide-and-Conquer-Paradigma verwendet.

Lass uns in Erwägung ziehen T(n) die Laufzeit auf ein Größenproblem sein n.

Wenn die Problemgröße klein genug ist, sagen wir n < c wo c Ist eine Konstante, benötigt die einfache Lösung eine konstante Zeit, die als geschrieben wird θ(1). Wenn die Aufteilung des Problems eine Reihe von Unterproblemen mit der Größe ergibt$\frac{n}{b}$.

Um das Problem zu lösen, ist die erforderliche Zeit a.T(n/b). Wenn wir die für die Teilung erforderliche Zeit berücksichtigen, istD(n) und die Zeit, die benötigt wird, um die Ergebnisse von Unterproblemen zu kombinieren, ist C(n)kann die Wiederholungsrelation dargestellt werden als -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

Eine Wiederholungsbeziehung kann mit den folgenden Methoden gelöst werden:

• Substitution Method - Bei dieser Methode erraten wir eine Grenze und beweisen mit Hilfe der mathematischen Induktion, dass unsere Annahme richtig war.

• Recursion Tree Method - Bei dieser Methode wird ein Wiederholungsbaum gebildet, in dem jeder Knoten die Kosten darstellt.

• Master’s Theorem - Dies ist eine weitere wichtige Technik, um die Komplexität einer Wiederholungsbeziehung zu ermitteln.

Amortisierte Analyse

Die amortisierte Analyse wird im Allgemeinen für bestimmte Algorithmen verwendet, bei denen eine Folge ähnlicher Operationen ausgeführt wird.

• Die amortisierte Analyse liefert eine Grenze für die tatsächlichen Kosten der gesamten Sequenz, anstatt die Kosten für die Sequenz der Operationen separat zu begrenzen.

• Die amortisierte Analyse unterscheidet sich von der Durchschnittsfallanalyse. Die Wahrscheinlichkeit ist nicht an der amortisierten Analyse beteiligt. Die amortisierte Analyse garantiert im schlimmsten Fall die durchschnittliche Leistung jeder Operation.

Es ist nicht nur ein Werkzeug zur Analyse, es ist eine Art, über das Design nachzudenken, da Design und Analyse eng miteinander verbunden sind.

Aggregatmethode

Die Aggregatmethode bietet eine globale Ansicht eines Problems. Bei dieser Methode, wennn Operationen dauern im schlimmsten Fall T(n)insgesamt. Dann sind die fortgeführten Anschaffungskosten für jede OperationT(n)/n. Obwohl unterschiedliche Vorgänge unterschiedliche Zeit in Anspruch nehmen können, werden bei diesem Verfahren unterschiedliche Kosten vernachlässigt.

Abrechnungsmethode

Bei dieser Methode werden verschiedene Vorgänge entsprechend ihren tatsächlichen Kosten unterschiedlichen Gebühren zugeordnet. Übersteigen die fortgeführten Anschaffungskosten eines Vorgangs die tatsächlichen Kosten, wird die Differenz dem Objekt als Gutschrift zugeordnet. Diese Gutschrift hilft bei der Bezahlung späterer Vorgänge, bei denen die fortgeführten Anschaffungskosten unter den tatsächlichen Kosten liegen.

Wenn die tatsächlichen Kosten und die fortgeführten Anschaffungskosten von i^th Betrieb sind $c_{i}$ und $\hat{c_{l}}$, dann

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

Mögliche Methode

Diese Methode stellt die vorausbezahlte Arbeit als potenzielle Energie dar, anstatt vorausbezahlte Arbeit als Gutschrift zu betrachten. Diese Energie kann freigesetzt werden, um den zukünftigen Betrieb zu finanzieren.

Wenn wir auftreten n Operationen, die mit einer anfänglichen Datenstruktur beginnen D₀. Lass uns in Erwägung ziehen,c_i als die tatsächlichen Kosten und D_i als Datenstruktur von i^thBetrieb. Die potentielle Funktion Ф ist einer reellen Zahl Ф zugeordnet (D_i), das damit verbundene Potenzial von D_i. Die fortgeführten Anschaffungskosten$\hat{c_{l}}$ kann definiert werden durch

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

Somit betragen die amortisierten Gesamtkosten

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

Dynamische Tabelle

Wenn der zugewiesene Speicherplatz für die Tabelle nicht ausreicht, müssen wir die Tabelle in eine größere Tabelle kopieren. Wenn eine große Anzahl von Elementen aus der Tabelle gelöscht wird, empfiehlt es sich, die Tabelle mit einer kleineren Größe neu zuzuweisen.

Mithilfe der amortisierten Analyse können wir zeigen, dass die amortisierten Kosten für das Einfügen und Löschen konstant sind und der nicht verwendete Speicherplatz in einer dynamischen Tabelle niemals einen konstanten Bruchteil des gesamten Speicherplatzes überschreitet.

Im nächsten Kapitel dieses Tutorials werden wir kurz auf asymptotische Notationen eingehen.

Beim Entwurf eines Algorithmus ist die Komplexitätsanalyse eines Algorithmus ein wesentlicher Aspekt. Die algorithmische Komplexität hängt hauptsächlich von der Leistung ab, davon, wie schnell oder langsam sie funktioniert.

Die Komplexität eines Algorithmus beschreibt die Effizienz des Algorithmus in Bezug auf die zur Verarbeitung der Daten erforderliche Speichermenge und die Verarbeitungszeit.

Die Komplexität eines Algorithmus wird aus zwei Perspektiven analysiert: Time und Space.

Zeitliche Komplexität

Diese Funktion beschreibt die zum Ausführen eines Algorithmus erforderliche Zeit in Bezug auf die Größe der Eingabe. "Zeit" kann die Anzahl der durchgeführten Speicherzugriffe, die Anzahl der Vergleiche zwischen Ganzzahlen, die Häufigkeit der Ausführung einer inneren Schleife oder eine andere natürliche Einheit in Bezug auf die Echtzeitdauer des Algorithmus bedeuten.

Raumkomplexität

Diese Funktion beschreibt die Speichermenge, die ein Algorithmus in Bezug auf die Größe der Eingabe in den Algorithmus benötigt. Wir sprechen oft von "zusätzlichem" Speicher, der benötigt wird, ohne den Speicher zu zählen, der zum Speichern der Eingabe selbst benötigt wird. Auch hier verwenden wir natürliche Einheiten (mit fester Länge), um dies zu messen.

Die Komplexität des Raums wird manchmal ignoriert, da der verwendete Platz minimal und / oder offensichtlich ist. Manchmal wird er jedoch genauso wichtig wie die Zeit.

Asymptotische Notationen

Die Ausführungszeit eines Algorithmus hängt vom Befehlssatz, der Prozessorgeschwindigkeit, der Platten-E / A-Geschwindigkeit usw. ab. Daher schätzen wir die Effizienz eines Algorithmus asymptotisch.

Die Zeitfunktion eines Algorithmus wird durch dargestellt T(n), wo n ist die Eingabegröße.

Verschiedene Arten von asymptotischen Notationen werden verwendet, um die Komplexität eines Algorithmus darzustellen. Die folgenden asymptotischen Notationen werden verwendet, um die Laufzeitkomplexität eines Algorithmus zu berechnen.

• O - Großes Oh

• Ω - Großes Omega

• θ - Großes Theta

• o - Wenig Oh

• ω - Kleines Omega

O: Asymptotische Obergrenze

'O' (Big Oh) ist die am häufigsten verwendete Notation. Eine Funktionf(n) dargestellt werden kann, ist die Reihenfolge von g(n) das ist O(g(n)), wenn ein Wert von positiver Ganzzahl vorhanden ist n wie n₀ und eine positive Konstante c so dass -

$f(n)\leqslant c.g(n)$ zum $n > n_{0}$ in jedem Fall

Daher Funktion g(n) ist eine Obergrenze für die Funktion f(n), wie g(n) wächst schneller als f(n).

Beispiel

Betrachten wir eine gegebene Funktion, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

In Anbetracht $g(n) = n^3$,

$f(n)\leqslant 5.g(n)$ für alle Werte von $n > 2$

Daher die Komplexität von f(n) kann dargestellt werden als $O(g(n))$dh $O(n^3)$

Ω: Asymptotische Untergrenze

Das sagen wir $f(n) = \Omega (g(n))$ wenn es eine Konstante gibt c Das $f(n)\geqslant c.g(n)$ für alle ausreichend großen Wert von n. Hiernist eine positive ganze Zahl. Es bedeutet Funktiong ist eine Untergrenze für die Funktion f;; nach einem bestimmten Wert vonn, f wird niemals untergehen g.

Beispiel

Betrachten wir eine gegebene Funktion, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$.

In Anbetracht $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ für alle Werte von $n > 0$.

Daher die Komplexität von f(n) kann dargestellt werden als $\Omega (g(n))$dh $\Omega (n^3)$

θ: Asymptotisch eng gebunden

Das sagen wir $f(n) = \theta(g(n))$ wenn es Konstanten gibt c₁ und c₂ Das $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ für alle ausreichend großen Wert von n. Hiern ist eine positive ganze Zahl.

Das bedeutet Funktion g ist eine enge Funktion f.

Beispiel

Betrachten wir eine gegebene Funktion, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

In Anbetracht $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ für alle großen Werte von n.

Daher die Komplexität von f(n) kann dargestellt werden als $\theta (g(n))$dh $\theta (n^3)$.

O - Notation

Die asymptotische Obergrenze von O-notationkann asymptotisch eng sein oder nicht. Die Grenze$2.n^2 = O(n^2)$ ist asymptotisch eng, aber die gebunden $2.n = O(n^2)$ ist nicht.

Wir gebrauchen o-notation eine Obergrenze zu bezeichnen, die nicht asymptotisch eng ist.

Wir definieren formal o(g(n)) (little-oh von g von n) als Menge f(n) = o(g(n)) für jede positive Konstante $c > 0$ und es existiert ein Wert $n_{0} > 0$, so dass $0 \leqslant f(n) \leqslant c.g(n)$.

Intuitiv in der o-notation, die Funktion f(n) wird relativ zu unbedeutend g(n) wie nnähert sich der Unendlichkeit; das ist,

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

Beispiel

Betrachten wir die gleiche Funktion, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

In Anbetracht $g(n) = n^{4}$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

Daher die Komplexität von f(n) kann dargestellt werden als $o(g(n))$dh $o(n^4)$.

ω - Notation

Wir gebrauchen ω-notationeine Untergrenze zu bezeichnen, die nicht asymptotisch eng ist. Formal definieren wir jedochω(g(n)) (kleines Omega von g von n) als Menge f(n) = ω(g(n)) für jede positive Konstante C > 0 und es existiert ein Wert $n_{0} > 0$, so dass $ 0 \ leqslant cg (n) <f (n) $.

Zum Beispiel, $\frac{n^2}{2} = \omega (n)$, aber $\frac{n^2}{2} \neq \omega (n^2)$. Die Beziehung$f(n) = \omega (g(n))$ impliziert, dass die folgende Grenze existiert

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

Das ist, f(n) wird relativ zu beliebig groß g(n) wie n nähert sich der Unendlichkeit.

Beispiel

Betrachten wir die gleiche Funktion, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

In Anbetracht $g(n) = n^2$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

Daher die Komplexität von f(n) kann dargestellt werden als $o(g(n))$dh $\omega (n^2)$.

Apriori- und Apostiari-Analyse

Apriori-Analyse bedeutet, dass die Analyse durchgeführt wird, bevor sie auf einem bestimmten System ausgeführt wird. Diese Analyse ist eine Phase, in der eine Funktion anhand eines theoretischen Modells definiert wird. Daher bestimmen wir die zeitliche und räumliche Komplexität eines Algorithmus, indem wir nur den Algorithmus betrachten, anstatt ihn auf einem bestimmten System mit einem anderen Speicher, Prozessor und Compiler auszuführen.

Die Apostiari-Analyse eines Algorithmus bedeutet, dass wir die Analyse eines Algorithmus erst durchführen, nachdem er auf einem System ausgeführt wurde. Es hängt direkt vom System ab und ändert sich von System zu System.

In einer Branche können wir keine Apostiari-Analyse durchführen, da die Software im Allgemeinen für einen anonymen Benutzer erstellt wurde, der sie auf einem anderen System als dem in der Branche vorhandenen ausführt.

In Apriori verwenden wir aus diesem Grund asymptotische Notationen, um die zeitliche und räumliche Komplexität zu bestimmen, wenn sie sich von Computer zu Computer ändern. asymptotisch sind sie jedoch gleich.

In diesem Kapitel werden wir die Komplexität von Rechenproblemen in Bezug auf den Platzbedarf eines Algorithmus diskutieren.

Die räumliche Komplexität teilt viele Merkmale der zeitlichen Komplexität und dient als weitere Möglichkeit, Probleme nach ihren Rechenschwierigkeiten zu klassifizieren.

Was ist Raumkomplexität?

Die Raumkomplexität ist eine Funktion, die die Menge an Speicher (Raum) beschreibt, die ein Algorithmus in Bezug auf die Menge an Eingaben in den Algorithmus benötigt.

Wir sprechen oft von extra memorybenötigt, ohne den Speicher zu zählen, der zum Speichern der Eingabe selbst benötigt wird. Auch hier verwenden wir natürliche Einheiten (mit fester Länge), um dies zu messen.

Wir können Bytes verwenden, aber es ist einfacher, beispielsweise die Anzahl der verwendeten Ganzzahlen, die Anzahl der Strukturen mit fester Größe usw. zu verwenden.

Am Ende ist die Funktion, die wir entwickeln, unabhängig von der tatsächlichen Anzahl von Bytes, die zur Darstellung der Einheit benötigt werden.

Die Raumkomplexität wird manchmal ignoriert, da der verwendete Raum minimal und / oder offensichtlich ist. Manchmal wird sie jedoch genauso wichtig wie die Zeitkomplexität

Definition

Lassen M deterministisch sein Turing machine (TM)das hält an allen Eingängen an. Die Raumkomplexität vonM ist die Funktion $f \colon N \rightarrow N$, wo f(n) ist die maximale Anzahl von Bandzellen und M scannt alle Längeneingaben M. Wenn die Raumkomplexität vonM ist f(n), Wir können das sagen M läuft im Weltraum f(n).

Wir schätzen die räumliche Komplexität der Turing-Maschine mithilfe der asymptotischen Notation.

Lassen $f \colon N \rightarrow R^+$eine Funktion sein. Die Raumkomplexitätsklassen können wie folgt definiert werden:

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE ist die Klasse von Sprachen, die im Polynomraum einer deterministischen Turing-Maschine entscheidbar sind.

Mit anderen Worten, PSPACE = U_k SPACE (n^k)

Satz von Savitch

Einer der frühesten Sätze in Bezug auf die Raumkomplexität ist der Satz von Savitch. Nach diesem Theorem kann eine deterministische Maschine nicht deterministische Maschinen simulieren, indem sie wenig Platz benötigt.

Für die zeitliche Komplexität scheint eine solche Simulation einen exponentiellen Zeitanstieg zu erfordern. Für die Raumkomplexität zeigt dieser Satz, dass jede nicht deterministische Turing-Maschine, die verwendetf(n) Raum kann in ein deterministisches TM umgewandelt werden, das verwendet f²(n) Raum.

Daher besagt der Satz von Savitch, dass für jede Funktion $f \colon N \rightarrow R^+$, wo $f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

Beziehung zwischen Komplexitätsklassen

Das folgende Diagramm zeigt die Beziehung zwischen verschiedenen Komplexitätsklassen.

Bisher haben wir in diesem Tutorial keine P- und NP-Klassen behandelt. Diese werden später besprochen.

Viele Algorithmen sind rekursiver Natur, um ein bestimmtes Problem zu lösen, das sich rekursiv mit Unterproblemen befasst.

Im divide and conquer approachwird ein Problem in kleinere Probleme unterteilt, dann werden die kleineren Probleme unabhängig voneinander gelöst, und schließlich werden die Lösungen kleinerer Probleme zu einer Lösung für das große Problem kombiniert.

Im Allgemeinen bestehen Divide-and-Conquer-Algorithmen aus drei Teilen:

• Divide the problem in eine Reihe von Unterproblemen, die kleinere Instanzen desselben Problems sind.

• Conquer the sub-problemsdurch rekursives Lösen. Wenn sie klein genug sind, lösen Sie die Unterprobleme als Basisfälle.

• Combine the solutions zu den Unterproblemen in die Lösung für das ursprüngliche Problem.

Vor- und Nachteile des Divide and Conquer-Ansatzes

Der Divide and Conquer-Ansatz unterstützt die Parallelität, da Unterprobleme unabhängig sind. Daher kann ein Algorithmus, der unter Verwendung dieser Technik entworfen wurde, gleichzeitig auf dem Multiprozessorsystem oder auf verschiedenen Maschinen ausgeführt werden.

Bei diesem Ansatz werden die meisten Algorithmen unter Verwendung von Rekursion entworfen, daher ist die Speicherverwaltung sehr hoch. Für rekursive Funktionen wird ein Stapel verwendet, in dem der Funktionsstatus gespeichert werden muss.

Anwendung des Divide and Conquer-Ansatzes

Im Folgenden sind einige Probleme aufgeführt, die mithilfe des Divide and Conquer-Ansatzes gelöst werden.

• Finden des Maximums und Minimums einer Folge von Zahlen
• Strassens Matrixmultiplikation
• Zusammenführen, sortieren
• Binäre Suche

Betrachten wir ein einfaches Problem, das durch Teilen und Erobern gelöst werden kann.

Problemstellung

Das Max-Min-Problem bei der Algorithmusanalyse besteht darin, den Maximal- und Minimalwert in einem Array zu ermitteln.

Lösung

So finden Sie die maximale und minimale Anzahl in einem bestimmten Array numbers[] von Größe nkann der folgende Algorithmus verwendet werden. Zuerst vertreten wir dienaive method und dann werden wir präsentieren divide and conquer approach.

Naive Methode

Die naive Methode ist eine grundlegende Methode, um jedes Problem zu lösen. Bei dieser Methode können die maximale und minimale Anzahl getrennt ermittelt werden. Um die maximale und minimale Anzahl zu finden, kann der folgende einfache Algorithmus verwendet werden.

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

Analyse

Die Anzahl der Vergleiche bei der naiven Methode beträgt 2n - 2.

Die Anzahl der Vergleiche kann mithilfe des Divide and Conquer-Ansatzes reduziert werden. Es folgt die Technik.

Ansatz teilen und erobern

Bei diesem Ansatz wird das Array in zwei Hälften geteilt. Dann werden unter Verwendung des rekursiven Ansatzes maximale und minimale Zahlen in jeder Hälfte gefunden. Geben Sie später das Maximum von zwei Maxima jeder Hälfte und das Minimum von zwei Minima jeder Hälfte zurück.

In diesem gegebenen Problem beträgt die Anzahl der Elemente in einem Array $y - x + 1$, wo y ist größer oder gleich x.

$\mathbf{\mathit{Max - Min(x, y)}}$ gibt die Maximal- und Minimalwerte eines Arrays zurück $\mathbf{\mathit{numbers[x...y]}}$.

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

Analyse

Lassen T(n) sei die Anzahl der Vergleiche von $\mathbf{\mathit{Max - Min(x, y)}}$, wo die Anzahl der Elemente $n = y - x + 1$.

Wenn T(n) stellt die Zahlen dar, dann kann die Wiederholungsrelation dargestellt werden als

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

Nehmen wir das an n ist in Form von Macht von 2. Daher,n = 2^k wo k ist die Höhe des Rekursionsbaums.

Damit,

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

Im Vergleich zur naiven Methode ist beim Divide and Conquer-Ansatz die Anzahl der Vergleiche geringer. Unter Verwendung der asymptotischen Notation werden jedoch beide Ansätze durch dargestelltO(n).

In diesem Kapitel werden wir die Zusammenführungssortierung diskutieren und ihre Komplexität analysieren.

Problemstellung

Das Problem des Sortierens einer Liste von Zahlen bietet sich sofort für eine Divide-and-Conquer-Strategie an: Teilen Sie die Liste in zwei Hälften, sortieren Sie jede Hälfte rekursiv und führen Sie dann die beiden sortierten Unterlisten zusammen.

Lösung

Bei diesem Algorithmus werden die Zahlen in einem Array gespeichert numbers[]. Hier,p und q repräsentiert den Start- und Endindex eines Subarrays.

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

Analyse

Betrachten wir die Laufzeit von Merge-Sort als T(n). Daher,

$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$wobei c und d Konstanten sind

Verwenden Sie daher diese Wiederholungsrelation,

$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$

Wie, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$

$=\:c.n + d.n.log\:n$

Deshalb, $T(n) = O(n\:log\:n)$

Beispiel

Im folgenden Beispiel haben wir den Merge-Sort-Algorithmus Schritt für Schritt gezeigt. Zunächst wird jedes Iterationsarray in zwei Unterarrays unterteilt, bis das Unterarray nur noch ein Element enthält. Wenn diese Unterarrays nicht weiter unterteilt werden können, werden Zusammenführungsvorgänge ausgeführt.

In diesem Kapitel werden wir einen anderen Algorithmus diskutieren, der auf der Divide and Conquer-Methode basiert.

Problemstellung

Die binäre Suche kann für ein sortiertes Array durchgeführt werden. Bei diesem Ansatz der Index eines Elementsxwird bestimmt, ob das Element zur Liste der Elemente gehört. Wenn das Array unsortiert ist, wird die Position mithilfe der linearen Suche bestimmt.

Lösung

In diesem Algorithmus wollen wir herausfinden, ob Element x gehört zu einer Reihe von Zahlen, die in einem Array gespeichert sind numbers[]. Wol und r stellen den linken und rechten Index eines Unterarrays dar, in dem eine Suchoperation ausgeführt werden soll.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Analyse

Die lineare Suche läuft in O(n)Zeit. Während die binäre Suche das Ergebnis in erzeugtO(log n) Zeit

Lassen T(n) sei die Anzahl der Vergleiche im schlimmsten Fall in einem Array von n Elemente.

Daher,

$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$

Verwenden dieser Wiederholungsrelation $T(n) = log\:n$.

Daher verwendet die binäre Suche $O(log\:n)$ Zeit.

Beispiel

In diesem Beispiel suchen wir nach Element 63.

In diesem Kapitel werden wir zuerst die allgemeine Methode der Matrixmultiplikation und später Strassens Matrixmultiplikationsalgorithmus diskutieren.

Problemstellung

Betrachten wir zwei Matrizen X und Y. Wir wollen die resultierende Matrix berechnenZ durch Multiplikation X und Y.

Naive Methode

Zunächst werden wir die naive Methode und ihre Komplexität diskutieren. Hier rechnen wirZ = X × Y. Mit der naiven Methode werden zwei Matrizen (X und Y) kann multipliziert werden, wenn die Reihenfolge dieser Matrizen ist p × q und q × r. Es folgt der Algorithmus.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

Komplexität

Hier nehmen wir an, dass ganzzahlige Operationen dauern O(1)Zeit. Dort sind dreiforSchleifen in diesem Algorithmus und einer ist in einem anderen verschachtelt. Daher nimmt der AlgorithmusO(n³) Zeit zur Ausführung.

Strassens Matrixmultiplikationsalgorithmus

In diesem Zusammenhang kann mit dem Matrix-Multiplikationsalgorithmus von Strassen der Zeitverbrauch ein wenig verbessert werden.

Strassens Matrixmultiplikation kann nur am durchgeführt werden square matrices wo n ist ein power of 2. Reihenfolge der beiden Matrizen sindn × n.

Teilen X, Y und Z in vier (n / 2) × (n / 2) Matrizen wie unten dargestellt -

$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ und $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$

Berechnen Sie mit dem Strassen-Algorithmus Folgendes:

$$M_{1} \: \colon= (A+C) \times (E+F)$$

$$M_{2} \: \colon= (B+D) \times (G+H)$$

$$M_{3} \: \colon= (A-D) \times (E+H)$$

$$M_{4} \: \colon= A \times (F-H)$$

$$M_{5} \: \colon= (C+D) \times (E)$$

$$M_{6} \: \colon= (A+B) \times (H)$$

$$M_{7} \: \colon= D \times (G-E)$$

Dann,

$$I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}$$

$$J \: \colon= M_{4} + M_{6}$$

$$K \: \colon= M_{5} + M_{7}$$

$$L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}$$

Analyse

$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$wobei c und d Konstanten sind

Mit dieser Wiederholungsrelation erhalten wir $T(n) = O(n^{log7})$

Daher ist die Komplexität von Strassens Matrixmultiplikationsalgorithmus $O(n^{log7})$.

Unter allen algorithmischen Ansätzen ist der einfachste und unkomplizierteste Ansatz die Greedy-Methode. Bei diesem Ansatz wird die Entscheidung auf der Grundlage der aktuell verfügbaren Informationen getroffen, ohne sich über die Auswirkungen der aktuellen Entscheidung in der Zukunft Gedanken zu machen.

Gierige Algorithmen bauen Teil für Teil eine Lösung auf und wählen den nächsten Teil so aus, dass er einen unmittelbaren Nutzen bringt. Bei diesem Ansatz werden die zuvor getroffenen Entscheidungen nie überdacht. Dieser Ansatz wird hauptsächlich zur Lösung von Optimierungsproblemen verwendet. Die gierige Methode ist einfach zu implementieren und in den meisten Fällen recht effizient. Daher können wir sagen, dass der Greedy-Algorithmus ein auf Heuristik basierendes algorithmisches Paradigma ist, das bei jedem Schritt der lokalen optimalen Auswahl folgt, in der Hoffnung, eine globale optimale Lösung zu finden.

Bei vielen Problemen führt es nicht zu einer optimalen Lösung, obwohl es in angemessener Zeit eine ungefähre (nahezu optimale) Lösung liefert.

Komponenten des Greedy-Algorithmus

Gierige Algorithmen haben die folgenden fünf Komponenten:

• A candidate set - Aus diesem Set wird eine Lösung erstellt.

• A selection function - Wird verwendet, um den besten Kandidaten für die Lösung auszuwählen.

• A feasibility function - Wird verwendet, um zu bestimmen, ob ein Kandidat verwendet werden kann, um zur Lösung beizutragen.

• An objective function - Wird verwendet, um einer Lösung oder einer Teillösung einen Wert zuzuweisen.

• A solution function - Wird verwendet, um anzuzeigen, ob eine vollständige Lösung erreicht wurde.

Anwendungsbereiche

Gieriger Ansatz wird verwendet, um viele Probleme zu lösen, wie z

• Finden des kürzesten Pfades zwischen zwei Eckpunkten mithilfe des Dijkstra-Algorithmus.

• Finden des minimalen Spannbaums in einem Diagramm unter Verwendung des Prim / Kruskal-Algorithmus usw.

Wo gieriger Ansatz fehlschlägt

Bei vielen Problemen findet der Greedy-Algorithmus keine optimale Lösung, außerdem kann er zu einer schlechtesten Lösung führen. Probleme wie Travelling Salesman und Knapsack können mit diesem Ansatz nicht gelöst werden.

Der Greedy-Algorithmus könnte mit einem bekannten Problem, das als Knapsack-Problem bezeichnet wird, sehr gut verstanden werden. Obwohl das gleiche Problem durch die Verwendung anderer algorithmischer Ansätze gelöst werden könnte, löst der Greedy-Ansatz das Fractional Knapsack-Problem in angemessener Zeit angemessen. Lassen Sie uns das Rucksackproblem im Detail diskutieren.

Rucksackproblem

Bestimmen Sie anhand einer Reihe von Elementen mit jeweils einem Gewicht und einem Wert eine Teilmenge der Elemente, die in eine Sammlung aufgenommen werden sollen, damit das Gesamtgewicht kleiner oder gleich einem bestimmten Grenzwert ist und der Gesamtwert so groß wie möglich ist.

Das Rucksackproblem liegt im kombinatorischen Optimierungsproblem. Es erscheint als Teilproblem in vielen, komplexeren mathematischen Modellen realer Probleme. Ein allgemeiner Ansatz für schwierige Probleme besteht darin, die restriktivste Einschränkung zu identifizieren, die anderen zu ignorieren, ein Rucksackproblem zu lösen und die Lösung irgendwie anzupassen, um die ignorierten Einschränkungen zu erfüllen.

Anwendungen

In vielen Fällen der Ressourcenzuweisung kann das Problem zusammen mit einigen Einschränkungen auf ähnliche Weise wie das Knapsack-Problem abgeleitet werden. Es folgt ein Beispiel.

• Den am wenigsten verschwenderischen Weg finden, um Rohstoffe zu schneiden
• Portfoliooptimierung
• Lagerprobleme schneiden

Problemszenario

Ein Dieb raubt ein Geschäft aus und kann ein maximales Gewicht von tragen Win seinen Rucksack. Es sind n Artikel im Geschäft verfügbar und das Gewicht voni^th Artikel ist w_i und sein Gewinn ist p_i. Welche Gegenstände sollte der Dieb mitnehmen?

In diesem Zusammenhang sollten die Gegenstände so ausgewählt werden, dass der Dieb die Gegenstände trägt, für die er maximalen Gewinn erzielt. Daher ist das Ziel des Diebes, den Gewinn zu maximieren.

Aufgrund der Art der Artikel werden Rucksackprobleme als kategorisiert

• Fractional Knapsack
• Knapsack

Fractional Knapsack

In diesem Fall können Gegenstände in kleinere Teile zerlegt werden, daher kann der Dieb Bruchteile von Gegenständen auswählen.

Nach der Problemstellung,

• Es gibt n Artikel im Laden

• Gewicht von i^th Artikel $w_{i} > 0$

• Gewinn für i^th Artikel $p_{i} > 0$ und

• Kapazität des Rucksacks ist W

In dieser Version des Rucksackproblems können Gegenstände in kleinere Teile zerlegt werden. Der Dieb kann also nur einen Bruchteil nehmenx_i von i^th Artikel.

$$0 \leqslant x_{i} \leqslant 1$$

Das i^th Artikel trägt das Gewicht bei $x_{i}.w_{i}$ auf das Gesamtgewicht im Rucksack und Gewinn $x_{i}.p_{i}$ zum Gesamtgewinn.

Daher ist das Ziel dieses Algorithmus zu

$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$

vorbehaltlich Einschränkungen,

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$

Es ist klar, dass eine optimale Lösung den Rucksack genau füllen muss, sonst könnten wir einen Bruchteil eines der verbleibenden Gegenstände hinzufügen und den Gesamtgewinn steigern.

Somit kann eine optimale Lösung erhalten werden durch

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$

In diesem Zusammenhang müssen wir zuerst diese Elemente nach dem Wert von sortieren $\frac{p_{i}}{w_{i}}$, damit $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$. Hier,x ist ein Array zum Speichern des Bruchteils von Elementen.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Analyse

Wenn die bereitgestellten Artikel bereits in absteigender Reihenfolge von sortiert sind $\mathbf{\frac{p_{i}}{w_{i}}}$, dann braucht der whileloop eine zeit in O(n);; Daher ist die Gesamtzeit einschließlich der Sortierung inO(n logn).

Beispiel

Betrachten wir die Kapazität des Rucksacks W = 60 und die Liste der bereitgestellten Elemente werden in der folgenden Tabelle angezeigt -

Artikel	EIN	B.	C.	D.
Profitieren	280	100	120	120
Gewicht	40	10	20	24
Verhältnis $(\frac{p_{i}}{w_{i}})$	7	10	6	5

Da die bereitgestellten Artikel nicht nach sortiert sind $\mathbf{\frac{p_{i}}{w_{i}}}$. Nach dem Sortieren sind die Elemente wie in der folgenden Tabelle gezeigt.

Artikel	B.	EIN	C.	D.
Profitieren	100	280	120	120
Gewicht	10	40	20	24
Verhältnis $(\frac{p_{i}}{w_{i}})$	10	7	6	5

Lösung

Nach dem Sortieren aller Artikel nach $\frac{p_{i}}{w_{i}}$. Zuerst alles vonB wird als Gewicht von gewählt Bist geringer als die Kapazität des Rucksacks. Nächstes ObjektA wird gewählt, da die verfügbare Kapazität des Rucksacks größer ist als das Gewicht von A. Jetzt,Cwird als nächster Punkt ausgewählt. Der gesamte Artikel kann jedoch nicht ausgewählt werden, da die verbleibende Kapazität des Rucksacks geringer ist als das Gewicht vonC.

Daher Bruchteil von C (dh (60 - 50) / 20) wird gewählt.

Jetzt entspricht die Kapazität des Rucksacks den ausgewählten Gegenständen. Daher kann kein Element mehr ausgewählt werden.

Das Gesamtgewicht der ausgewählten Artikel beträgt 10 + 40 + 20 * (10/20) = 60

Und der Gesamtgewinn ist 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Dies ist die optimale Lösung. Wir können nicht mehr Gewinn erzielen, wenn wir eine andere Kombination von Gegenständen auswählen.

Problemstellung

Bei Jobsequenzierungsproblemen besteht das Ziel darin, eine Sequenz von Jobs zu finden, die innerhalb ihrer Fristen abgeschlossen wird und maximalen Gewinn bietet.

Lösung

Betrachten wir eine Reihe von ngegebene Jobs, die mit Fristen und Gewinn verbunden sind, werden verdient, wenn ein Job innerhalb seiner Frist abgeschlossen ist. Diese Jobs müssen so bestellt werden, dass ein maximaler Gewinn erzielt wird.

Es kann vorkommen, dass nicht alle angegebenen Aufträge innerhalb ihrer Fristen ausgeführt werden.

Angenommen, Frist von i^th Job J_i ist d_i und der Gewinn aus diesem Job ist p_i. Daher ist die optimale Lösung dieses Algorithmus eine praktikable Lösung mit maximalem Gewinn.

So, $D(i) > 0$ zum $1 \leqslant i \leqslant n$.

Diese Jobs werden zunächst nach Gewinn geordnet, d. H. $p_{1} \geqslant p_{2} \geqslant p_{3} \geqslant \:... \: \geqslant p_{n}$.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Analyse

In diesem Algorithmus verwenden wir zwei Schleifen, eine innerhalb einer anderen. Daher ist die Komplexität dieses Algorithmus$O(n^2)$.

Beispiel

Betrachten wir eine Reihe gegebener Jobs, wie in der folgenden Tabelle gezeigt. Wir müssen eine Abfolge von Jobs finden, die innerhalb ihrer Fristen abgeschlossen werden und maximalen Gewinn bringen. Jeder Job ist mit einer Frist und einem Gewinn verbunden.

Job	J1	J2	J3	J4	J5
Frist	2	1	3	2	1
Profitieren	60	100	20	40	20

Lösung

Um dieses Problem zu lösen, werden die angegebenen Jobs in absteigender Reihenfolge nach ihrem Gewinn sortiert. Daher werden die Jobs nach dem Sortieren wie in der folgenden Tabelle gezeigt sortiert.

Job	J2	J1	J4	J3	J5
Frist	1	2	2	3	1
Profitieren	100	60	40	20	20

Aus diesen Jobs wählen wir zuerst aus J₂, da es innerhalb seiner Frist abgeschlossen werden kann und maximalen Gewinn beiträgt.

• Nächster, J₁ wird ausgewählt, da es im Vergleich zu mehr Gewinn bringt J₄.

• In der nächsten Uhr J₄ kann daher nicht ausgewählt werden, da die Frist abgelaufen ist J₃ wird ausgewählt, wenn es innerhalb seiner Frist ausgeführt wird.

• Die Arbeit J₅ wird verworfen, da es nicht innerhalb seiner Frist ausgeführt werden kann.

Die Lösung ist also die Reihenfolge der Jobs (J₂, J₁, J₃), die innerhalb ihrer Frist ausgeführt werden und maximalen Gewinn bringen.

Der Gesamtgewinn dieser Sequenz beträgt 100 + 60 + 20 = 180.

Führen Sie eine Reihe sortierter Dateien unterschiedlicher Länge zu einer einzigen sortierten Datei zusammen. Wir müssen eine optimale Lösung finden, bei der die resultierende Datei in kürzester Zeit generiert wird.

Wenn die Anzahl der sortierten Dateien angegeben ist, gibt es viele Möglichkeiten, sie zu einer einzigen sortierten Datei zusammenzuführen. Diese Zusammenführung kann paarweise durchgeführt werden. Daher wird diese Art der Zusammenführung als bezeichnet2-way merge patterns.

Da unterschiedliche Paarungen unterschiedliche Zeit benötigen, möchten wir in dieser Strategie einen optimalen Weg zum Zusammenführen vieler Dateien ermitteln. Bei jedem Schritt werden zwei kürzeste Sequenzen zusammengeführt.

Zusammenführen von a p-record file und ein q-record file erfordert möglicherweise p + q Rekordbewegungen, wobei die offensichtliche Wahl darin besteht, die beiden kleinsten Dateien bei jedem Schritt zusammenzuführen.

Zweiwege-Zusammenführungsmuster können durch binäre Zusammenführungsbäume dargestellt werden. Betrachten wir eine Reihe vonn sortierte Dateien {f₁, f₂, f₃, …, f_n}. Anfänglich wird jedes Element davon als ein einzelner Knoten-Binärbaum betrachtet. Um diese optimale Lösung zu finden, wird der folgende Algorithmus verwendet.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

Am Ende dieses Algorithmus repräsentiert das Gewicht des Wurzelknotens die optimalen Kosten.

Beispiel

Betrachten wir die gegebenen Dateien f ₁ , f ₂ , f ₃ , f ₄ und f ₅ mit einer Anzahl von 20, 30, 10, 5 bzw. 30 Elementen.

Wenn Zusammenführungsvorgänge gemäß der angegebenen Reihenfolge ausgeführt werden, dann

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Daher beträgt die Gesamtzahl der Operationen

50 + 60 + 65 + 95 = 270

Nun stellt sich die Frage, ob es eine bessere Lösung gibt.

Wenn wir die Zahlen nach ihrer Größe in aufsteigender Reihenfolge sortieren, erhalten wir die folgende Reihenfolge:

f₄, f₃, f₁, f₂, f₅

Daher können Zusammenführungsoperationen für diese Sequenz ausgeführt werden

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Daher beträgt die Gesamtzahl der Operationen

15 + 35 + 65 + 95 = 210

Offensichtlich ist dies besser als das vorherige.

In diesem Zusammenhang werden wir nun das Problem mit diesem Algorithmus lösen.

Erster Satz

Schritt 1

Schritt 2

Schritt 3

Schritt 4

Daher benötigt die Lösung 15 + 35 + 60 + 95 = 205 Vergleiche.

Dynamische Programmierung wird auch bei Optimierungsproblemen verwendet. Wie die Divide-and-Conquer-Methode löst die dynamische Programmierung Probleme, indem sie die Lösungen von Teilproblemen kombiniert. Darüber hinaus löst der dynamische Programmieralgorithmus jedes Unterproblem nur einmal und speichert dann seine Antwort in einer Tabelle, wodurch die Arbeit vermieden wird, die Antwort jedes Mal neu zu berechnen.

Zwei Haupteigenschaften eines Problems legen nahe, dass das angegebene Problem mithilfe der dynamischen Programmierung gelöst werden kann. Diese Eigenschaften sindoverlapping sub-problems and optimal substructure.

Überlappende Unterprobleme

Ähnlich wie beim Divide-and-Conquer-Ansatz kombiniert die dynamische Programmierung auch Lösungen für Unterprobleme. Es wird hauptsächlich verwendet, wenn die Lösung eines Teilproblems wiederholt benötigt wird. Die berechneten Lösungen werden in einer Tabelle gespeichert, sodass diese nicht neu berechnet werden müssen. Daher wird diese Technik benötigt, wenn überlappende Unterprobleme bestehen.

Beispielsweise hat die binäre Suche kein überlappendes Unterproblem. Während rekursives Programm von Fibonacci-Zahlen viele überlappende Unterprobleme aufweist.

Optimale Unterstruktur

Ein gegebenes Problem hat die optimale Substruktur-Eigenschaft, wenn die optimale Lösung des gegebenen Problems unter Verwendung optimaler Lösungen seiner Unterprobleme erhalten werden kann.

Zum Beispiel hat das Problem des kürzesten Pfades die folgende optimale Unterstruktureigenschaft:

Wenn ein Knoten x liegt auf dem kürzesten Weg von einem Quellknoten u zum Zielknoten v, dann der kürzeste Weg von u zu v ist die Kombination des kürzesten Weges von u zu xund der kürzeste Weg von x zu v.

Die Standardalgorithmen für den kürzesten Pfad aller Paare wie Floyd-Warshall und Bellman-Ford sind typische Beispiele für dynamische Programmierung.

Schritte des dynamischen Programmieransatzes

Der Algorithmus für die dynamische Programmierung besteht aus den folgenden vier Schritten:

• Charakterisieren Sie die Struktur einer optimalen Lösung.
• Definieren Sie rekursiv den Wert einer optimalen Lösung.
• Berechnen Sie den Wert einer optimalen Lösung, normalerweise von unten nach oben.
• Konstruieren Sie aus den berechneten Informationen eine optimale Lösung.

Anwendungen des dynamischen Programmieransatzes

• Matrixkettenmultiplikation
• Längste gemeinsame Folge
• Problem mit dem reisenden Verkäufer

In diesem Tutorial haben wir zuvor das Fractional Knapsack-Problem unter Verwendung des Greedy-Ansatzes erörtert. Wir haben gezeigt, dass der Greedy-Ansatz eine optimale Lösung für Fractional Knapsack bietet. In diesem Kapitel werden jedoch das 0-1-Rucksackproblem und seine Analyse behandelt.

In 0-1 Knapsack können Gegenstände nicht zerbrochen werden, was bedeutet, dass der Dieb den Gegenstand als Ganzes nehmen oder verlassen sollte. Dies ist der Grund, warum man es als 0-1 Knapsack bezeichnet.

Daher ist im Fall von 0-1 Knapsack der Wert von x_i Kann beides sein 0 oder 1, wo andere Einschränkungen gleich bleiben.

0-1 Rucksack kann nicht durch gierigen Ansatz gelöst werden. Ein gieriger Ansatz gewährleistet keine optimale Lösung. In vielen Fällen kann der gierige Ansatz eine optimale Lösung bieten.

Die folgenden Beispiele begründen unsere Aussage.

Beispiel 1

Nehmen wir an, dass die Kapazität des Rucksacks W = 25 beträgt und die Elemente wie in der folgenden Tabelle gezeigt sind.

Artikel	EIN	B.	C.	D.
Profitieren	24	18	18	10
Gewicht	24	10	10	7

Ohne Berücksichtigung des Gewinns pro Gewichtseinheit (p_i/w_i), wenn wir den gierigen Ansatz anwenden, um dieses Problem zu lösen, erster Punkt Awird ausgewählt , da es max beitragen _i mum Gewinn unter allen Elementen.

Nach Auswahl des Elements Awird kein Element mehr ausgewählt. Daher beträgt für diesen gegebenen Satz von Gegenständen der Gesamtgewinn24. Während die optimale Lösung durch Auswahl von Elementen erreicht werden kann,B und C, wobei der Gesamtgewinn 18 + 18 = 36 beträgt.

Beispiel-2

Anstatt die Elemente basierend auf dem Gesamtnutzen auszuwählen, werden in diesem Beispiel die Elemente basierend auf dem Verhältnis p _i / w _{i ausgewählt} . Nehmen wir an, dass die Kapazität des Rucksacks W = 60 beträgt und die Elemente wie in der folgenden Tabelle gezeigt sind.

Artikel	EIN	B.	C.
Preis	100	280	120
Gewicht	10	40	20
Verhältnis	10	7	6

Mit dem Greedy-Ansatz, erster Punkt Aist ausgewählt. Dann der nächste PunktBist gewählt. Daher ist der Gesamtgewinn100 + 280 = 380. Die optimale Lösung dieser Instanz kann jedoch durch Auswahl von Elementen erreicht werden.B und C, wo der Gesamtgewinn ist 280 + 120 = 400.

Daraus kann geschlossen werden, dass der gierige Ansatz möglicherweise keine optimale Lösung bietet.

Um 0-1 Knapsack zu lösen, ist ein dynamischer Programmieransatz erforderlich.

Problemstellung

Ein Dieb raubt ein Geschäft und kann einen max tragen _i mal GewichtWin seinen Rucksack. Es gibtn Artikel und Gewicht von i^th Artikel ist w_i und der Gewinn der Auswahl dieses Artikels ist p_i. Welche Gegenstände sollte der Dieb mitnehmen?

Dynamischer Programmieransatz

Lassen i Seien Sie der Artikel mit der höchsten Nummer in einer optimalen Lösung S zum WDollar. DannS^' = S - {i} ist eine optimale Lösung für W - w_i Dollar und der Wert der Lösung S ist V_i plus den Wert des Unterproblems.

Wir können diese Tatsache in der folgenden Formel ausdrücken: define c[i, w] die Lösung für Gegenstände sein 1,2, … , iund der max _i mum Gewichtw.

Der Algorithmus verwendet die folgenden Eingaben

• Der max _i mum GewichtW

• Die Anzahl der Elemente n

• Die zwei Sequenzen v = <v₁, v₂, …, v_n> und w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

Die Menge der zu entnehmenden Gegenstände kann ab der Tabelle aus der Tabelle abgeleitet werden c[n, w] und rückwärts verfolgen, woher die optimalen Werte kamen.

Wenn c [i, w] = c [i-1, w] , dann Punkti ist nicht Teil der Lösung, und wir verfolgen weiter mit c[i-1, w]. Ansonsten Artikeli ist Teil der Lösung, und wir verfolgen weiter mit c[i-1, w-W].

Analyse

Dieser Algorithmus benötigt θ ( n , w ) mal, da Tabelle c ( n + 1) ( w + 1) Einträge hat, wobei jeder Eintrag θ (1) Zeit zum Berechnen benötigt.

Das längste häufige Teilsequenzproblem besteht darin, die längste Sequenz zu finden, die in beiden angegebenen Zeichenfolgen vorhanden ist.

Folge

Betrachten wir eine Folge S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >.

Eine Folge Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m > über S wird genau dann als Teilsequenz von S bezeichnet, wenn sie aus der S-Löschung einiger Elemente abgeleitet werden kann.

Gemeinsame Folge

Annehmen, X und Ysind zwei Sequenzen über eine endliche Menge von Elementen. Wir können das sagenZ ist eine häufige Folge von X und Y, wenn Z ist eine Folge von beiden X und Y.

Längste gemeinsame Folge

Wenn ein Satz von Sequenzen angegeben ist, besteht das längste gemeinsame Teilsequenzproblem darin, eine gemeinsame Teilsequenz aller Sequenzen zu finden, die von maximaler Länge ist.

Das längste häufige Teilsequenzproblem ist ein klassisches Informatikproblem, das die Grundlage für Datenvergleichsprogramme wie das Diff-Utility bildet und Anwendungen in der Bioinformatik hat. Es wird auch häufig von Revisionskontrollsystemen wie SVN und Git verwendet, um mehrere Änderungen an einer revisionskontrollierten Sammlung von Dateien abzugleichen.

Naive Methode

Lassen X eine Folge von Längen sein m und Y eine Folge von Längen n. Überprüfen Sie für jede Teilsequenz vonX ob es eine Folge von ist Yund geben die längste gemeinsame gefundene Teilsequenz zurück.

Es gibt 2^m Teilsequenzen von X. Testen von Sequenzen, ob es sich um eine Teilsequenz von handelt oder nichtY nimmt O(n)Zeit. Somit würde der naive Algorithmus dauernO(n2^m) Zeit.

Dynamische Programmierung

Sei X = <x ₁ , x ₂ , x ₃ ,…, x _m > und Y = <y ₁ , y ₂ , y ₃ ,…, y _n > die Folgen. Um die Länge eines Elements zu berechnen, wird der folgende Algorithmus verwendet.

In diesem Verfahren Tabelle C[m, n] wird in der Hauptreihenfolge der Zeile und einer anderen Tabelle berechnet B[m,n] wird berechnet, um eine optimale Lösung zu konstruieren.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Dieser Algorithmus druckt die längste gemeinsame Teilsequenz von X und Y.

Analyse

Um die Tabelle zu füllen, die äußere for Schleife iteriert m Zeiten und das Innere for Schleife iteriert nmal. Daher ist die Komplexität des Algorithmus O (m, n) , wobeim und n sind die Länge von zwei Saiten.

Beispiel

In diesem Beispiel haben wir zwei Zeichenfolgen X = BACDB und Y = BDCB um die längste gemeinsame Teilfolge zu finden.

Nach dem Algorithmus LCS-Length-Table-Formulation (wie oben angegeben) haben wir Tabelle C (auf der linken Seite gezeigt) und Tabelle B (auf der rechten Seite gezeigt) berechnet.

In Tabelle B verwenden wir anstelle von 'D', 'L' und 'U' den diagonalen Pfeil, den Pfeil nach links bzw. den Pfeil nach oben. Nach dem Generieren von Tabelle B wird das LCS durch die Funktion LCS-Print bestimmt. Das Ergebnis ist BCB.

EIN spanning tree ist eine Teilmenge eines ungerichteten Graphen, bei dem alle Eckpunkte durch eine minimale Anzahl von Kanten verbunden sind.

Wenn alle Eckpunkte in einem Diagramm verbunden sind, gibt es mindestens einen Spannbaum. In einem Diagramm kann mehr als ein Spanning Tree vorhanden sein.

Eigenschaften

• Ein Spanning Tree hat keinen Zyklus.
• Jeder Scheitelpunkt kann von jedem anderen Scheitelpunkt aus erreicht werden.

Beispiel

In der folgenden Grafik bilden die hervorgehobenen Kanten einen Spannbaum.

Minimum Spanning Tree

EIN Minimum Spanning Tree (MST)ist eine Teilmenge von Kanten eines verbundenen gewichteten ungerichteten Graphen, der alle Eckpunkte mit dem minimal möglichen Gesamtkantengewicht verbindet. Um einen MST abzuleiten, kann der Prim-Algorithmus oder der Kruskal-Algorithmus verwendet werden. Daher werden wir in diesem Kapitel den Prim-Algorithmus diskutieren.

Wie wir bereits besprochen haben, kann ein Graph mehr als einen Spanning Tree haben. Wenn es gibtn Anzahl der Eckpunkte, die der Spanning Tree haben sollte n - 1Anzahl der Kanten. Wenn in diesem Zusammenhang jede Kante des Diagramms einer Gewichtung zugeordnet ist und mehr als ein Spannbaum vorhanden ist, müssen wir den minimalen Spannbaum des Diagramms ermitteln.

Wenn doppelte gewichtete Kanten vorhanden sind, kann der Graph außerdem mehrere minimale Spannbäume aufweisen.

In der obigen Grafik haben wir einen Spanning Tree gezeigt, obwohl dies nicht der minimale Spanning Tree ist. Die Kosten für diesen Spannbaum betragen (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Wir werden den Prim-Algorithmus verwenden, um den minimalen Spannbaum zu finden.

Prims Algorithmus

Der Algorithmus von Prim ist ein gieriger Ansatz, um den minimalen Spannbaum zu finden. In diesem Algorithmus können wir zur Bildung eines MST von einem beliebigen Scheitelpunkt ausgehen.

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

Die Funktion Extract-Min gibt den Scheitelpunkt mit minimalen Kantenkosten zurück. Diese Funktion funktioniert auf Min-Heap.

Beispiel

Mit dem Prim-Algorithmus können wir von jedem Scheitelpunkt aus beginnen. Lassen Sie uns vom Scheitelpunkt aus beginnen 1.

Scheitel 3 ist mit dem Scheitelpunkt verbunden 1 mit minimalen Kantenkosten, daher Kante (1, 2) wird dem Spanning Tree hinzugefügt.

Als nächstes Rand (2, 3) wird als das Minimum unter den Kanten angesehen {(1, 2), (2, 3), (3, 4), (3, 7)}.

Im nächsten Schritt bekommen wir Rand (3, 4) und (2, 4)mit minimalen Kosten. Kante(3, 4) wird zufällig ausgewählt.

In ähnlicher Weise Kanten (4, 5), (5, 7), (7, 8), (6, 8) und (6, 9)ausgewählt sind. Da alle Eckpunkte besucht werden, stoppt der Algorithmus jetzt.

Die Kosten für den Spanning Tree betragen (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. In diesem Diagramm gibt es keinen Spanning Tree mehr mit Kosten von weniger als 23.

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus löst das Problem der kürzesten Wege aus einer Hand in einem gerichteten gewichteten Graphen G = (V, E) , wobei alle Kanten nicht negativ sind (dh w (u, v) ≥ 0 für jede Kante (u, v) ) Є E ).

Im folgenden Algorithmus verwenden wir eine Funktion Extract-Min(), der den Knoten mit dem kleinsten Schlüssel extrahiert.

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

Analyse

Die Komplexität dieses Algorithmus hängt vollständig von der Implementierung der Extract-Min-Funktion ab. Wenn die Funktion zum Extrahieren von min mithilfe der linearen Suche implementiert wird, ist die Komplexität dieses AlgorithmusO(V² + E).

Wenn wir in diesem Algorithmus Min-Heap verwenden, auf dem Extract-Min() Funktion gibt den Knoten von zurück Q Mit dem kleinsten Schlüssel kann die Komplexität dieses Algorithmus weiter reduziert werden.

Beispiel

Betrachten wir den Scheitelpunkt 1 und 9als Start- bzw. Zielscheitelpunkt. Zu Beginn sind alle Scheitelpunkte mit Ausnahme des Startscheitelpunkts mit ∞ und der Startscheitelpunkt mit markiert0.

Scheitel	Initiale	Schritt 1 V 1	Schritt 2 V 3	Schritt 3 V 2	Schritt 4 V 4	Schritt 5 V 5	Schritt 6 V 7	Schritt 7 V 8	Schritt 8 V 6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	11	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	11	11	11	11	11	11	11
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

Daher der minimale Abstand des Scheitelpunkts 9 vom Scheitelpunkt 1 ist 20. Und der Weg ist

1 → 3 → 7 → 8 → 6 → 9

Dieser Pfad wird basierend auf Vorgängerinformationen bestimmt.

Bellman Ford Algorithmus

Dieser Algorithmus löst das Problem des kürzesten Wegs einer einzelnen Quelle eines gerichteten Graphen G = (V, E)bei denen die Kantengewichte negativ sein können. Darüber hinaus kann dieser Algorithmus angewendet werden, um den kürzesten Weg zu finden, wenn kein negativ gewichteter Zyklus existiert.

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

Analyse

Der Erste for Die Schleife wird für die Initialisierung verwendet, die in ausgeführt wird O(V)mal. Der nächstefor Schleife läuft |V - 1| geht über die Kanten, die dauertO(E) mal.

Daher läuft der Bellman-Ford-Algorithmus ein O(V, E) Zeit.

Beispiel

Das folgende Beispiel zeigt Schritt für Schritt, wie der Bellman-Ford-Algorithmus funktioniert. Dieser Graph hat eine negative Flanke, aber keinen negativen Zyklus, daher kann das Problem mit dieser Technik gelöst werden.

Zum Zeitpunkt der Initialisierung sind alle Scheitelpunkte außer der Quelle mit ∞ und die Quelle mit gekennzeichnet 0.

Im ersten Schritt werden alle Eckpunkte, die von der Quelle aus erreichbar sind, zu minimalen Kosten aktualisiert. Daher Eckpunktea und h werden aktualisiert.

Im nächsten Schritt Scheitelpunkte a, b, f und e werden aktualisiert.

Nach der gleichen Logik werden in diesem Schritt Eckpunkte verwendet b, f, c und g werden aktualisiert.

Hier Eckpunkte c und d werden aktualisiert.

Daher der minimale Abstand zwischen dem Scheitelpunkt s und Scheitelpunkt d ist 20.

Basierend auf den Vorgängerinformationen lautet der Pfad s → h → e → g → c → d

Ein mehrstufiges Diagramm G = (V, E) ist ein gerichteter Graph, in den Eckpunkte unterteilt sind k (wo k > 1) Anzahl der disjunkten Teilmengen S = {s₁,s₂,…,s_k}so dass die Kante (u, v) in E ist, dann ist u _i und v _{1 + 1} für einige Teilmengen in der Partition und |s₁| = |s_k| = 1.

Der Scheitelpunkt s Є s₁ heißt das source und der Scheitelpunkt t Є s_k wird genannt sink.

Gwird normalerweise als gewichteter Graph angenommen. In diesem Diagramm werden die Kosten einer Kante (i, j) durch c (i, j) dargestellt . Daher die Kosten für den Pfad von der Quelles sinken t ist die Summe der Kosten jeder Kante in diesem Pfad.

Das mehrstufige Diagrammproblem besteht darin, den Pfad mit minimalen Kosten von der Quelle zu finden s sinken t.

Beispiel

Betrachten Sie das folgende Beispiel, um das Konzept des mehrstufigen Diagramms zu verstehen.

Nach der Formel müssen wir die Kosten berechnen (i, j) Verwenden Sie die folgenden Schritte

Schritt 1: Kosten (K-2, j)

In diesem Schritt werden drei Knoten (Knoten 4, 5. 6) als ausgewählt j. Daher haben wir drei Möglichkeiten, um die Mindestkosten in diesem Schritt zu wählen.

Kosten (3, 4) = min {c (4, 7) + Kosten (7, 9), c (4, 8) + Kosten (8, 9)} = 7

Kosten (3, 5) = min {c (5, 7) + Kosten (7, 9), c (5, 8) + Kosten (8, 9)} = 5

Kosten (3, 6) = min {c (6, 7) + Kosten (7, 9), c (6, 8) + Kosten (8, 9)} = 5

Schritt 2: Kosten (K-3, j)

Zwei Knoten werden als j ausgewählt, da im Stadium k - 3 = 2 zwei Knoten 2 und 3 vorhanden sind. Der Wert i = 2 und j = 2 und 3.

Kosten (2, 2) = min {c (2, 4) + Kosten (4, 8) + Kosten (8, 9), c (2, 6) +

Kosten (6, 8) + Kosten (8, 9)} = 8

Kosten (2, 3) = {c (3, 4) + Kosten (4, 8) + Kosten (8, 9), c (3, 5) + Kosten (5, 8) + Kosten (8, 9), c (3, 6) + Kosten (6, 8) + Kosten (8, 9)} = 10

Schritt 3: Kosten (K-4, j)

Kosten (1, 1) = {c (1, 2) + Kosten (2, 6) + Kosten (6, 8) + Kosten (8, 9), c (1, 3) + Kosten (3, 5) + Kosten (5, 8) + Kosten (8, 9))} = 12

c (1, 3) + Kosten (3, 6) + Kosten (6, 8 + Kosten (8, 9))} = 13

Daher ist der Weg mit den minimalen Kosten 1→ 3→ 5→ 8→ 9.

Problemstellung

Ein Reisender muss alle Städte aus einer Liste besuchen, in der Entfernungen zwischen allen Städten bekannt sind und jede Stadt nur einmal besucht werden sollte. Was ist die kürzest mögliche Route, auf der er jede Stadt genau einmal besucht und in die Ursprungsstadt zurückkehrt?

Lösung

Das Problem des reisenden Verkäufers ist das berüchtigtste Rechenproblem. Wir können den Brute-Force-Ansatz verwenden, um jede mögliche Tour zu bewerten und die beste auszuwählen. Zumn Anzahl der Eckpunkte in einem Diagramm gibt es (n - 1)! Anzahl der Möglichkeiten.

Anstelle von Brute-Force unter Verwendung eines dynamischen Programmieransatzes kann die Lösung in kürzerer Zeit erhalten werden, obwohl es keinen Polynomzeitalgorithmus gibt.

Betrachten wir ein Diagramm G = (V, E), wo V ist eine Reihe von Städten und Eist eine Reihe von gewichteten Kanten. Eine Eckee(u, v) repräsentiert diese Eckpunkte u und vsind verbunden. Abstand zwischen Scheitelpunktu und v ist d(u, v), die nicht negativ sein sollte.

Angenommen, wir haben in der Stadt angefangen 1 und nachdem wir einige Städte besucht haben, sind wir jetzt in der Stadt j. Daher ist dies eine Teiltour. Wir müssen es auf jeden Fall wissenj, da dies bestimmt, welche Städte als nächstes am bequemsten zu besuchen sind. Wir müssen auch alle bisher besuchten Städte kennen, damit wir keine von ihnen wiederholen. Daher ist dies ein geeignetes Unterproblem.

Für eine Untergruppe von Städten S Є {1, 2, 3, ... , n} das schließt ein 1, und j Є S, Lassen C(S, j) ist die Länge des kürzesten Pfades, der jeden Knoten in besucht S genau einmal ab 1 und endet bei j.

Wann |S| > 1 definieren wirC(S, 1) = ∝ da der Pfad nicht bei beginnen und enden kann 1.

Lassen Sie uns jetzt ausdrücken C(S, j)in Bezug auf kleinere Unterprobleme. Wir müssen bei beginnen1 und ende bei j. Wir sollten die nächste Stadt so auswählen, dass

$$C(S, j) = min \:C(S - \lbrace j \rbrace, i) + d(i, j)\:where\: i\in S \: and\: i \neq jc(S, j) = minC(s- \lbrace j \rbrace, i)+ d(i,j) \:where\: i\in S \: and\: i \neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

Analyse

Es gibt höchstens $2^n.n$Unterprobleme und jedes braucht lineare Zeit, um zu lösen. Daher beträgt die Gesamtlaufzeit$O(2^n.n^2)$.

Beispiel

Im folgenden Beispiel werden die Schritte zur Lösung des Problems des Handlungsreisenden veranschaulicht.

Aus dem obigen Diagramm wird die folgende Tabelle erstellt.

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

S = Φ

$$\small Cost (2,\Phi,1) = d (2,1) = 5\small Cost(2,\Phi,1)=d(2,1)=5$$

$$\small Cost (3,\Phi,1) = d (3,1) = 6\small Cost(3,\Phi,1)=d(3,1)=6$$

$$\small Cost (4,\Phi,1) = d (4,1) = 8\small Cost(4,\Phi,1)=d(4,1)=8$$

S = 1

$$\small Cost (i,s) = min \lbrace Cost (j,s – (j)) + d [i,j]\rbrace\small Cost (i,s)=min \lbrace Cost (j,s)-(j))+ d [i,j]\rbrace$$

$$\small Cost (2,\lbrace 3 \rbrace,1) = d [2,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(2,\lbrace3 \rbrace,1)=d[2,3]+cost(3,\Phi ,1)=9+6=15$$

$$\small Cost (2,\lbrace 4 \rbrace,1) = d [2,4] + Cost (4,\Phi,1) = 10 + 8 = 18cost(2,\lbrace4 \rbrace,1)=d[2,4]+cost(4,\Phi,1)=10+8=18$$

$$\small Cost (3,\lbrace 2 \rbrace,1) = d [3,2] + Cost (2,\Phi,1) = 13 + 5 = 18cost(3,\lbrace2 \rbrace,1)=d[3,2]+cost(2,\Phi,1)=13+5=18$$

$$\small Cost (3,\lbrace 4 \rbrace,1) = d [3,4] + Cost (4,\Phi,1) = 12 + 8 = 20cost(3,\lbrace4 \rbrace,1)=d[3,4]+cost(4,\Phi,1)=12+8=20$$

$$\small Cost (4,\lbrace 3 \rbrace,1) = d [4,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(4,\lbrace3 \rbrace,1)=d[4,3]+cost(3,\Phi,1)=9+6=15$$

$$\small Cost (4,\lbrace 2 \rbrace,1) = d [4,2] + Cost (2,\Phi,1) = 8 + 5 = 13cost(4,\lbrace2 \rbrace,1)=d[4,2]+cost(2,\Phi,1)=8+5=13$$

S = 2

$$\small Cost(2, \lbrace 3, 4 \rbrace, 1)=\begin{cases}d[2, 3] + Cost(3, \lbrace 4 \rbrace, 1) = 9 + 20 = 29\\d[2, 4] + Cost(4, \lbrace 3 \rbrace, 1) = 10 + 15 = 25=25\small Cost (2,\lbrace 3,4 \rbrace,1)\\\lbrace d[2,3]+ \small cost(3,\lbrace4\rbrace,1)=9+20=29d[2,4]+ \small Cost (4,\lbrace 3 \rbrace ,1)=10+15=25\end{cases}= 25$$

$$\small Cost(3, \lbrace 2, 4 \rbrace, 1)=\begin{cases}d[3, 2] + Cost(2, \lbrace 4 \rbrace, 1) = 13 + 18 = 31\\d[3, 4] + Cost(4, \lbrace 2 \rbrace, 1) = 12 + 13 = 25=25\small Cost (3,\lbrace 2,4 \rbrace,1)\\\lbrace d[3,2]+ \small cost(2,\lbrace4\rbrace,1)=13+18=31d[3,4]+ \small Cost (4,\lbrace 2 \rbrace ,1)=12+13=25\end{cases}= 25$$

$$\small Cost(4, \lbrace 2, 3 \rbrace, 1)=\begin{cases}d[4, 2] + Cost(2, \lbrace 3 \rbrace, 1) = 8 + 15 = 23\\d[4, 3] + Cost(3, \lbrace 2 \rbrace, 1) = 9 + 18 = 27=23\small Cost (4,\lbrace 2,3 \rbrace,1)\\\lbrace d[4,2]+ \small cost(2,\lbrace3\rbrace,1)=8+15=23d[4,3]+ \small Cost (3,\lbrace 2 \rbrace ,1)=9+18=27\end{cases}= 23$$

S = 3

$$\small Cost(1, \lbrace 2, 3, 4 \rbrace, 1)=\begin{cases}d[1, 2] + Cost(2, \lbrace 3, 4 \rbrace, 1) = 10 + 25 = 35\\d[1, 3] + Cost(3, \lbrace 2, 4 \rbrace, 1) = 15 + 25 = 40\\d[1, 4] + Cost(4, \lbrace 2, 3 \rbrace, 1) = 20 + 23 = 43=35 cost(1,\lbrace 2,3,4 \rbrace),1)\\d[1,2]+cost(2,\lbrace 3,4 \rbrace,1)=10+25=35\\d[1,3]+cost(3,\lbrace 2,4 \rbrace,1)=15+25=40\\d[1,4]+cost(4,\lbrace 2,3 \rbrace ,1)=20+23=43=35\end{cases}$$

Der Mindestkostenpfad beträgt 35.

Beginnen Sie mit den Kosten {1, {2, 3, 4}, 1}erhalten wir den Mindestwert für d [1, 2]. Wanns = 3Wählen Sie den Pfad von 1 bis 2 (Kosten sind 10) und gehen Sie dann rückwärts. Wanns = 2erhalten wir den Mindestwert für d [4, 2]. Wählen Sie den Pfad von 2 bis 4 (Kosten sind 10) und gehen Sie dann rückwärts.

Wann s = 1erhalten wir den Mindestwert für d [4, 3]. Wenn Sie den Pfad 4 bis 3 auswählen (die Kosten betragen 9), gehen wir zu und dann zus = ΦSchritt. Wir bekommen den Mindestwert fürd [3, 1] (Kosten sind 6).

Ein binärer Suchbaum (BST) ist ein Baum, in dem die Schlüsselwerte in den internen Knoten gespeichert sind. Die externen Knoten sind Nullknoten. Die Schlüssel sind lexikografisch geordnet, dh für jeden internen Knoten sind alle Schlüssel im linken Unterbaum kleiner als die Schlüssel im Knoten und alle Schlüssel im rechten Unterbaum sind größer.

Wenn wir die Häufigkeit der Suche nach jedem der Schlüssel kennen, ist es recht einfach, die erwarteten Kosten für den Zugriff auf jeden Knoten im Baum zu berechnen. Ein optimaler binärer Suchbaum ist eine BST, die nur minimale erwartete Kosten für die Lokalisierung jedes Knotens aufweist

Die Suchzeit eines Elements in einer BST beträgt O(n), während in einer Balanced-BST Suchzeit ist O(log n). Auch hier kann die Suchzeit im binären Suchbaum für optimale Kosten verbessert werden, indem die am häufigsten verwendeten Daten in der Wurzel und näher am Wurzelelement platziert werden, während die am seltensten verwendeten Daten in der Nähe von Blättern und in Blättern platziert werden.

Hier wird der optimale binäre Suchbaumalgorithmus vorgestellt. Zuerst erstellen wir eine BST aus einer Reihe von bereitgestelltenn Anzahl der verschiedenen Schlüssel < k₁, k₂, k₃, ... k_n >. Hier nehmen wir die Wahrscheinlichkeit des Zugriffs auf einen Schlüssel anK_i ist p_i. Einige Dummy-Schlüssel (d₀, d₁, d₂, ... d_n) werden hinzugefügt, da möglicherweise nach den Werten gesucht wird, die im Schlüsselsatz nicht vorhanden sind K. Wir nehmen für jeden Dummy-Schlüssel and_i Zugangswahrscheinlichkeit ist q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Analyse

Der Algorithmus erfordert O (n³) Zeit, seit drei verschachtelt forSchleifen werden verwendet. Jede dieser Schleifen nimmt höchstens ann Werte.

Beispiel

In Anbetracht des folgenden Baums betragen die Kosten 2,80, obwohl dies kein optimales Ergebnis ist.

Knoten	Tiefe	Wahrscheinlichkeit	Beitrag
k 1	1	0,15	0,30
k 2	0	0,10	0,10
k 3	2	0,05	0,15
k 4	1	0,10	0,20
k 5	2	0,20	0,60
d 0	2	0,05	0,15
d 1	2	0,10	0,30
d 2	3	0,05	0,20
d 3	3	0,05	0,20
d 4	3	0,05	0,20
d 5	3	0,10	0,40
Total			2,80

Um eine optimale Lösung zu erhalten, werden mithilfe des in diesem Kapitel beschriebenen Algorithmus die folgenden Tabellen generiert.

In den folgenden Tabellen ist der Spaltenindex i und Zeilenindex ist j.

e	1	2	3	4	5	6
5	2,75	2.00	1.30	0,90	0,50	0,10
4	1,75	1,20	0,60	0,30	0,05
3	1,25	0,70	0,25	0,05
2	0,90	0,40	0,05
1	0,45	0,10
0	0,05

w	1	2	3	4	5	6
5	1,00	0,80	0,60	0,50	0,35	0,10
4	0,70	0,50	0,30	0,20	0,05
3	0,55	0,35	0,15	0,05
2	0,45	0,25	0,05
1	0,30	0,10
0	0,05

Wurzel	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

Aus diesen Tabellen kann der optimale Baum gebildet werden.

Es gibt verschiedene Arten von Heaps. In diesem Kapitel werden wir jedoch auf binäre Heaps eingehen. EINbinary heapist eine Datenstruktur, die einem vollständigen Binärbaum ähnelt. Die Heap-Datenstruktur entspricht den unten beschriebenen Reihenfolgeeigenschaften. Im Allgemeinen wird ein Heap durch ein Array dargestellt. In diesem Kapitel stellen wir einen Haufen von darH.

Da die Elemente eines Heaps in einem Array gespeichert sind, wird der Startindex als betrachtet 1, die Position des Elternknotens von i^th Element finden Sie unter ⌊ i/2 ⌋. Linkes Kind und rechtes Kind voni^th Knoten ist an Position 2i und 2i + 1.

Ein binärer Heap kann weiter als entweder a klassifiziert werden max-heap oder ein min-heap basierend auf der bestellenden Eigenschaft.

Max-Heap

In diesem Heap ist der Schlüsselwert eines Knotens größer oder gleich dem Schlüsselwert des höchsten untergeordneten Knotens.

Daher, H[Parent(i)] ≥ H[i]

Min-Heap

Im Mittelwert-Heap ist der Schlüsselwert eines Knotens kleiner oder gleich dem Schlüsselwert des niedrigsten untergeordneten Elements.

Daher, H[Parent(i)] ≤ H[i]

In diesem Zusammenhang werden nachfolgend grundlegende Operationen in Bezug auf Max-Heap gezeigt. Das Einfügen und Löschen von Elementen in und aus Haufen erfordert eine Neuanordnung von Elementen. Daher,Heapify Funktion muss aufgerufen werden.

Array-Darstellung

Ein vollständiger Binärbaum kann durch ein Array dargestellt werden, in dem seine Elemente mithilfe der Durchquerung der Ebenenreihenfolge gespeichert werden.

Betrachten wir einen Heap (wie unten gezeigt), der durch ein Array dargestellt wird H.

Betrachtet man den Startindex als 0Bei Verwendung der Durchquerung der Ebenenreihenfolge werden die Elemente wie folgt in einem Array gehalten.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

In diesem Zusammenhang werden Operationen auf dem Heap in Bezug auf Max-Heap dargestellt.

So finden Sie den Index des übergeordneten Elements eines Elements im Index i, der folgende Algorithmus Parent (numbers[], i) wird eingesetzt.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

Der Index des linken untergeordneten Elements eines Elements am Index i kann mit dem folgenden Algorithmus gefunden werden: Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

Der Index des rechten untergeordneten Elements eines Elements am Index i kann mit dem folgenden Algorithmus gefunden werden: Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

Um ein Element in einen Heap einzufügen, wird das neue Element zunächst als letztes Element des Arrays an das Ende des Heaps angehängt.

Nach dem Einfügen dieses Elements kann die Heap-Eigenschaft verletzt werden. Daher wird die Heap-Eigenschaft repariert, indem das hinzugefügte Element mit seinem übergeordneten Element verglichen und das hinzugefügte Element um eine Ebene nach oben verschoben wird, wobei Positionen mit dem übergeordneten Element ausgetauscht werden. Dieser Vorgang wird aufgerufenpercolation up.

Der Vergleich wird wiederholt, bis der Elternteil größer oder gleich dem Perkolationselement ist.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Analyse

Zunächst wird am Ende des Arrays ein Element hinzugefügt. Wenn es die Heap-Eigenschaft verletzt, wird das Element mit seinem übergeordneten Element ausgetauscht. Die Höhe des Baumes istlog n. Maximallog n Anzahl der Operationen muss ausgeführt werden.

Daher ist die Komplexität dieser Funktion O(log n).

Beispiel

Betrachten wir einen Max-Heap, wie unten gezeigt, bei dem ein neues Element 5 hinzugefügt werden muss.

Am Ende dieses Arrays werden zunächst 55 hinzugefügt.

Nach dem Einfügen wird die Heap-Eigenschaft verletzt. Daher muss das Element mit seinem übergeordneten Element ausgetauscht werden. Nach dem Tausch sieht der Heap wie folgt aus.

Auch hier verletzt das Element die Eigenschaft von Heap. Daher wird es mit seinem Elternteil getauscht.

Jetzt müssen wir aufhören.

Die Heapify-Methode ordnet die Elemente eines Arrays neu, wobei der linke und der rechte Unterbaum von i^th Element gehorcht der Heap-Eigenschaft.

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

Wenn das bereitgestellte Array die Heap-Eigenschaft nicht erfüllt, wird Heap basierend auf dem folgenden Algorithmus erstellt Build-Max-Heap (numbers[]).

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

Die Extraktionsmethode wird verwendet, um das Stammelement eines Heaps zu extrahieren. Es folgt der Algorithmus.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Beispiel

Betrachten wir dasselbe zuvor diskutierte Beispiel. Jetzt wollen wir ein Element extrahieren. Diese Methode gibt das Stammelement des Heaps zurück.

Nach dem Löschen des Stammelements wird das letzte Element an die Stammposition verschoben.

Nun wird die Heapify-Funktion aufgerufen. Nach Heapify wird der folgende Heap generiert.

Die Blasensortierung ist ein elementarer Sortieralgorithmus, bei dem bei Bedarf wiederholt benachbarte Elemente ausgetauscht werden. Wenn kein Austausch erforderlich ist, wird die Datei sortiert.

Dies ist die einfachste Technik unter allen Sortieralgorithmen.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Implementierung

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Analyse

Hier ist die Anzahl der Vergleiche

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Die Grafik zeigt deutlich die n² Art der Blasensorte.

Bei diesem Algorithmus ist die Anzahl der Vergleiche unabhängig vom Datensatz, dh ob die bereitgestellten Eingabeelemente in sortierter Reihenfolge oder in umgekehrter Reihenfolge oder zufällig sind.

Speicherbedarf

Aus dem oben angegebenen Algorithmus geht hervor, dass die Blasensortierung keinen zusätzlichen Speicher benötigt.

Beispiel

Unsorted list:

5 2 1 4 3 7 6

1 ^st Iteration:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2^nd iteration:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

There is no change in 3^rd, 4^th, 5^th and 6^th iteration.

Finally,

the sorted list is

1 2 3 4 5 6 7

Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game.

The numbers, which are needed to be sorted, are known as keys. Here is the algorithm of the insertion sort method.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Analysis

Run time of this algorithm is very much dependent on the given input.

If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n²) time.

Example

Unsorted list:

2 13 5 18 14

1^st iteration:

Key = a[2] = 13

a[1] = 2 < 13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Key = a[3] = 5

a[2] = 13 > 5

Swap 5 and 13

2 5 13 18 14

Next, a[1] = 2 < 13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Key = a[4] = 18

a[3] = 13 < 18,

a[2] = 5 < 18,

a[1] = 2 < 18

Swap, no swap

2 5 13 18 14

4^th iteration:

Key = a[5] = 14

a[4] = 18 > 14

Swap 18 and 14

2 5 13 14 18

Next, a[3] = 13 < 14,

a[2] = 5 < 14,

a[1] = 2 < 14

So, no swap

2 5 13 14 18

Finally,

the sorted list is

2 5 13 14 18

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once.

Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order.

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if A[j] < min x is executed exactly the same number of times in every case.

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort.

• Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array.

• Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n - 1 exchanges and

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparisons.

These observations hold, no matter what the input data is.

In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.

Implementation

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Example

Unsorted list:

5 2 1 4 3

1^st iteration:

Smallest = 5

2 < 5, smallest = 2

1 < 2, smallest = 1

4 > 1, smallest = 1

3 > 1, smallest = 1

Swap 5 and 1

1 2 5 4 3

2^nd iteration:

Smallest = 2

2 < 5, smallest = 2

2 < 4, smallest = 2

2 < 3, smallest = 2

No Swap

1 2 5 4 3

3^rd iteration:

Smallest = 5

4 < 5, smallest = 4

3 < 4, smallest = 3

Swap 5 and 3

1 2 3 4 5

4^th iteration:

Smallest = 4

4 < 5, smallest = 4

No Swap

1 2 3 4 5

Finally,

the sorted list is

1 2 3 4 5

It is used on the principle of divide-and-conquer. Quick sort is an algorithm of choice in many situations as it is not difficult to implement. It is a good general purpose sort and it consumes relatively fewer resources during execution.

Advantages

• It is in-place since it uses only a small auxiliary stack.

• It requires only n (log n) time to sort n items.

• It has an extremely short inner loop.

• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Disadvantages

• It is recursive. Especially, if recursion is not available, the implementation is extremely complicated.

• It requires quadratic (i.e., n2) time in the worst-case.

• It is fragile, i.e. a simple mistake in the implementation can go unnoticed and cause it to perform badly.

Quick sort works by partitioning a given array A[p ... r] into two non-empty sub array A[p ... q] and A[q+1 ... r] such that every key in A[p ... q] is less than or equal to every key in A[q+1 ... r].

Then, the two sub-arrays are sorted by recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is computed as a part of the partitioning procedure.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Note that to sort the entire array, the initial call should be Quick-Sort (A, 1, length[A])

As a first step, Quick Sort chooses one of the items in the array to be sorted as pivot. Then, the array is partitioned on either side of the pivot. Elements that are less than or equal to pivot will move towards the left, while the elements that are greater than or equal to pivot will move towards the right.

Partitioning the Array

Partitioning procedure rearranges the sub-arrays in-place.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Analysis

The worst case complexity of Quick-Sort algorithm is O(n²). However using this technique, in average cases generally we get the output in O(n log n) time.

Radix sort is a small method that many people intuitively use when alphabetizing a large list of names. Specifically, the list of names is first sorted according to the first letter of each name, that is, the names are arranged in 26 classes.

Intuitively, one might want to sort numbers on their most significant digit. However, Radix sort works counter-intuitively by sorting on the least significant digits first. On the first pass, all the numbers are sorted on the least significant digit and combined in an array. Then on the second pass, the entire numbers are sorted again on the second least significant digits and combined in an array and so on.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Analyse

Jede Taste wird einmal für jede Ziffer (oder jeden Buchstaben, wenn die Tasten alphabetisch sind) der längsten Taste gesucht. Daher, wenn der längste Schlüssel hatm Ziffern und es gibt n Schlüssel, Radix Sort hat Ordnung O(m.n).

Wenn wir uns diese beiden Werte ansehen, ist die Größe der Schlüssel im Vergleich zur Anzahl der Schlüssel relativ klein. Wenn wir beispielsweise sechsstellige Schlüssel haben, könnten wir eine Million verschiedene Datensätze haben.

Hier sehen wir, dass die Größe der Schlüssel nicht signifikant ist und dieser Algorithmus von linearer Komplexität ist O(n).

Beispiel

Das folgende Beispiel zeigt, wie die Radix-Sortierung mit sieben dreistelligen Zahlen funktioniert.

Eingang	1 st Pass	2 nd Pass	3 rd Pass
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

Im obigen Beispiel ist die erste Spalte die Eingabe. Die verbleibenden Spalten zeigen die Liste nach aufeinanderfolgenden Sortierungen an immer wichtigeren Stellen. Der Code für die Radix-Sortierung setzt voraus, dass jedes Element in einem Array enthalten istA von n Elemente hat d Ziffern, wo Ziffer 1 ist die niedrigste Ziffer und d ist die Ziffer höchster Ordnung.

Klasse verstehen P und NPZuerst sollten wir das Rechenmodell kennen. Daher werden wir in diesem Kapitel zwei wichtige Rechenmodelle diskutieren.

Deterministische Berechnung und die Klasse P.

Deterministische Turingmaschine

Eines dieser Modelle ist eine deterministische Einband-Turingmaschine. Diese Maschine besteht aus einer endlichen Zustandssteuerung, einem Lese- / Schreibkopf und einem Zweiwegeband mit unendlicher Sequenz.

Es folgt das schematische Diagramm einer deterministischen Einband-Turingmaschine.

Ein Programm für eine deterministische Turingmaschine gibt die folgenden Informationen an:

• Ein endlicher Satz von Bandsymbolen (Eingabesymbole und ein leeres Symbol)
• Eine endliche Menge von Zuständen
• Eine Übergangsfunktion

Wenn in der algorithmischen Analyse ein Problem in Polynomzeit durch eine deterministische Einband-Turing-Maschine lösbar ist, gehört das Problem zur P-Klasse.

Nichtdeterministische Berechnung und die Klasse NP

Nichtdeterministische Turingmaschine

Ein weiteres Modell zur Lösung des Rechenproblems ist die nicht deterministische Turingmaschine (NDTM). Die Struktur von NDTM ähnelt der von DTM, hier haben wir jedoch ein zusätzliches Modul, das als Schätzmodul bekannt ist und einem Nur-Schreib-Kopf zugeordnet ist.

Es folgt das schematische Diagramm.

Wenn das Problem durch eine nicht deterministische Turing-Maschine in Polynomzeit lösbar ist, gehört das Problem zur NP-Klasse.

In einem ungerichteten Diagramm a cliqueist ein vollständiger Untergraph des gegebenen Graphen. Vollständiger Untergraph bedeutet, dass alle Scheitelpunkte dieses Untergraphen mit allen anderen Scheitelpunkten dieses Untergraphen verbunden sind.

Das Max-Clique-Problem ist das Rechenproblem beim Finden der maximalen Clique des Graphen. Max Clique wird in vielen realen Problemen eingesetzt.

Betrachten wir eine Social-Networking-Anwendung, bei der Eckpunkte das Profil von Personen darstellen und die Kanten die gegenseitige Bekanntschaft in einem Diagramm darstellen. In diesem Diagramm repräsentiert eine Clique eine Untergruppe von Personen, die sich alle kennen.

Um eine maximale Clique zu finden, kann man systematisch alle Teilmengen untersuchen, aber diese Art der Brute-Force-Suche ist für Netzwerke mit mehr als ein paar Dutzend Eckpunkten zu zeitaufwändig.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Analyse

Das Max-Clique-Problem ist ein nicht deterministischer Algorithmus. In diesem Algorithmus versuchen wir zunächst, eine Menge von zu bestimmenk verschiedene Scheitelpunkte und dann versuchen wir zu testen, ob diese Scheitelpunkte einen vollständigen Graphen bilden.

Es gibt keinen zeitdeterministischen Polynomalgorithmus, um dieses Problem zu lösen. Dieses Problem ist NP-vollständig.

Beispiel

Schauen Sie sich die folgende Grafik an. Hier bildet der Untergraph mit den Eckpunkten 2, 3, 4 und 6 einen vollständigen Graphen. Daher ist dieser Untergraph aclique. Da dies das maximal vollständige Unterdiagramm des bereitgestellten Diagramms ist, ist es a4-Clique.

Eine Scheitelpunktabdeckung eines ungerichteten Graphen G = (V, E) ist eine Teilmenge von Eckpunkten V^' ⊆ V so dass, wenn Kante (u, v) ist eine Kante von Gdann auch nicht u im V oder v im V^' oder beides.

Suchen Sie eine Scheitelpunktabdeckung mit maximaler Größe in einem bestimmten ungerichteten Diagramm. Diese optimale Scheitelpunktabdeckung ist die Optimierungsversion eines NP-vollständigen Problems. Es ist jedoch nicht allzu schwer, eine nahezu optimale Scheitelpunktabdeckung zu finden.

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

Beispiel

Die Kantenmenge des angegebenen Diagramms ist -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

Nun wählen wir zunächst eine beliebige Kante (1,6) aus. Wir eliminieren alle Kanten, die entweder auf Scheitelpunkt 1 oder 6 fallen, und fügen der Abdeckung eine Kante (1,6) hinzu.

Im nächsten Schritt haben wir zufällig eine andere Kante (2,3) ausgewählt

Nun wählen wir eine andere Kante (4,7).

Wir wählen eine andere Kante (8,5).

Daher ist die Scheitelpunktabdeckung dieses Graphen {1,2,4,5}.

Analyse

Es ist leicht zu erkennen, dass die Laufzeit dieses Algorithmus ist O(V + E), unter Verwendung der Adjazenzliste zur Darstellung E^'.

In der Informatik werden viele Probleme gelöst, bei denen das Ziel darin besteht, einige Werte zu maximieren oder zu minimieren, während wir bei anderen Problemen versuchen, herauszufinden, ob es eine Lösung gibt oder nicht. Daher können die Probleme wie folgt kategorisiert werden:

Optimierungsproblem

Optimierungsprobleme sind solche, bei denen das Ziel darin besteht, einige Werte zu maximieren oder zu minimieren. Zum Beispiel,

• Ermitteln der Mindestanzahl von Farben, die zum Färben eines bestimmten Diagramms erforderlich sind.

• Finden des kürzesten Pfades zwischen zwei Eckpunkten in einem Diagramm.

Entscheidungsproblem

Es gibt viele Probleme, für die die Antwort Ja oder Nein lautet. Diese Arten von Problemen werden als bezeichnet decision problems. Zum Beispiel,

• Gibt an, ob ein bestimmtes Diagramm nur mit 4 Farben eingefärbt werden kann.

• Das Finden des Hamilton-Zyklus in einem Diagramm ist kein Entscheidungsproblem, während das Überprüfen eines Diagramms ein Hamilton-Problem ist oder nicht.

Was ist Sprache?

Jedes Entscheidungsproblem kann nur zwei Antworten haben, ja oder nein. Daher kann ein Entscheidungsproblem zu einer Sprache gehören, wenn es für eine bestimmte Eingabe die Antwort "Ja" liefert. Eine Sprache ist die Gesamtheit der Eingaben, für die die Antwort Ja lautet. Die meisten der in den vorherigen Kapiteln beschriebenen Algorithmen sindpolynomial time algorithms.

Für die Eingabegröße n, wenn die Worst-Case-Zeitkomplexität eines Algorithmus ist O(n^k), wo k ist eine Konstante, der Algorithmus ist ein Polynomzeitalgorithmus.

Algorithmen wie Matrixkettenmultiplikation, kürzester Pfad aus einer Quelle, kürzester Pfad aller Paare, minimaler Spanning Tree usw. werden in Polynomzeit ausgeführt. Es gibt jedoch viele Probleme, wie z. B. reisende Verkäufer, optimale Farbgebung der Diagramme, Hamilton-Zyklen, Finden des längsten Pfades in einer Grafik und Erfüllen einer Booleschen Formel, für die keine Polynomzeitalgorithmen bekannt sind. Diese Probleme gehören zu einer interessanten Klasse von Problemen, die alsNP-Complete Probleme, deren Status unbekannt ist.

In diesem Zusammenhang können wir die Probleme wie folgt kategorisieren:

P-Klasse

Die Klasse P besteht aus den Problemen, die in Polynomzeit lösbar sind, dh diese Probleme können rechtzeitig gelöst werden O(n^k) im schlimmsten Fall, wo k ist konstant.

Diese Probleme werden genannt tractable, während andere genannt werden intractable or superpolynomial.

Formal ist ein Algorithmus ein Polynomzeitalgorithmus, wenn ein Polynom existiert p(n) so dass der Algorithmus jede Instanz der Größe lösen kann n in einer Zeit O(p(n)).

Problem erforderlich Ω(n⁵⁰) Zeit zu lösen sind im Wesentlichen für große unlösbar n. Der bekannteste Polynomzeitalgorithmus läuft zeitlich abO(n^k) für ziemlich niedrigen Wert von k.

Die Vorteile bei der Betrachtung der Klasse der Polynom-Zeit-Algorithmen sind, dass alle vernünftig sind deterministic single processor model of computation kann mit höchstens einem Polynom slow-d aufeinander simuliert werden

NP-Klasse

Die Klasse NP besteht aus den Problemen, die in der Polynomzeit überprüfbar sind. NP ist die Klasse von Entscheidungsproblemen, für die es einfach ist, die Richtigkeit einer behaupteten Antwort mit Hilfe einiger zusätzlicher Informationen zu überprüfen. Daher fragen wir nicht nach einer Möglichkeit, eine Lösung zu finden, sondern nur, um zu überprüfen, ob eine angebliche Lösung wirklich korrekt ist.

Jedes Problem in dieser Klasse kann durch umfassende Suche in exponentieller Zeit gelöst werden.

P gegen NP

Jedes Entscheidungsproblem, das durch einen deterministischen Polynomzeitalgorithmus lösbar ist, ist auch durch einen nichtdeterministischen Polynomzeitalgorithmus lösbar.

Alle Probleme in P können mit Polynomzeitalgorithmen gelöst werden, während alle Probleme in NP - P unlösbar sind.

Es ist nicht bekannt, ob P = NP. In NP sind jedoch viele Probleme mit der Eigenschaft bekannt, dass, wenn sie zu P gehören, bewiesen werden kann, dass P = NP ist.

Wenn P ≠ NPgibt es Probleme in NP, die weder in P noch in NP-Complete sind.

Das Problem gehört zur Klasse Pwenn es einfach ist, eine Lösung für das Problem zu finden. Das Problem gehört dazuNP, wenn es einfach ist, eine Lösung zu überprüfen, deren Suche möglicherweise sehr mühsam war.

Stephen Cook stellte in seiner Arbeit „The Complexity of Theorem Proving Procedures“ vier Theoreme vor. Diese Sätze sind unten angegeben. Wir verstehen, dass in diesem Kapitel viele unbekannte Begriffe verwendet werden, aber wir haben keinen Spielraum, um alles im Detail zu diskutieren.

Es folgen die vier Sätze von Stephen Cook -

Satz-1

Wenn ein Satz S von Strings wird dann von einer nicht deterministischen Turing-Maschine innerhalb der Polynomzeit akzeptiert S ist P-reduzierbar auf {DNF-Tautologien}.

Satz-2

Die folgenden Sätze sind paarweise P-reduzierbar (und haben daher jeweils den gleichen Polynom-Schwierigkeitsgrad): {Tautologien}, {DNF-Tautologien}, D3, {Subgraphenpaare}.

Satz 3

• Für jeden T_Q(k) vom Typ Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ ist unbegrenzt

• Da ist ein T_Q(k) vom Typ Q so dass $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

Satz-4

Wenn die Menge S von Strings von einer nicht deterministischen Maschine innerhalb der Zeit akzeptiert wird T(n) = 2ⁿ, und wenn T_Q(k) ist eine ehrliche (dh in Echtzeit zählbare) Funktion des Typs Qdann gibt es eine Konstante K, damit S kann von einer deterministischen Maschine innerhalb der Zeit erkannt werden T_Q(K8ⁿ).

• Zunächst betonte er die Bedeutung der Reduzierbarkeit der Polynomzeit. Dies bedeutet, dass bei einer Polynomzeitverkürzung von einem Problem zum anderen sichergestellt wird, dass jeder Polynomzeitalgorithmus aus dem zweiten Problem in einen entsprechenden Polynomzeitalgorithmus für das erste Problem konvertiert werden kann.

• Zweitens konzentrierte er sich auf die Klasse NP von Entscheidungsproblemen, die in Polynomzeit von einem nicht deterministischen Computer gelöst werden können. Die meisten unlösbaren Probleme gehören zu dieser Klasse, NP.

• Drittens hat er bewiesen, dass ein bestimmtes Problem in NP die Eigenschaft hat, dass jedes andere Problem in NP polynomiell darauf reduziert werden kann. Wenn das Erfüllbarkeitsproblem mit einem Polynomzeitalgorithmus gelöst werden kann, kann jedes Problem in NP auch in Polynomzeit gelöst werden. Wenn ein Problem in NP unlösbar ist, muss das Erfüllbarkeitsproblem unlösbar sein. Somit ist das Erfüllbarkeitsproblem das schwierigste Problem bei NP.

• Viertens schlug Cook vor, dass andere Probleme in NP mit dem Erfüllbarkeitsproblem dieser Eigenschaft, das härteste Mitglied von NP zu sein, teilen könnten.

Ein Problem ist in der Klasse NPC, wenn es in NP ist und wie ist hardwie jedes Problem in NP. Ein Problem istNP-hard wenn alle Probleme in NP polynomial sind, kann die Zeit darauf reduziert werden, obwohl es möglicherweise nicht in NP selbst ist.

Wenn für eines dieser Probleme ein Polynomzeitalgorithmus existiert, wären alle Probleme in NP polynomialzeitlösbar. Diese Probleme werden genanntNP-complete. Das Phänomen der NP-Vollständigkeit ist sowohl aus theoretischen als auch aus praktischen Gründen wichtig.

Definition der NP-Vollständigkeit

Eine Sprache B ist NP-complete wenn es zwei Bedingungen erfüllt

• B ist in NP

• Jeder A in NP ist die Polynomzeit auf reduzierbar B.

Wenn eine Sprache die zweite Eigenschaft erfüllt, aber nicht unbedingt die erste, die Sprache B ist bekannt als NP-Hard. Informell ein SuchproblemB ist NP-Hard wenn es welche gibt NP-Complete Problem A das Turing reduziert sich auf B.

Das Problem in NP-Hard kann erst in Polynomzeit gelöst werden P = NP. Wenn sich herausstellt, dass es sich bei einem Problem um einen NPC handelt, müssen Sie keine Zeit damit verschwenden, einen effizienten Algorithmus dafür zu finden. Stattdessen können wir uns auf den Entwurfsnäherungsalgorithmus konzentrieren.

NP-vollständige Probleme

Es folgen einige NP-Complete-Probleme, für die kein Polynomzeitalgorithmus bekannt ist.

• Bestimmen, ob ein Graph einen Hamilton-Zyklus hat
• Bestimmen, ob eine Boolesche Formel erfüllt werden kann usw.

NP-harte Probleme

Die folgenden Probleme sind NP-Hard

• Das Problem der Schaltungserfüllbarkeit
• Abdeckung einstellen
• Scheitelpunktabdeckung
• Problem mit dem reisenden Verkäufer

In diesem Zusammenhang werden wir nun diskutieren, dass TSP NP-vollständig ist

TSP ist NP-vollständig

Das Problem der reisenden Verkäufer besteht aus einem Verkäufer und einer Reihe von Städten. Der Verkäufer muss jede der Städte von einer bestimmten Stadt aus besuchen und in dieselbe Stadt zurückkehren. Die Herausforderung des Problems besteht darin, dass der reisende Verkäufer die Gesamtlänge der Reise minimieren möchte

Beweis

Beweisen TSP is NP-CompleteZuerst müssen wir das beweisen TSP belongs to NP. In TSP finden wir eine Tour und überprüfen, ob die Tour jeden Scheitelpunkt einmal enthält. Dann werden die Gesamtkosten der Kanten der Tour berechnet. Schließlich prüfen wir, ob die Kosten minimal sind. Dies kann in Polynomzeit abgeschlossen werden. SoTSP belongs to NP.

Zweitens müssen wir das beweisen TSP is NP-hard. Um dies zu beweisen, besteht eine Möglichkeit darin, dies zu zeigenHamiltonian cycle ≤_p TSP (da wir wissen, dass das Hamilton-Zyklus-Problem NPcomplete ist).

Annehmen G = (V, E) eine Instanz des Hamilton-Zyklus sein.

Daher wird eine Instanz von TSP erstellt. Wir erstellen das komplette DiagrammG^' = (V, E^'), wo

$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$

Somit ist die Kostenfunktion wie folgt definiert:

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$

Nehmen wir nun an, dass ein Hamilton-Zyklus h existiert in G. Es ist klar, dass die Kosten für jede Kante inh ist 0 im G^' wie jede Kante gehört E. Deshalb,h hat Kosten von 0 im G^'. Also wenn graphG hat einen Hamilton-Zyklus, dann Graph G^' hat eine Tour von 0 Kosten.

Umgekehrt gehen wir davon aus G^' hat eine Tour h^' von Kosten höchstens 0. Die Kosten für Kanten inE^' sind 0 und 1per Definition. Daher muss jede Kante Kosten von haben0 als die Kosten von h^' ist 0. Wir schließen daraush^' enthält nur Kanten in E.

Das haben wir bewiesen G hat einen Hamilton-Zyklus, wenn und nur wenn G^' hat höchstens eine Kostenreise 0. TSP ist NP-vollständig.

Die in den vorherigen Kapiteln beschriebenen Algorithmen werden systematisch ausgeführt. Um das Ziel zu erreichen, müssen ein oder mehrere zuvor untersuchte Pfade zur Lösung gespeichert werden, um die optimale Lösung zu finden.

Für viele Probleme ist der Weg zum Ziel irrelevant. Zum Beispiel müssen wir uns beim N-Queens-Problem nicht um die endgültige Konfiguration der Königinnen sowie um die Reihenfolge kümmern, in der die Königinnen hinzugefügt werden.

Berg steigen

Hill Climbing ist eine Technik zur Lösung bestimmter Optimierungsprobleme. Bei dieser Technik beginnen wir mit einer suboptimalen Lösung und die Lösung wird wiederholt verbessert, bis einige Bedingungen maximiert sind.

Die Idee, mit einer suboptimalen Lösung zu beginnen, wird mit dem Starten vom Fuß des Hügels aus verglichen. Das Verbessern der Lösung wird mit dem Gehen auf dem Hügel verglichen, und schließlich wird das Maximieren einiger Bedingungen mit dem Erreichen der Spitze des Hügels verglichen.

Daher kann die Bergsteigertechnik als die folgenden Phasen betrachtet werden:

• Konstruieren einer suboptimalen Lösung unter Berücksichtigung der Einschränkungen des Problems
• Schritt für Schritt die Lösung verbessern
• Verbesserung der Lösung, bis keine Verbesserung mehr möglich ist

Die Hill Climbing-Technik wird hauptsächlich zur Lösung rechenintensiver Probleme verwendet. Es wird nur der aktuelle Zustand und der unmittelbare zukünftige Zustand betrachtet. Daher ist diese Technik speichereffizient, da sie keinen Suchbaum verwaltet.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Iterative Verbesserung

Bei der iterativen Verbesserungsmethode wird die optimale Lösung erreicht, indem bei jeder Iteration Fortschritte in Richtung einer optimalen Lösung erzielt werden. Diese Technik kann jedoch auf lokale Maxima stoßen. In dieser Situation gibt es keinen nahe gelegenen Staat für eine bessere Lösung.

Dieses Problem kann durch verschiedene Methoden vermieden werden. Eine dieser Methoden ist das simulierte Tempern.

Zufälliger Neustart

Dies ist eine weitere Methode zur Lösung des Problems der lokalen Optima. Diese Technik führt eine Reihe von Suchen durch. Jedes Mal beginnt es mit einem zufällig generierten Ausgangszustand. Daher können Optima oder nahezu optimale Lösungen erhalten werden, wenn die Lösungen der durchgeführten Suchen verglichen werden.

Probleme der Bergsteigertechnik

Lokale Maxima

Wenn die Heuristik nicht konvex ist, kann Hill Climbing zu lokalen Maxima anstelle von globalen Maxima konvergieren.

Grate und Gassen

Wenn die Zielfunktion einen schmalen Grat erzeugt, kann der Kletterer den Grat nur im Zick-Zack-Verfahren besteigen oder die Gasse hinuntersteigen. In diesem Szenario muss der Kletterer sehr kleine Schritte unternehmen, die mehr Zeit benötigen, um das Ziel zu erreichen.

Plateau

Ein Plateau tritt auf, wenn der Suchraum flach oder ausreichend flach ist, so dass der von der Zielfunktion zurückgegebene Wert aufgrund der von der Maschine zur Darstellung ihres Werts verwendeten Genauigkeit nicht von dem für nahegelegene Regionen zurückgegebenen Wert zu unterscheiden ist.

Komplexität der Bergsteigertechnik

Diese Technik leidet nicht unter weltraumbezogenen Problemen, da sie nur den aktuellen Status betrachtet. Zuvor erkundete Pfade werden nicht gespeichert.

Für die meisten Probleme bei der Random-Restart-Hill-Climbing-Technik kann eine optimale Lösung in Polynomzeit erreicht werden. Bei NP-Complete-Problemen kann die Rechenzeit jedoch basierend auf der Anzahl der lokalen Maxima exponentiell sein.

Anwendungen der Bergsteigertechnik

Die Hill Climbing-Technik kann verwendet werden, um viele Probleme zu lösen, bei denen der aktuelle Status eine genaue Bewertungsfunktion ermöglicht, wie z. B. Netzwerkfluss, Problem des Handlungsreisenden, 8-Queens-Problem, Entwurf integrierter Schaltkreise usw.

Hill Climbing wird auch in induktiven Lernmethoden eingesetzt. Diese Technik wird in der Robotik zur Koordination zwischen mehreren Robotern in einem Team verwendet. Es gibt viele andere Probleme, bei denen diese Technik verwendet wird.

Beispiel

Diese Technik kann angewendet werden, um das Problem des Handlungsreisenden zu lösen. Zunächst wird eine erste Lösung festgelegt, die alle Städte genau einmal besucht. Daher ist diese anfängliche Lösung in den meisten Fällen nicht optimal. Auch diese Lösung kann sehr schlecht sein. Der Hill Climbing-Algorithmus beginnt mit einer solchen anfänglichen Lösung und verbessert sie iterativ. Schließlich wird wahrscheinlich eine viel kürzere Route erhalten.