#algorithm
#алгоритм
Вопрос:
Предыстория:
Ниже приведен псевдокод из статьи Дональда Кнута: Танцующие ссылки
If A is empty, the problem is solved; terminate successfully.
Otherwise choose a column, c (deterministically).
Choose a row, r, such that A[r, c] = 1 (nondeterministically).
Include r in the partial solution.
For each j such that A[r, j] = 1,
delete column j from matrix A;
for each i such that A[i, j] = 1,
delete row i from matrix A.
Repeat this algorithm recursively on the reduced matrix A.
Затем Кнут пишет:
Недетерминированный выбор r означает, что алгоритм по существу клонирует себя в независимые подалгоритмы; каждый подалгоритм наследует текущую матрицу A, но уменьшает ее по отношению к другой строке r.
Мои предположения о (не) детерминированных алгоритмах:
Я думаю, что выбор c является детерминированным, потому что количество столбцов в точной матрице ограничений A известно заранее.
Я думаю, что этот выбор r недетерминирован, потому что количество доступных строк заранее неизвестно. Набор доступных строк зависит от текущего состояния решателя. Например, для определенного состояния решателя следующая строка, удовлетворяющая A[r, c] = 1 , может быть поблизости. В другом состоянии это может быть намного дальше.
Я пришел к вышеуказанным предположениям, прочитав статью в Википедии о недетерминированных алгоритмах, в частности:
Алгоритм, который решает задачу за недетерминированное полиномиальное время, может выполняться за полиномиальное или экспоненциальное время в зависимости от выбора, который он делает во время выполнения.
Вопрос
Каким образом недетерминированность алгоритма делает его «по существу, клонирующим самого себя»? Это больше похоже на свойство рекурсии, чем детерминированных алгоритмов.
Комментарии:
1. Я думаю, что статья в Википедии неверна; или, по крайней мере, она определяет термин «недетерминированный» совсем не так, как его использует Кнут. (Они связаны, но не таким образом, чтобы вы могли легко разобраться самостоятельно, если вы не знакомы с тем, как Кнут его использует.) Вместо этого прочитайте это: en.wikipedia.org/wiki/Non-deterministic_Turing_machine .
2. @ruakh, спасибо, что указал мне на это определение. Я вижу, как дерево вычислений недетерминированной машины Тьюринга, описанное в Википедии, соответствует выбору слова Кнута. Каждая ветвь дерева вычислений NTM является одним из «клонов» Кнута. (Для будущих искателей ответов см. Разрешение нескольких правил
Ответ №1:
Выбор c является детерминированным, потому что нет неправильных вариантов (но некоторые правила для этого выбора лучше других; смотрите обсуждение вскоре после псевдокода в статье Кнута). Алгоритм делает один произвольный выбор и движется дальше. При рекурсивных вызовах количество столбцов, которые остаются в матрице, заранее неизвестно.
Выбор r недетерминирован, потому что алгоритму нужно попробовать все возможные варианты, чтобы найти все решения. Кнут, вероятно, описал это таким образом, потому что (1) он теоретик CS старой школы, и именно так это было бы описано в теории автоматов / формального языка (2) это подчеркивает тот факт, что недетерминированные ветви не зависят друг от друга и, следовательно, поддаются параллелизму.