Нерекурсивные алгоритмы упорядоченного обхода

Question

Существует семейство комбинаторных алгоритмов, основанных на следующем методе - мы наблюдаем некоторое свойство структуры и, используя это свойство, обходим все возможные / доступные варианты в линейном (или закрытом, что угодно, не имеет большого значения) Время без рекурсии.

Примеры

лексикографическая перестановка a 1 .. a [n]

• найти последний a [k] такой, что a [k] ...
• найдите минимальное значение a [m] в a [k + 1] .. a [n] такое, что a [k] поменяйте местами [m] и [k]
• вернуть a [k + 1] .. a [n]

k-подмножеств n

• повторить с конца, найти первый ноль, которому предшествует 1 (сначала a [k] == 0, так что a [k + 1] == 1)
• назначить [k] = 1
• считать 1 в [k] .. a [n]
• rebalance - назначить как можно больше единиц в конце, остальные установить на ноль

разбиений n (в порядке убывания)

• найти первый k такой, что a [k]> a [k + 1] (k = 1 тоже в порядке)
• увеличение a [k] = a [k] + 1
• найти сумму элементов от k до последнего
• увеличить количество левых соседей на 1, если позволяет сумма.

Полагаю, этого достаточно, чтобы проиллюстрировать природу таких алгоритмов. Эти и некоторые другие примеры можно найти в превосходной превосходной книге " Алгоритмы и программирование: проблемы и решения ".

У меня следующий вопрос. Можете ли вы описать мне больше примеров таких алгоритмов в любой области? Было бы здорово, если бы вы также предоставили сам алгоритм (на словах, как и выше, предпочтительнее). Ссылки на книги, статьи также приветствуются. Ссылки на связанные теоретические вопросы также приветствуются (например, у меня просто нет ощущения, когда такие алгоритмы можно создавать, а когда - нет).

Заранее спасибо.

Answer 1

Рассмотрим алгоритм A из семейства алгоритмов. Либо A уже итеративный, либо, если он рекурсивный, его можно преобразовать в эквивалентный итерационный алгоритм путем моделирования стека вызовов с помощью явной структуры данных. Смотрите, например Википедии .

Answer 2

Это то же самое, что и ответ Джири, но, возможно, немного более прямой: любая разрешимая вычислительная проблема разрешима машиной Тьюринга, и я не думаю, что кто-то мог бы описать функционирование машины Тьюринга как "рекурсивное" , но как на основе государства. Другими словами, при наличии достаточного количества вспомогательного накопителя на магнитной ленте, цикла while и регистра выбора (или эквивалентного ветвления, например, если / else, конструкция), вы можете решить любую проблему - включая эти проблемы перечисления - используя подход, основанный на автомате состояний .

Например, довольно просто определить основанный на состоянии алгоритм для выполнения обхода в порядке двоичного дерева поиска.

1. Начать в состоянии DL (вниз-влево). Если вы находитесь в DL и если у узла есть левый потомок, перейдите к нему и оставайтесь в состоянии DL; в противном случае выведите содержимое узла и, если у узла есть правильный дочерний элемент, перейдите в состояние DR и перейдите к правому дочернему элементу; если у узла нет правого потомка, перейдите в состояние UR и перейдите к родителю.

2. Если в штате DR и у вас есть левый ребенок, перейдите к левому ребенку и перейдите в состояние DL. В противном случае, если у вас есть правильный дочерний элемент, распечатайте содержимое узла и перейдите к дочернему элементу и оставайтесь в DR. В противном случае перейдите к родительскому узлу и перейдите в состояние UL.

3. Если в состоянии UR выведите информацию об узле и, если есть правильный дочерний элемент, перейдите к нему и измените состояние на DR; в противном случае перейдите к родителю и оставайтесь в UR.

4. Если в состоянии UL, если текущий узел является правым потомком своего родителя, оставайтесь в UL и переходите к родителю; в противном случае, если текущий узел не является правым дочерним элементом родительского элемента и является левым дочерним элементом, перейдите в состояние UR и перейдите к родительскому элементу. Если у этого узла нет родителя, завершите алгоритм.

В любом случае, вы поняли идею. Упорядоченные обходы деревьев примерно так же естественны, как и вы; многие (все?) другие проблемы обхода могут быть рассмотрены с точки зрения обхода некоторого дерева, и вот метод выполнения обхода по порядку за линейное время с использованием конечного автомата. Вы верите, что этот метод O (n)? Подсказка: он посещает каждый узел не более трех раз.