Backtracking

Grundsätzliches Prinzip

Backtracking arbeitet grundsätzlich nach dem Trial-and Error printzip. Es wird also so lange nach einer Lösung gesucht, bis sie gefunden wird. Wenn abzusehen ist, dass der aktuelle Lösungsweg nicht zur Lösung führen wird, wird ein Schritt zurück gegangen und nach einer alterantiven Lösung gesucht. Am einfachsten werden Backtracking …

Komplexität

Mitschriften aus dem Unterricht

Komplexitaet von suchen

• gegeben ist ein feld mit n elementen
• Benchmarking ist nicht aussagekräftig
  • Nicht die Algorithmen, sondern die Umgebung (Computer, architektur, betriebssystem, etc.) wird dabei betrachtet
• Besser ist die Betrachtung in Einzelschritten des Algorithmus
  • Bestimmung in abstrakter Zeiteinheit
  • Unabhängig von environment

Beispiel anhand der Schritte …

Suche

Lineare Suche

Bei der Linearen Suche wird über jedes Element in der Liste gelaufen und mit dem gesuchten Element verglichen. Wenn die Elemente gleich sind, wird der Index zurück gegeben. Wenn kein Element gefunden wird, wird -1 zurück gegeben.

Sortieren

Sortierverfahren

Selection Sort

Es gibt das min und das max selection sort verfahren. Beim Min-Selection sort wird immer aus einem unsortierten bereich das minimum herausgesucht und dann als letztes Element der sortierten Menge angefügt.

Struktogram

Java Implementierung

public static void minSort(int[] a)
{
    for (int iUnsorted = 0; iUnsorted < a …

Rekursion

Rekursion

Eine Prozedur teilt ein Problem auf indem es sich immer wieder selbstaufruft, bis es zu einer einfachen Lösung kommt. Eine rekursive Berechnung geht von dem zu berechnenden Folgeglied aus und berechnet von dort ausgehend immer weitere Folgeglieder.

Rekursionsschreibweise:

• Basis ist der startpunkt
  • z.B. f(0)=0, f(1 …