Dieser Artikel ist ein kurzer Überblick über verschiedene Algorithmen und wie sie verwendet werden , um Probleme zu lösen. Gute Kenntnisse über Algorithmen haben eine große Hilfe bei meiner Arbeit mit gewesen Programmierung .

Der Artikel besteht aus  Notizen auf Algorithmen aus , wenn ich das gelesen AP Informatik.

Backtracking-Algorithmen

Backtracking-Algorithmen auf Basis von Tiefen erste rekursive Suche – rekursive Strategie.

Backtracking-Algorithmen können beispielsweise verwenden, um diese Probleme zu lösen – TicTacToe, 8 Queens und Sudoku.

Teile und herrsche Algorithmen – Teile und herrsche algorimer

Teile und herrsche Algorithmen teilen das Problem in kleinere Teile und lösen die Subprobleme rekursiv.

Die Lösungen für die Teilprobleme kombiniert werden, dann wird das ursprüngliche Problem gelöst ist.

Ein Algorithmus wird nur Teile und herrsche genannt, wenn es zwei oder mehr rekusive Anruf.

• Merge Sort – Easy Split / beitreten hart
• Schnell Schwarz – Hard Split / join einfach

Mergesort

Merge Art ist eine Teile und Herrsche-Algorithmus, der für die Sortierung verwendet wird. Merge Art teilt das Problem in zwei Teilprobleme bei jedem Schritt. Teilprobleme werden so die Hälfte der Größe des ursprünglichen Problems: O (n log n). Subprobleme ist dann zusammen Merget.

• O (n log n) im schlimmsten Fall und den Durchschnittsfall

Schritte zum Mergesort

1. Teile unsortierte Liste in der Mitte und verschmelzen schwarz jede Hälfte.
2. Kombinieren Sie die zwei sortierten Listen zu einer von ihnen zu verschmelzen.

Lesen Sie mehr über Mergesort hier: https://en.wikipedia.org/wiki/Merge_sort

Schnell Schwarz

Schnell Schwarz ist auch ein Teile und Herrsche-Algorithmus. Quicksort Algorithmus trennt das Array in zwei Unterfelder. Eine teilweise Anordnung von niedrigen Werten und einem Unterarray von hohen Werten. Kurze schwarze Sorten so rekursiv Unteranordnungen.

• O (n ^ 2) im schlimmsten Fall
• O (n log n) im Durchschnitt Fall
• Insgesamt benötigte Zeit auf Neuanordnung des Arrays ausgegeben ist immer O (n)

Schritte in Schnell Schwarz

1. Wählen Sie ein Element aus einem Array. Dieses Element ist ein Schwenk genannt.
2. Ordnen Sie die Elemente im Array – niedrigere Werte vor dem Drehpunkt und höhere Werte für Dreh.
3. Verwenden Sie die oben beschriebenen Schritte wieder rekursiv in kleinere Teilprobleme.

Denken Sie daran, Schnell Schwarz kann auf viele verschiedene Arten in Bezug auf Auswahl der Dreh- und der omrokingen impleteres. Es hat eine große Bedeutung für die Leistung von Quciksort Algorithmus.

Lesen Sie mehr über die Schnell Schwarz hier: https://en.wikipedia.org/wiki/Quicksort

Möchten Sie mehr über Kluft zu wissen und zu erobern Algorithmen, also mehr über binäre Suche, Fibonacci-Zahlen (Türme von Hanoi Problem) zu lesen.

Dynamische Programmieralgorithmen

Ähnlich teile und herrsche (teile und herrsche). Das Problem ist aufgeteilt auf Teilprobleme

Dynamische Programmieralgorithmen speichert die vorherige Antwort / Lösung, die dann verwendet wird, wenn es ein ähnliches Teilproblem erfüllt. Dies bedeutet, dass das gleiche Problem nicht alle immer wieder gelöst werden – daher wieder Computing zu vermeiden.

• Fibonacci-Zahlen in der Informatik
• Fibonacci-Heap
• Fibonacci Suche

Greedy Algorithmen – Greedy Algorithmen

Die Optimierung der Probleme ist, wo Sie finden wollen – nicht nur eine Lösung, sondern die beste Lösung.

Ein Greedy-Algorithmus optimiert das Problem, indem sie immer die beste gegenwärtige Lösung suchen, die dann auf eine Sammlung von Teillösungen zugesetzt wird. Greedy Wahl Eigenschaft – eine lokal optimale Wahl ist global optimal.

• ordentlich
• Kruskal
• Dijkstra (kürzesten Pfad in einem Graphen)
• Brute – Force – Algorithmen
• randomisierten Algorithmen

A * -Algorithmus

A * Algorithmus ist viel in Wegfindung und Graph Traversal verwendet. A * -Algorithmus verwendet Heuristiken in die richtige Richtung zu führen, während sie einen Pfad mit minimalen Kosten bestimmt.

Variante Dijkstra-Algorithmus wird in den Spielen (Wegfindung, 8 Puzzle), die üblicherweise anveldt.

A * berechnet die Funktion

f (v) = g (v) + h (v)

g (v) = tatsächlichen Kosten des Wegs vom Startpunkt zum Scheitelpunkt v.

h (v) = heuristische Foreca Kosten von Knoten v zum Ziel