![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
танцующие ссылки
Jul. 18th, 2015 12:28 amСЯУ из комментария в Hacker News, что проблему решения судоку можно легко представить в виде частного случая проблемы exact cover. Заодно решил прочитать уже ставшую классической статью Кнута о его алгоритме "танцующих ссылок" для решения проблемы exact cover.
Помню, что мне много лет назад это показалось слишком сложным, и я отложил статью, но теперь не понимаю, почему. На самом деле эти танцующие ссылки не сложны, и действительно очень красивы. Рекомендую к прочтению.
Если в двух словах, то Кнут описывает эффективный подход к написанию поиска с backtracking. Любой, кто писал в том или ином виде backtracking search, знает, что сложность обычно заключается в том, чтобы выбрать правильную репрезентацию данных, так, чтобы добавить следующий выбор, а потом его "откатить назад", было легко. Часто оказывается, что есть трейдофф между быстрым доступом к данным и быстрым изменению/откатыванию их части. Алгоритм Кнута основывается на следующем наблюдении. Если мы удаляем элемент из двойного связанного списка, то сам элемент, вырванный из списка, естественным образом сохраняет в себе - в своих указателях влево/вправо - информацию о том, где он был в списке; и за O(1) времени его можно обратно вставить. Значит, если в процессе backtracking search можно представить "следующий выбор" как удаление элементов из связанных списков, то "откат" - возвращение их в эти списки - получается и очень быстрым, и удобным с точки зрения промежуточных данных: элементы сами помнят, куда их вставлять, не нужно это отдельно никуда записывать.
Это еще не все, есть важные подробности конкретно в случае exact cover о том, в каком порядке удалять/возвращать элементы из списков, но это все можно прочитать в статье. Отличная статья, легко читается.
Мета-замечание: "алгоритм танцующих ссылок" Кнута требует свободного владения указателями! Не в каком-то конкретном языке, а самим понятием указателя. Его можно считать примером того, почему все-таки важно программистам иметь опыт работы с языками, в которых указатели не спрятаны от программиста: не только Питон, но и C++ или хотя бы Джава. Не то чтобы на Питоне невозможно было имплементировать этот алгоритм; нет, можно, но странно и неудобно, потому что нормальный способ работы со списком в Питоне - это, как ни странно, питоновский список, а в нем удаленный элемент не хранит при себе свое место и не может за O(1) вернуть себя на него.
Кто-то написал элегантный код алгоритма Кнута на Питоне, но его можно считать только кодом алгоритма X для решения exact cover, а не питоновским вариантом "танцующих ссылок", вопреки тому, что говорит автор кода. В его коде никакие ссылки не танцуют, а удаление элемента и возвращение его воплощено как удаление/возвращение из питоновского множества, т.е. операция O(logN) на каком-то сбалансированном дереве (полагаю - не знаю точно, как в Питоне внутри устроены множества). С другой стороны, важно отметить, что если это работает для проблем нужного нам масштаба, то и ладно. Еще в начале 90-х, не говоря уж о более ранних эпохах, делать отдельное сбалансированное дерево для каждой строки матрицы было бы безнадежно медленным. Закон Мура быстро, но верно сделал свое дело. Задачи с малым N теперь обычно не требуют элегантных оптимизаций, подобных "танцующим ссылкам"; а задачам с огромным N они все равно часто не помогают, потому что задачи NP-полные и перебор растет экспоненциально. Остается область посредине, где такие техники все еще важны и останутся важными. Нередко интересные задачи оказываются именно там, так что "танцующие ссылки" еще потанцуют, думаю.
Помню, что мне много лет назад это показалось слишком сложным, и я отложил статью, но теперь не понимаю, почему. На самом деле эти танцующие ссылки не сложны, и действительно очень красивы. Рекомендую к прочтению.
Если в двух словах, то Кнут описывает эффективный подход к написанию поиска с backtracking. Любой, кто писал в том или ином виде backtracking search, знает, что сложность обычно заключается в том, чтобы выбрать правильную репрезентацию данных, так, чтобы добавить следующий выбор, а потом его "откатить назад", было легко. Часто оказывается, что есть трейдофф между быстрым доступом к данным и быстрым изменению/откатыванию их части. Алгоритм Кнута основывается на следующем наблюдении. Если мы удаляем элемент из двойного связанного списка, то сам элемент, вырванный из списка, естественным образом сохраняет в себе - в своих указателях влево/вправо - информацию о том, где он был в списке; и за O(1) времени его можно обратно вставить. Значит, если в процессе backtracking search можно представить "следующий выбор" как удаление элементов из связанных списков, то "откат" - возвращение их в эти списки - получается и очень быстрым, и удобным с точки зрения промежуточных данных: элементы сами помнят, куда их вставлять, не нужно это отдельно никуда записывать.
Это еще не все, есть важные подробности конкретно в случае exact cover о том, в каком порядке удалять/возвращать элементы из списков, но это все можно прочитать в статье. Отличная статья, легко читается.
Мета-замечание: "алгоритм танцующих ссылок" Кнута требует свободного владения указателями! Не в каком-то конкретном языке, а самим понятием указателя. Его можно считать примером того, почему все-таки важно программистам иметь опыт работы с языками, в которых указатели не спрятаны от программиста: не только Питон, но и C++ или хотя бы Джава. Не то чтобы на Питоне невозможно было имплементировать этот алгоритм; нет, можно, но странно и неудобно, потому что нормальный способ работы со списком в Питоне - это, как ни странно, питоновский список, а в нем удаленный элемент не хранит при себе свое место и не может за O(1) вернуть себя на него.
Кто-то написал элегантный код алгоритма Кнута на Питоне, но его можно считать только кодом алгоритма X для решения exact cover, а не питоновским вариантом "танцующих ссылок", вопреки тому, что говорит автор кода. В его коде никакие ссылки не танцуют, а удаление элемента и возвращение его воплощено как удаление/возвращение из питоновского множества, т.е. операция O(logN) на каком-то сбалансированном дереве (полагаю - не знаю точно, как в Питоне внутри устроены множества). С другой стороны, важно отметить, что если это работает для проблем нужного нам масштаба, то и ладно. Еще в начале 90-х, не говоря уж о более ранних эпохах, делать отдельное сбалансированное дерево для каждой строки матрицы было бы безнадежно медленным. Закон Мура быстро, но верно сделал свое дело. Задачи с малым N теперь обычно не требуют элегантных оптимизаций, подобных "танцующим ссылкам"; а задачам с огромным N они все равно часто не помогают, потому что задачи NP-полные и перебор растет экспоненциально. Остается область посредине, где такие техники все еще важны и останутся важными. Нередко интересные задачи оказываются именно там, так что "танцующие ссылки" еще потанцуют, думаю.
