Tanz der Kanten

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

• 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).