| dbo:abstract
|
- 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. 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. (de)
- In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Donald Knuth's Algorithm X for the exact cover problem. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku. The name dancing links, which was suggested by Donald Knuth, stems from the way the algorithm works, as iterations of the algorithm cause the links to "dance" with partner links so as to resemble an "exquisitely choreographed dance." Knuth credits Hiroshi Hitotsumatsu and Kōhei Noshita with having invented the idea in 1979, but it is his paper which has popularized it. (en)
- 在计算机科学中, 舞蹈链（Dancing Links), 也叫 DLX, 是由 Donald Knuth 提出的数据结构，目的是快速实现他提出的的 X算法. X算法是一种递归算法，时间复杂度不确定, 深度优先, 通过回溯寻找精确覆盖问题所有可能的解。有一些著名的精确覆盖问题，包括铺砖块，八皇后问题，数独问题。 名字来自于这个算法的工作方式，算法中的迭代让链接与同伴链接"跳舞"，很像“精心编排的舞蹈”。 Knuth 归功于 Hiroshi Hitotsumatsu 与 Kōhei Noshita 在1979的研究 , 但是Knuth的论文让舞蹈链流行。 (zh)
|
| rdfs:comment
|
- 在计算机科学中, 舞蹈链（Dancing Links), 也叫 DLX, 是由 Donald Knuth 提出的数据结构，目的是快速实现他提出的的 X算法. X算法是一种递归算法，时间复杂度不确定, 深度优先, 通过回溯寻找精确覆盖问题所有可能的解。有一些著名的精确覆盖问题，包括铺砖块，八皇后问题，数独问题。 名字来自于这个算法的工作方式，算法中的迭代让链接与同伴链接"跳舞"，很像“精心编排的舞蹈”。 Knuth 归功于 Hiroshi Hitotsumatsu 与 Kōhei Noshita 在1979的研究 , 但是Knuth的论文让舞蹈链流行。 (zh)
- In computer science, dancing links (DLX) is a technique for adding and deleting a node from a circular doubly linked list. It is particularly useful for efficiently implementing backtracking algorithms, such as Donald Knuth's Algorithm X for the exact cover problem. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku. (en)
- 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. 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; B.links.rechts := B;B.rechts.links := B; (de)
|
