https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Tanz_der_Kanten 2026-06-21T18:24:40Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Tanz_der_Kanten&diff=454403&oldid=prev 2021-03-30T08:16:01Z

<p>Vorlagen-fix (arXiv)</p> <p><b>Neue Seite</b></p><div>&#039;&#039;&#039;Tanz der Kanten&#039;&#039;&#039; ist eine Technik zum effektiven Umgang mit [[Liste (Datenstruktur)|Listen]] in der [[Informatik]]. Sie ermöglicht es auf unkomplizierte Weise, Elemente in Listen zu entfernen oder einzufügen.<br /> <br /> [[Datei:DancingLinks.png|mini|Element B wird aus der Liste entfernt.]]<br /> <br /> 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 &#039;&#039;B&#039;&#039; aus der Liste zu entfernen, ist:<br /> <br /> B.links.rechts := B.rechts;<br /> B.rechts.links := B.links;<br /> <br /> 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.<br /> <br /> 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:<br /> <br /> B.links.rechts := B;<br /> B.rechts.links := B;<br /> <br /> Besonders praktisch ist dieses Prinzip für [[Backtracking]]-[[Algorithmus|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.<br /> <br /> 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.<br /> <br /> == Literatur ==<br /> <br /> * {{Literatur |Autor=Hirosi Hitotumatu, Kohei Noshita |Titel=A technique for implementing backtrack algorithms and its applications |Sammelwerk=Information Processing Letters |Band=8 |Nummer=4 |Datum=1979 |Seiten=174-175 |Sprache=en}}<br /> * {{Literatur |Autor=Donald E. Knuth |Titel=Dancing links |Datum=2000-11-15 |Kommentar=Preprint |Sprache=en |arXiv=cs/0011047}}<br /> <br /> [[Kategorie:Algorithmus]]</div>

imported>Crazy1880