Algorithms
Sortieralgorithmen
| Name | Avg. case | Worst case | Stabil | Extra Speicher Befarf | Idee |
|---|---|---|---|---|---|
| Bubblesort | O(n^2) | O(n^2) | Ja | kein extra Speicher | bubbelt in jedem Durchlauf ein Element an seinen endgültigen Platz. |
| Mergesort | O(n*log(n) | O(n*log(n) | Ja | kein extra Speicher, O(n) oder O(n*log(n) | Die Liste wird immer wird halbiert bis man nur noch Listen der Größe 1 hat, dann werden die Listen wieder zusammengemischt. Worst Case ist schneller als Quicksort, in der Praxis ist Quicksort aber meist schneller. |
| Quicksort | O(n*log(n) | O(n^2) | Nein | O(n*log(n)) für Stack | Man wählt Pivotelement aus der Liste aus, findet alle Elemente kleiner gleich Pivotelement, das Pivotlement, alle Elemente größer als das Pivotelement. Die linke und rechte Liste müssen dann rekursiv ebenfalls sortiert werden. Wichtig ist ein geschicktes Pivotelement zu nehmen, z.B. ein zufälliges. |
| Heapsort | O(n*log(n) | O(n^2) | Nein | kein extra Speicher | Man erst mal einen http://de.wikipedia.org/wiki/Bin%C3%A4rer_Heap, alle Knoten sind kleiner (größer) als ihre Kinder. Das kostet O(n). Jetzt nimmt man immer die Wurzel raus, sie ist das kleinste (größte) Element und schiebt ein anderes Element in die Wurzel. Jetzt muss man die Heap Eigenschaft wiederherstellen. Das kostet O(log(n)). |
| AVL-Baum | O(n*log(n) | O(n*log(n) | Ja | O(n) | Ein Baum, in den Knoten stehen die Werte, die linken Söhne sind kleiner als der Knoten, der rechten größer. Für jeden Knoten gilt, die Tiefe des linken und rechten Teilbaums ist maximal um 1 unterschiedlich sonst wird durch umhängen dieser Zustand hergestellt. Der Baum kann in O(n) traversiert werden. Einfügen kostet höchstens O(log n). |
Graphen
Dijkstra
Ein Graph, mit postiv gewichteten Kanten. Für einen Startknoten wird der kürzeste Weg zu allen anderen Knoten gefunden. Alle Knoten erhalten die Eigenschaft Distanz (Initialisiert mit unendlich) und Vorgänger (initialisiert mit null). Der Startknoten erhält die Distanz 0. Es wird immer als nächstes der Knoten besucht, der
- noch nicht besucht wurde
- dessen bisherige Distanz am kleinsten ist
Wenn ein Knoten besucht wird, dann
- wird er als besucht markiert
- berechne die Distanz zu uns + Kante zu unserem Sohn. Ist dieser Wert < als der bisherige Distanzwert zu unserem Sohn aktualisiere dessen Distanz.
Der Algorithmus profiert davon, wenn man effizient denjenigen Knoten ermitteln kann, dessen bisherige Distanz am kleinsten ist. Siehe Prioritätswarteschlange. Diese benötigt eine decrease key Methode, für den Fall dass man einen kürzeren Weg für einen Knoten findet. Falls man keinen zur Verfügung hat, kann man notfalls auch den Knoten erneut, mit einer kürzeren Distanz, einfügen. Dieser wird dann zuerst entnommen, die anderen Knoten sind dann bereits markiert wenn sie an die Reihe kommen. Das macht natürlich die Operationen auf der Warteschlange teuerer, weil sie voller wird. Laufzeit (wenn man einen Fibonacci-Heap benutz ist O(Knoten*log(Knoten+Kanten)).
A* Algorithmus
A* Algorithmus Wenn man die Nachbarknoten eines Knotens hinzufügt, berechnet man: Distanz bis zum Knoten + Distanz zum Nachbarknoten + Geschätze Distanz vom Nachbarknoten bis zum Ziel. Dadurch versucht man zu verhindern, dass man als nächstes Knoten besucht, die zwar nahe an guten Knoten liegen, aber nicht in Richtung Ziel. Die Luftlinie ist z.B. eine gute Schätzfunktion.
Bellman-Ford-Algorithmus
Berechnet wie Dijkstra von einem Knoten zu allen anderen Knoten den kürzesten Weg, wobei auch negative Kanten erlaubt sind, negative Zyklen können erkannt werden. Laufzeit O(Knoten*Kanten) oder O(Knoten*Knoten*Kanten) wenn man von allen Knoten zu allen Knoten den kürzesten Weg sucht. Idee: Nimmt wiederholt alle Kanten u nach v, untersuche Distanz nach u + Kosten Kante u nach v. Ist das kleiner als die Distanz zu v dann verbessert diese Kante den Weg nach v.
Floyd-Warshall-Algorithmus
Floyd
Berechnet den kürzesten Weg zwischen allen Knoten eines Graphen. Negative Kanten sind erlaubt, negative Zyklen führen zu einem falschen Ergebnis, können aber erkannt werden. Idee: Wenn der kürzeste Weg an A nach Z über M geht, dann ist sind auch die Teilwege Weg A-M und M-Z bereits optimal. In die Matrix dist[a,b] werden die Kantenkosten von a nach b abgelegt, oder unendlich falls keine direkte Kante existiert.
for(int a=0; a<MAX; a++)
for(int b=0; b<MAX; b++)
dist[a,b]:=min(dist[a,b], dist[a,k], dist[k, j]);
Für jeden Knoten k wird also untersucht, ob es den Weg von a nach b (für alle a,b) verbessert (oder erst ermöglicht), wenn man für a-b erst von a nach k und dann von k nach b fährt.
Warshall
Wie Flyod, nur dass man sich nur dafür interessiert, ob es einen Weg von a nach b gibt, nicht wie lang der ist. Idee: Falls ein Weg von a nach b existiert und von b nach c, dann gibt es auch einen von a nach c
for(int a=0; a<MAX; a++)
if(connected[a,b])
for(int c=0; c<MAX; c++)
if(connected[b,c])
connected[a,c]:=true;
Ford und Fulkerson
Ford und Fulkerson Der Algorithmus sucht nach dem maximalem Fluß von q nach s in einem Graphen. Jede Kante hat einen maximalen Fluss, eine tatsächlich genutzen Fluss und es gibt noch Residualgraphen (Restegraphen) in dem Gegenkanten eingetragen werden, die anzeigen wieviel vom maximalen Fluss jeder Kante nicht genutzt wird.
Die Levenshtein Distanz
Man hat zwei Zeichenketten, z.B. "Affe" und "Apfel" und möchte ein Maß dafür erhalten, wie ähnlich sich die beiden Zeichenketten sind. Die Levenshtein Distanz liefert die minimale Anzahl an Einfüge-, Lösch- und Ersetzoperationen, um die erste Zeichenkette in die zweite umzuwandeln. Man könnte z.B. mit einer Ersetzung und einer Einfügeoperation "Affe" in "Apfel" umwandeln. Falls beide Operationen mit 1 bewertet würden wäre die Distanz der beiden Zeichenketten dann 2.
In Java
<groupId>org.apache.commons</groupId>
<artifactId>commons-text</artifactId>
<version>1.1</version>
</dependency>
Hier ist ein Beispiel für eine Implementierung der Distanz in Java
*
* http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance
*/
public class LevenshteinDistance
{
private String string1;
private String string2;
private int[][] distMatrix;
private int costAdd=1;
private int costReplace=1;
private int costRemove=1;
/**
* @param pValA int value 1
* @param pValB int value 2
* @param pValC int value 3
* @return the minumum of int value 1-3
*/
private static int getMinimumOfThree(int pValA, int pValB, int pValC)
{
int lMin;
lMin=Math.min(pValA, pValB);
lMin=Math.min(lMin, pValC);
return lMin;
}
/**
* Constructor to get an object to get the Levenshtein distance betweent string 1 and string 2
* @param pString1 String 1
* @param pString2 String 2
* @param pCostAdd Cost for adding a char to string 1 to match string 2
* @param pCostReplace Cost for replacing a char to string 1 to match string 2
* @param pCostRemove Cost for removing a char to string 1 to match string 2
*/
public LevenshteinDistance(String pString1, String pString2, int pCostAdd, int pCostReplace, int pCostRemove)
{
this(pString1, pString2);
if(pCostAdd<0 || pCostReplace <0 || pCostRemove<0) throw new IllegalArgumentException("Negative costs are not allowed");
costAdd=pCostAdd;
costReplace=pCostReplace;
costRemove=pCostRemove;
}
/**
* Constructor to get an object to get the Levenshtein distance betweent string 1 and string 2
* All costs are set to default value 1
* @param pString1 String 1
* @param pString2 String 2
*/
public LevenshteinDistance(String pString1, String pString2)
{
string1=pString1;
string2=pString2;
}
/**
* @return String 1
*/
public String getString1()
{
return string1;
}
/**
* @return String 2
*/
public String getString2() {
return string2;
}
/**
* @return The Levenshtein distance matrix
*/
private int[][] getDistanceMatrix()
{
if(distMatrix==null)
{
distMatrix=this.computeLevenshteinDistance();
}
return distMatrix;
}
/**
* @return What is the minimum distance between string 1 and string 2
*/
public int getMinDistance()
{
int result=this.getDistanceMatrix()[string1.length()][string2.length()];
return result;
}
/**
* @return Show one way to change string 1 into string 2 with the minimum amount of operations
*/
public String getOperations()
{
return findOperationsRec(string1.length(), string2.length());
}
/**
* Find one way to change string 1 into string 2 starting from i,j
* @param i position in string 1
* @param j position in string 2
* @return String with operations
*/
private String findOperationsRec(int i, int j)
{
int left=(i<=0) ? -1 : getDistanceMatrix()[i-1][j];
int top= (j<=0) ? -1 : getDistanceMatrix()[i][j-1];
int here=getDistanceMatrix()[i][j];
int diag=(i<=0 || j<=0) ? -1 :getDistanceMatrix()[i-1][j-1];
// a removal?
if (i>0 && (left) + costRemove == here)
{
return findOperationsRec(i-1, j)+'-';
}
// an addition?
if(j>0 && top + costAdd == here)
{
return findOperationsRec(i, j-1)+'+';
}
// a replacement?
if(i>0 && j>0 && diag + costReplace == here)
{
return findOperationsRec(i-1, j-1)+'r';
}
// if non of the other cases applied, it must have been equal
if(i>0 && j>0 && diag == here)
{
return findOperationsRec(i-1, j-1)+'=';
}
return "";
}
/**
* @return return the calculated Levenshtein distance matrix for string 1 to string 2
*/
private synchronized int[][] computeLevenshteinDistance()
{
int[][] distance = new int[string1.length() + 1][string2.length() + 1];
for (int i = 0; i <= string1.length(); i++)
{
distance[i][0] = i;
}
for (int j = 0; j <= string2.length(); j++)
{
distance[0][j] = j;
}
for (int i = 1; i <= string1.length(); i++)
{
for (int j = 1; j <= string2.length(); j++)
{
int a=distance[i - 1][j] + costRemove;
int b=distance[i][j - 1] + costAdd;
int c=distance[i - 1][j - 1];
if(string1.charAt(i - 1)!=string2.charAt(j - 1))
{
c=c+costReplace;
}
distance[i][j] = getMinimumOfThree(a, b, c);
}
}
return distance;
}
@Override
public String toString()
{
StringBuffer result=new StringBuffer();
result.append(string1);
result.append("n");
result.append(string2);
result.append("n");
int maxNr=0;
for (int i = 1; i <= string1.length(); i++)
{
for (int j = 1; j <= string2.length(); j++)
{
int distval=getDistanceMatrix()[i-1][j-1];
if(maxNr<distval) maxNr=distval;
}
}
for (int i = 1; i <= string1.length(); i++)
{
for (int j = 1; j <= string2.length(); j++)
{
int distval=getDistanceMatrix()[i-1][j-1];
String distvalString=String.valueOf(distval);
while(distvalString.length()<String.valueOf(maxNr).length())
{
distvalString=" "+distvalString;
}
result.append(distvalString);
result.append(" ");
}
result.append("n");
}
result.append("Min Distance:");
result.append(this.getMinDistance());
result.append("n");
result.append("Schritte: ");
result.append(this.getOperations());
result.append("n");
return result.toString();
}
}
Und mit diesem Komparator kann in Java eine Liste von Strings danach sortiert werden, wie ähnlich sie einem vorgegeben String sind.
/**
* Compares two strings vs a reference string. This will tell you
* which of the two strings is more similar to reference string
*
*/
public class LevenshteinDistanceComparator implements Comparator<String>
{
String referenceString;
private int costAdd=1;
private int costReplace=1;
private int costRemove=1;
/**
* @param pReferenceString The reference string
*/
public LevenshteinDistanceComparator(String pReferenceString)
{
referenceString=pReferenceString;
}
/**
* @param pReferenceString The reference string
* @param pCostAdd How expensive should it be if we need to add a character
* @param pCostReplace How expensive should it be if we need to replace a character
* @param pCostRemove How expensive should it be if we need to remove a character
*/
public LevenshteinDistanceComparator(String pReferenceString, int pCostAdd, int pCostReplace, int pCostRemove)
{
this(pReferenceString);
costAdd=pCostAdd;
costReplace=pCostReplace;
costRemove=pCostRemove;
}
/**
* @param pReferenceString The reference string
*/
private int getLevenshteinDistance(String pString)
{
LevenshteinDistance lev=new LevenshteinDistance(referenceString, pString, costAdd, costReplace, costRemove);
int distance=lev.getMinDistance();
return distance;
}
/* (non-Javadoc)
* @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
*/
@Override
public int compare(String o1, String o2)
{
if(o1==null || o2==null) throw new NullPointerException("Can not compare null strings");
Integer dist1=getLevenshteinDistance(o1);
Integer dist2=getLevenshteinDistance(o2);
return dist1.compareTo(dist2);
}
}