Beispiele für ausgefeilte rekursive Algorithmen

14

Ich habe einem Freund den berühmten deterministischen linearen Zeitauswahlalgorithmus (Median des Medianalgorithmus) erklärt.

Die Rekursion in diesem Algorithmus ist (obwohl sehr einfach) ziemlich ausgefeilt. Es gibt zwei rekursive Aufrufe mit jeweils unterschiedlichen Parametern.

Ich habe versucht, andere Beispiele für solche interessanten rekursiven Algorithmen zu finden, konnte aber keine finden. Alle rekursiven Algorithmen, die mir einfallen könnten, sind entweder einfache Schwanzrekursionen oder einfaches Teilen und Erobern (wobei die beiden Aufrufe "gleich" sind).

Können Sie einige Beispiele für anspruchsvolle Rekursionen nennen?

elektronaj
quelle
Das Durchqueren eines Labyrinths oder allgemeiner eines Graphen mit einer Breitensuche ist ein einfaches Beispiel für eine interessante Rekursion.
Ich denke, dass BFS nicht für meine Frage geeignet ist, da es einfach und natürlich mit einer Warteschlange und einer while-Schleife implementiert werden kann.
elektronaj
Was ist mit dem Zurückverfolgen beim Lösen von Rätseln und Parsen? Auch die Algorithmen für Rangfolgen und das Aufheben von Rangfolgen weisen nicht standardmäßige Rekursionen auf.
uli
Memo- Algorithmen?
Kaveh
2
@vzn: Eine Warteschlange kann einen Stapel nicht ersetzen. BFS ist ein Sonderfall.
Raphael

Antworten:

15

