1.) Vorstellung des Problems:
|
Gegeben: |
|
|
Eine (lineare) Liste von Elementen |
|
|
(im Allgemeinen ist die Liste nicht sortiert) |
|
|
(Anschaulich: ein Karteikasten mit unsortierten Karteikarten) |
|
|
Aufgabe: |
|
|
Suche ein bestimmtes Element (bzw. eine Folge von Elementen) in möglichst minimaler Zeit/Kosten |
|
|
(worst-case: die gesamte Liste muss durchsucht werden) |
|
|
Offline Lösung: |
|
|
(Anfragefolge bekannt) |
Die Elemente werden ihrer Häufigkeit entsprechend (oft - > wenig) angeordnet |
|
und die Liste wird immer linear von vorne nach hinten durchsucht. |
|
|
(weiter unten folgt noch ein kleines Beispiel) |
|
|
Anm.: |
- der Algorithmus ist nicht optimal ! |
|
Problem: |
|
|
Meist sind die Anfragelisten/folgen nicht bekannt. |
|
|
(zumindest bei Online-Lösungen, um die es mir hier geht) |
|
|
=> |
Man benötigt Algorithmen die nach jedem Zugriff auf ein Element, die Liste so verändern, |
|
dass eine zukünftige Suche nach dem Element schneller geht. |
|
|
=> |
Mehrere Algorithmen um das Problem zu lösen |
|
Anm.: |
die Listen sind i. Allg. unsortiert und können sequentiell oder verkettet gespeichert werden. |
|
Drei Strategien sind hierbei die am häufigst benutzten und untersuchten: |
|
|
- Die MF-, die T- und die FC-Regel. |
|
|
(die meisten andern Online Algorithmen sind Variationen dieser 3 Strategien) |
|
Kosten |
|
|
(für den Zugriff auf ein Element) |
- Um ein Element an Stelle i zu finden entstehen Kosten von i. |
|
- in denen der Aufwand des Umsortierens mit enthalten ist |
|
- X(i) = kostenpflichtige Vertauschung von i |
|
- ein Element wird nach dem Zugriff und dem dazugehörigen Umsortieren um einen Platz nach hinten geschoben |
|
- F(i) = kostenfreie Vertauschung von i |
|
- ein Element wird nach dem Zugriff und dem dazugehörigen Umsortieren um einen Platz nach vorne geschoben |
|
( für eine Offline-Lösung) |
|
|
Gegeben: |
- 7 Elemente mit den Beschriftungen 1 bis 7 |
|
- die Elemente sind der Reihe nach geordnet: 1,2,3,4,5,6,7 |
|
|
- die Anfragen Folge1: ruft 10mal nacheinander 1 bis 7 auf |
|
|
- die Anfragen Folge2: ruft 10mal 1, dann 10mal 2,...,dann 10mal die 7 auf |
|
|
=> Häufigkeiten bei Folge 1: alle Zahlen haben Häufigkeit 10 |
|
|
=> Häufigkeiten bei Folge 2: alle Zahlen haben Häufigkeit 10 |
|
Der Offline-Algorithmus ordnet die Liste also nun folgendermaßen: |
1,2,3,4,5,6,7 |
|
(für beide Folgen) |
(da die Reihefolge egal ist, da alle Häufigkeiten gleich sind, ändert er sie nicht) |
|
und erhält so die Kosten: |
280 = (1+2+3+4+5+6+7)*10 bzw. (1*10+2*10+3*10+4*10+5*10+6*10+7*10) |
|
(als durchschnittliche Kosten pro Zug hat man also nur Kosten von 4 bei jeder der Folgen) |
Anm.: Es ist noch kein optimaler Algorithmus gefunden worden, und der bis dato schnellste offline Algorithmus hat eine Laufzeit von O(2n n! m).
(zum Inhaltsverzeichnis, zum selben Beispiel gelöst mit der MF-Regel und der T-Regel.)