Tanz der Kanten

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

Tanz der Kanten ist eine Technik zum effektiven Umgang mit Listen in der Informatik. Sie ermöglicht es auf unkomplizierte Weise, Elemente in Listen zu entfernen oder einzufügen.

Element B wird aus der Liste entfernt.

Zum Beispiel habe das Element B einer Liste den Vorgänger A und den Nachfolger C. Jedes Element habe einen Verweis zu seinem Vorgänger und seinem Nachfolger: Im Falle von B ist A mit B.links und C mit B.rechts erreichbar. Eine typische Operation, um B aus der Liste zu entfernen, ist:


B.links.rechts := B.rechts;
B.rechts.links := B.links;


Das heißt B.links, also A, erhält als Nachfolger das Element, das vorher der Nachfolger seines Nachfolgers war, nämlich C. Entsprechend erhält B.rechts, also C, als Vorgänger A. Von A oder C ausgehend ist nun B nicht mehr zu erreichen. B ist aus der Liste entfernt worden.

Die Idee hinter dem Tanz der Kanten ist nun, dass in B nach dem Entfernen immer noch die Informationen gespeichert sind, um das Entfernen rückgängig zu machen:


B.links.rechts := B;
B.rechts.links := B;


Besonders praktisch ist dieses Prinzip für Backtracking-Algorithmen, die nach dem Prinzip von Versuch und Irrtum einen bestimmten Zustand herstellen, und diesen wieder rückgängig machen müssen, falls er nicht die Lösung des Problems ist.

Diese Technik wurde zuerst 1979 von Hirosi Hitotumatu und Kohei Noshita vorgestellt. Ihren Namen verdankt sie Donald Knuth, den der systematische Wechsel der Verweise an einen Tanz erinnerte. Mit ihrer Hilfe kann man mit dem Dancing-Links-Algorithmus das Problem der exakten Überdeckung lösen.

Literatur[Bearbeiten]

  •  Hirosi Hitotumatu, Kohei Noshita: A technique for implementing backtrack algorithms and its applications. In: Information Processing Letters. 8, Nr. 4, 1979, S. 174-175.
  •  Donald E. Knuth: Dancing links. arXiv:cs/0011047 (Preprint).