Meine Lieblingswiederholung taucht in ausgangssensitiven Algorithmen zur Berechnung konvexer Hüllen auf, zuerst von Kirkpatrick und Seidel , aber später von anderen wiederholt. Es sei die Zeit zum Berechnen der konvexen Hülle von n Punkten in der Ebene, wenn die konvexe Hülle h Eckpunkte hat. (Der Wert von h ist im Voraus nicht bekannt, abgesehen von der trivialen Grenze h n .) Der Kirkpatrick- und Seidel-Algorithmus liefert die Wiederholung T ( n , h ) = { O ( n ) if T(n,h)nhhhn wobein1,n23n/4undn1+n2=nundh1+h2=h.

T(n,h)={Ö(n)wenn n3 oder h3T(n1,h1)+T(n2,h2)+Ö(n)Andernfalls
n1,n23n/4n1+n2=nh1+h2=h

Die Lösung ist . Dies ist ein wenig überraschend, da h nicht der Parameter ist, der gleichmäßig aufgeteilt wird. Tatsächlich tritt der schlimmste Fall der Wiederholung auf, wenn h 1 und h 2 beide ungefähr h / 2 sind ; wenn irgendwie magisch h 1 immer konstant ist, wäre die Lösung T ( n , h ) = O ( n ) .T(n,h)=Ö(nLogh)hh1h2h/2h1T(n,h)=Ö(n)

Ich habe eine Variante dieser Wiederholung in einer meiner ersten Arbeiten zur Computertopologie verwendet : wo

T(n,g)={O(n)if n3 or g=0T(n1,g1)+T(n2,g2)+O(min{n1,n2})otherwise
und g 1 + g 2 = g . Wieder ist die Lösung O ( n log g ) , und derschlimmsteFall tritt auf, wenn sowohl n als auch g immer gleichmäßig aufgeteilt werden.n1+n2=ng1+g2=gO(nlogg)ng
JeffE
quelle
n=O(1)h=O(1)OnhO(1)O(n)
Raphael
1
O(1)31010100!
Wie haben Sie diese Diagramme in den Papieren zur Computertopologie gezeichnet?
user119264
12

Die Rekursion, die ich in meiner Arbeit "Ein linearer Zeitalgorithmus zur Berechnung des Voronoi-Diagramms eines konvexen Polygons" von Aggarwal et al. Verwendet habe, ist ebenfalls ziemlich kompliziert.

n|B|αn|R|βn|C|γnα,β,γ>0

Ich werde Sie herausfinden lassen, warum der gesamte Algorithmus lineare Zeit benötigt.

  1. Teilen Sie die ursprünglichen Punkte in die blauen und roten Sätze B und R.
  2. Berechnen Sie rekursiv die konvexe Hülle der blauen Punkte.
  3. Wählen Sie anhand der Struktur des blauen Rumpfs die purpurroten Punkte C aus.
  4. Fügen Sie die purpurroten Punkte einzeln zum blauen Rumpf hinzu.
  5. Berechnen Sie rekursiv die konvexe Hülle der Granatpunkte G.
  6. Verbinden Sie diesen Granatrumpf mit dem erweiterten blauen Rumpf von Schritt 4.

Was den Algorithmus linear macht, ist die Fähigkeit, einen festen Bruchteil der roten Punkte zu konstanten Kosten pro Punkt zum blauen Rumpf hinzuzufügen. Die hinzugefügten Punkte sind die purpurroten Punkte.

T(n)=T(|B|)+T(|G|)+O(n)
|B||G||B|+|G|(1γ)n
Peter Shor
quelle
7

Es gibt eine Variation des Medianwerts für das Wiederauffinden von Wiederholungen, die bei der Entfernungssuche mit Halbebenen auftreten. Die Wiederholung selbst ist von der Form

T(n)=T(n/2)+T(n/4)+cn
Suresh
quelle
1
Meine Antwort hier ( cs.stackexchange.com/questions/332/… ) hat zufällig genau die gleiche Wiederholung für die Laufzeit :)
Alex ten Brink
6

Es gibt eine Reihe von coolen rekursiven Algorithmen [1], [2] die bei der Vorhersage von RNA-Sekundärstrukturen verwendet werden. Ein RNA-Strang, der sich selbst überlassen bleibt, bildet mit sich selbst Basenpaare. Ein relativ einfaches Beispiel aus [3] berechnet die maximale Anzahl verschachtelter, gepaarter Basen, die ein RNA-String mit sich selbst bilden wird:

M(ich,j)=meinxichk<j-Lmichn{M(ich,k-1)+M(k+1,j-1)+1M(ich,j-1)


  1. Optimale Computerfaltung großer RNA-Sequenzen mit Hilfe von Thermodynamik und Hilfsinformationen von M. Zuker, P. Stiegler (1981)

  2. Ein dynamischer Programmieralgorithmus zur Vorhersage der RNA-Struktur mit Pseudoknoten von E. Rivas, SR Eddy (1999)

  3. Schneller Algorithmus zur Vorhersage der Sekundärstruktur von einzelsträngiger RNA von R. Nussinov, AB Jacobson (1980)

rphv
quelle
Ein verwandter ein Vorschlag hier ist recht kompliziert , da es drei voneinander abhängigen (dynamische Programmierung) Rekursion Sport.
Raphael
4

Ich verstehe immer noch nicht wirklich, was Sie unter "raffinierter Rekursion" verstehen. Zum Beispiel ist der Rekursionsschritt im FFT-Algorithmus komplex!

Wenn Sie jedoch nach einer komplizierteren Rekursion suchen möchten , ist die gegenseitige Rekursion möglicherweise eine mögliche Antwort. Die gegenseitige Rekursion ist nützlich, wenn Sie mit funktionalen Programmiersprachen arbeiten . Die gegenseitige Rekursion ist das Hauptmerkmal von Parsern für rekursive Abstammung .

Dai
quelle
Nun, die Rekursion in FFT (einfachste Form von Cooley-Tukey) ist "Standard" Teilen und Erobern. Dies ergibt sich aus der Komplexität von O (nlogn). Die 2 rekursiven Aufrufe (1 für die gerade, 1 für die Chancen) sind etwas "gleich".
elektronaj
3

Die McCarthy 91 funktioniert auf Anhieb

F(N) = 
    n - 100    if n > 100
    F(F(n+11)) if n <= 100

und die Ackermann-Funktion

A(m, n) = 
    n + 1             if m = 0
    A(m-1, 1)         if m > 0 and n = 0
    A(m-1, A(m, n-1)) if m > 0 and n > 0

könnte als ungewöhnliche, wenn auch spielzeughafte, rekursive Funktionen gelten.

hugomg
quelle