Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

танцующие ссылки

СЯУ из комментария в 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-полные и перебор растет экспоненциально. Остается область посредине, где такие техники все еще важны и останутся важными. Нередко интересные задачи оказываются именно там, так что "танцующие ссылки" еще потанцуют, думаю.
Tags: программирование
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 35 comments