Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007, страница 7

4 в точности соответствуют 14 строкам вложенных скобок в табл. 1. Это наблюдение позволяет легко генерировать строки табл. 4 последовательно, снизу вверх, при помощи метода, аналогичного алгоритму Р (см, упражнение 77). Пусть 7 (хм..., х„) — произвольная монотонная булева функция от и переменных.

Если и = а1... а„— произвольная битовая строка длиной и, для удобства можно записывать У(п) = 7 (ам...,а„). любая строка п1...а, шаблона ролсдественской елки образует целочку, так что мы имеем 0< 7'(и») « 7(п,) < 1. сделано для вълклн$анаса.ого (40) для некоторых р и 9 (О < р < 4), где подстроки ар,...,а» корректно вложенные (возможно, пустые). Ровно р правых скобок и 4 — р левых "свободны" в том смысле, что не имеют соответствующей пары.

Например, у строки 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАГОРНЫХ ОВЪЕК'ГОВ ЗЗ Другими словами, имеется индекс $, такой„что /(<гу) = 0 при,у < 1 и /(ау) = 1 при 1' > $; нам будут известны значения /(а) для всех 2" битовых строк а, если мы узнаем индексы 1 для каждой строки шаблона. Джордж Хансель (Оеогбез Нэлве!) [Сошр1ез Кепс(ав Асад. 3сй (А), 262 (Рапв, 1966), 1088 — 1090[ заметил, что шаблон рождественской елки обладает еще одним важным свойством: если а ы о; и аз+1 представляют собой три последовательных элемента любой строки, битовая строка ! а = а; 1 9 а !9 аз+1 (41) находится в предыдущей строке. В действительности а! находится в том же столбце, что и а", и удовлетворяет условию <г 1Са! Са.+1, ! (42) зто значение называется относительным дополнением (ге1а11 е сошр1ешепх) о в интервале (а ! ..а +!), Наблюдение Ханселя легкодоказать по индукции при помощи рекурсивного правила (36), определяющего шаблон рождественской елки.

Он воспользовался им для того, чтобы показать, что можно вывести значения / (о) для всех с!, вычисляя значения функции в относительно небольшом количестве мест; если известно значение / (о'), то в силу (42) известно либо /(а 1), либо /(а +~). Алгоритм Н (Исследование монотонной булевой функции). Пусть /(хм ..., х„) — булева функция, неубывающая по каждой из булевых переменных (более о ней ничего не известно).

Обозначим для данной битовой строки а длиной ц через г (а) номер строки, в которой !т находится в шаблоне рождественской елки; очевидно, что 1 < г (а) < М„. Для 1 < т < М„обозначим через х (т) количество битовых строк в строке т; а Х (т, й) будет означать битовую строку в столбце к этой строки при (п+ 1 — х (т))/2 < Й < (и — 1+ х (т))/2.

Данный алгоритм определяет последовательность пороговых значений Ф (1), Ф (2),...,1 (М„), таких, что /( ) =1 ( ) > ( (.)), (43) путем вычисления / не более чем в двух точках на строку. Н1. [Цикл по т.[ Выполнить шаги с Н2 по Н4 для т = 1,..., М„; после этого завершить выполнение алгоритма. НЗ. [Бинарный поиск.! Если х < а + 1, перейти к шагу Н4. В противном случае установить й — [(а+ х)/2) и Х( Ь,й-1) ЕХ(т,й) ЕХ(т,й+ 1). (44) Если Й > 1(г(а)), установить х — Й; в противном случае установить а ! — Й.

Повторить шаг НЗ. Н4. [Вычисление.] Если / (Х (т, а)) = 1, установить | (т) !- а; в противном случае, если а = х, установить | (т) — а+1; в противном случае установить 1 (т) — х+ +1 — /(Х(т, )). 1 сделано для ьуэуж$н$анаса,ого Н2, [Начальная строка т.[ Установить а — (и + 1 — э (т))/2 и х -(и — 1 + э (т))/2.

34 КОМВИНАТОРНЫИ ПОИСК 7.2.1 Алгоритм Ханселя опшимален в том смысле, что вычисляет / в наименьшем возможном количестве точек в наихудшем случае. Если / представляет собой пороговую функцию /(и) = (м(п) > н/2], (45) любой корректный алгоритм, который исследует / на первых т строках шаблона рождественской елки, должен вычислять /(а) в столбце (/2] каждой строки и в столбце (и/2] + 1 каждой строки, размер которой больше 1.

В противном случае невозможно отличить / от функции, которая не совпадает с ней только в неисследованных точках. ]См. У.К. КогоЪкот, РгоЫету К1Ьегпег1(п', 13 (1965), 5-28, теорема 5.] Ориентированные деревья н леса. Обратимся теперь к другому виду деревьев, в которых важны отношения "родитель — потомок", но не порядок потомков в каждом семействе. Ориеншщюеаннмй лес из и узлов можно определить как последовательность указателей р1... р„, где р — родитель узла у (если 1 — корень, р. = О); ориентированный граф с вершинами (О, 1,..., и) и ребрами (1 -+ р ]1 < 1 < и) не имеет ориентированных циклов. Ориекшщюваниое дерево представляет собой ориентированный лес с единственным корнем (см. раздел 2.3.4.2). Каждый ориентированный лес из и узлов эквивалентен (и+ 1)-узловому ориентированному дереву, поскальку корень этого дерева можно рассматривать как родителя для всех корней леса.

В разделе 2.3.4.4 мы видели, что имеется А„ориентированных деревьев с и узлами. Вот несколько первых значений А„: и = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 А„= 1 1 2 4 9 20 48 115 286 719 1842 4766 12486 32973 Асимптотически А„= со"и зуз + О (а"и™), где а 2.9558 и с 0.4399. Так, например, только 9 из 14 лесов в табл, 1 различны, если игнорировать порядок по горизонтали и рассматривать только вертикальную ориентацию.

Каждый ориентированный лес соответствует единственному упорядоченному лесу, если мы соответствующим образом отсортируем члены каждого семейства с использованием упорядочения деревьев, предложенного Г.Я. Скоинсом (Н.1. Бсо1пз) ]Мас1ипе 1псе)08еасе, 3 (1968), 43-60]: вспомним из (11), что упорядоченные леса могут характеризоваться кодами их уровней с1... с„, где сз указывает уровень, на котором в лесу находится ~-й в прямом порядке обхода узел. Упорядоченный лес называется каноническшм, если последовательность кодов уровней поддеревьев в каждом семействе находится в невозрастающем лексикографическом порядке. Например, каноническими лесами в табл. 1 являются те, у которых коды уровней с1сзсзс4 равны 0000, 0100, 0101, 0110, ОШ, 0120, 0121, 0122 и 0123. Последовательность 0112 канонической не является, поскольку поддеревья корня имеют соответственно коды уровней 1 и 12; строка 1 лексикографически меньше 12.

По индукции можно легко убедиться, что канонические коды уровней лексикографически наибольшие среди всех сткобов переупорядочения поддеревьев данного ориентированного леса. Т. Вейер (Т. Веуег) и С.М. Хедетниеми (8.М. Небесп1еш1) ]ЯСОМР, 9 (1980), 706-712] заметили, что существует удивительно простой способ генерации ориентированных лесов, если посещать их в уменьшающемся лексикографическом порядке канонических кодов уровней. Предположим, что с1... с„— канонический код, в котором сь > 0 и сь+1 = = с„= О.

Следующая наименьшая последовательность сделано для ьуьлулп(апа1а.ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 33 получается путем уменьшения сь и увеличения сь+»... с„до наибольших уровней, согласующихся с условием квноничности; эти уровни достаточно просто вычислить. Если у = рь — родительский по отношению к узлу Й узел, получаем с» = сь— — 1 < с» для у < 1 < й, а следовательно, уровни с ...сь представляют поддерево, корнем которого является узел у. Для получения наибольшей последовательности уровней, меньших с»...с„, мы заменяем сь...с первыми и+ 1 — Й элементами бесконечной последовательности (с ...сь») = с;...сь»с ...сь»с».... (Результатом будет удаление Й из его текущей позиции крайнего справа потомка,~ и добавление новых поддеревьев, являющихся 'братьями" у, путем клонирования 1 и его наследников настолько часто, насколько это возможно.

Этот процесс клонирования может завершиться посередине последовательности с»... сь», но это не приведет к сложностям, поскольку каждый префикс канонической последовательности является каноническим.) Например, чтобы получить последующий элемент для любой последовательности канонических кодов, заканчивающейся на 23443433000000000, необходимо заменить окончание 3000000000 на 2344343234. Алгоритм О (Ориентированные леса). Данный алгоритм генерирует все ориентированные леса нз п узлов путем посещения всех канонических и-узловых лесов в уменьшающемся лексикографнческом порядке их кодов уровней с»...

с . Коды уровней, однако, явно не вычисляя»гся; каждый канонический лес представляется непосредственно последовательностью родительских указателей р»... р„в порядке прямого обхода узлов. Для генерации всех ориентированных деревьев из и + 1 узлов можно представить, что корнем является узел О.

01. [Инициализация.] Установить рь — и — 1 для 0 < й < т». (В частности, этот шаг делает ненулевым ро для использования при проверке на завершение алгоритма; см. шаг 04.) 02. ]Посещение,] Посетить лес, представленный родительскими указателями Р» ° ° Р и. 03. ]Простой случай?] Если р„> О, установить р„- рр„и вернуться к шагу 02. 04. ]Поиск у и к.] Найти наибольшее й < и, такое, что рь ф О. Завершить работу алгоритма, если и = 0; в противном случае установить у — рь и»( — и — у. Об, ]Клонирование]. Если рь,у = р», установить рь — р; в противном случае установить рь — рь э +»(. Вернуться к шагу 02, если й = и; в противном случае установить Й вЂ” Й + 1 и повторить данный шаг.