1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 25
Текст из файла (страница 25)
Информационные связи мея<ду вершинами дерева формулы задают частичное отношение порядка выполнения операций при вычислении формулы: любая вершина и должна выполняться после любой вершины из Т(п). Это отношение порядка частично в том смысле, что оно предписывает порядок выполнения не полностью: вершины, лежащие на пути, соединяэ»щем висячую вершину с корнем, должны выполняться друг по отношению 'к другу строго в том порядке, в каком онп проходятся в этом пути; с другой стоРоны, ДлЯ двУх веРшин и, и Рт, вычислЯюЩих аРгУменты какой- либо бинарной операции и, любая пара вершин из деревьев Т(пт) и Т(э ) соответственно может друг по отношению к другу выполняться в любом порядке. Эта частичность упорядоченности вершин в дереве формулы н является источником того, что одна и та ясе формула может быть запрограммирована многими разными способами (два способа программирования формулы для вычисления хь» и показаны на рис.
3:8, б) и в)). Любая программа, вычисляющая формулу, аадает полный порядок выполнения операций, обрааующих формулу. При этом, однако, сохраняется частичный порядок, установленный информационными связями в формуле. Итак, программой выполнения формулы может быть любое полное упорядочение операций формулы, сохраняющее присущий ей частичный порядок. Мы видим, что различные варианты программ, вычисляющие формулу, требуют разного количества ячеек памяти, вычисляемого как максимальная ширина сечений информационных свяаей.
В связи с этим естественно возникает комбинаторная аадача: найти такое упорядочение вершин дерева формулы, которое имеет нанменыпую ширину среди всех упорядочений (при атом, говоря о ширине упорядочения, мы имеем в виду максимальную ширину среди всех сечений при заданном упорядочении). Эта задача— типичный пример так называемых «минимаксных» комбинаторных проблем, часто встречающихся в математике. Найденное таким в) дерево может быть определено и с яротлэоположпой орпелтацией дтг по отношению п корню и висячим вершинам.
Последние пл»ывают также во»левыми вля тврмилавьиыми вершин«ми плп просто тевмвяввмлэм Гл. 3. АлгогитмизАция 12О образом сечение мы тоже будем называть гзиниг«акеныг«сечением формулы. Сначала оценим общее количество вариантов упорядочеиия вершин дерева. Для простоты возьмем случай симметричного или, как говорят, равновесного й-яруского бинарного дерева (рис. 3.7, г)), имеющего 2" аргументов, 2" — 1 вершин, из иих 2" — ' висячих.
Будем подсчитывать число упорядочений иядукцяей по числу ярусов. Рассмотрим некоторую яевисячую вершину дерева ю, и ее пРеДнлествеиииков Рл и и». Мы Уже заметили, что ках«ДаЯ паРа вершин из Т(и,) и Т(и,) соответственно может быть произвольно упорядочеиа при условии, что обе они будут предшествовать и. Пусть т — число вершин в деревьях Т(и,) и Т(ил) (в силу симметрии оии одинаковы). Пусть А и  — какие-то упорядочеиия вершил из Т(пл) и Т(ил) соответственно. Тогда при задаииых А и В мы молем получить серию упорядочений для дерева Т(в) таким образом: перемешаем каким-то произвольиым образом вершины из Т(и,) и вершины из Т(ил), по так, чтобы относительные порядки А и В между вершинами, отяосяшимися к одному дереву, сохравились бы (иазовем зту процедуру упорядоченным смешиванием последовательностей А и В) и вслед за зтим упорядочением длииы 2т поместим вершину ле.
Пусть В(р, д) — количество всех возлюжяых упорядоченных смешиваний двух последовательиостей длин р и д соотяетствекяо, а М вЂ” число всезоаможкых упорядочений вершин деревьев как Т(и,), так и Т(ел). Тогда число М' всевоаможиых упорядочений вершин дерева Т(ю) будет равно М' = М».В(т, т). (1) Оценим теперь функцило В(р, д).
Будем для краткости последовательность длины и называть н-ыабором. Решение ' задачи упорядоченного смешивания д-иабора с р-кабором можно понимать так, что из некоторых аадаияых р +д «мест», какие-то р мест занимаются р-иабором, а оставлпиеся «) мест занимаются д-яабором. Очевидно, что лзлбое упорядоченное смешивание характерпауется выбором некоторых р мест из заданных р -'; а мест и, наоборот любой амбар р мест однозначно задает некоторое упорядоченное смешиваиие. Отсюда ораву получаем, что (2) Пусть М» — число всевозможных упорядочеиий Й-яруспого равкозеспого бинарного дерева. Тогда (1) и (2) вместе дают соотношение Мт (2" — 2)1 ( " ' — )'1' % 3.3.
РАСКРАСКА ВЕРШИН ГРАФА. ОБЩЕЕ ИССЛЕДОВАНИЕ 121 Поскольку М, = 1, то окончательяое выра>кение получает вид; (2" — 2) ! »» — 1 П (21 — ')3» ' Упростим полученное выражение, заменив правую часть ее нижней оценкой, увеличив анаменатель за счет замены 2' — 1 на 2': (2 — 2) ! (2" — 2)! »)» П 212» — ' (2" — 2) ! » — 1 1» — ! 2 12" 4 2» Х 42 21= 1=-1 4 1 Слагаемые в скобках — зто отрезок сходящегося числового ряда с суммой, согласно задачнику Б. П.
Демидовича, равной двум. Заменив отрезок ряда его суммой, мы усилим неравенство, Назовем числитель и знаменатель дроби соответственно повышаю- щим и понижающим факториалами. Само соотношение обозначим Г'(44 — 1) и назовем й — 1 его порядком. Подставим в М», его выражение через М» 3, т. е.
применим СООТНОШЕНИЕ г"(44 — 2): М„= М,',, Н2» 1 — 2)(1 (2» )1 [(2» 2 — 1)1! И2» 1 — 1)()3 [(2».— 1 — 2)! )г (2» — 2) ! 2 [(2» 1 — 2)'(2» 1 — 1)[3 К2" 2 — 1)([4 ш» (2„2), (2» — г )4 [(. 1, 2 )([4 . [1[ы видим закономерность в применении соотношения г (Й вЂ” 2), состоящую в том, что повышающий факториал соотношения г"(Й вЂ” 2) сокращается с понижающим факториалом соотношения г'(Й вЂ” 1), оставляя в знаменателе степенной множитель с показа- телем, равным двойке в степени, дополняющей порядок применяе- мого соотношения до Й вЂ” 1. При последовательном применении соотношений г'(44 — 1) (1 = 1,..., Й вЂ” 1) в выражении для М» в числителе будет получаться М"„, и сохраняться факториаль- ный множитель (2" — 2)[, а в знаменателе — накапливаться степенные множители и получаться понижающий факториал [(2" ' — 1)! !'.
После применения соотношения г'(1) получим, что М»-- 4И1 (2» — 2)! (2» ' — 1) х ... х (2,' — 1!' [(2' — 1)([3 Гл. 3. ллгогитмизация и вспомнив, что 2ь — 1 = и, где и — число операций в дереве, получим окончательную оценку для Мь.' (и — 1)! М ) Итак, мы обнаружили, что число различных вариантов упорядочивания операций формулы, представляемой равновесным деревом с и вершинами, растет с и несколько медленнее, чем п! В то же время мы сейчас покажем, что для неко(срого (правда, упрощенного) способа вычисления формул их минимаксное сечение может быть найдено очень простым алгоритмом с числом действий порядка всего лишь и. Упрощение будет состоять в том, что аргументы формулы'не входят в категорию величин, для которых мы хотим экономно распределить паыять, и что, если в формуле есть совпадающие подвыражения, то они программируются каждый раз заново.
В этом случае информационные связи в формуле будут действительно образовывать дерево, а не какой-либо более сложный граф (однако мы не требуем, чтобы дерево было строго бинарным и равновесным, в частности, оно может содержать унарные операции, т. е. над одним аргументом). Опишем этот алгоритм индукцией по построению дерева. Другими словами, говоря о дереве Т(ю) с корнем ю, мы будем рассматривать два случая: а) и имеет единственного предшественника о, являющегося корнем дерева Т(и) (случай унарной операции); б) ю имеет двух предшественников, од и о„явля!ощихся корнями деревьев Т(о,) и Т(ог) соответственно (случай бинарной операции). Будем считать, что минимаксные сечения деревьев Т(о), Т(о„) и Т(о,) найдены н равны соответственно з, з, и з,.
Секрет алгоритма раскрывает следувнцая далее Т е о р е м а 6. В принятых обозначениях минимаксное сечение з' формулы, задаваемой деревом Т(ю), в случае а) равно з, а в случае б) выражается формулой шах(з„з,), если г, ~ ге, з,+1, еслиз,=з. г Упорядочение вершин дерева Т(ю), достигающее минимоксной ширины (оптимальное упорядочение), строится следующим образом: в случае а) берется оптимальное упорядочение дерева Т(о), за ним — вершина ю; в случае б) берется оптимальное упорядочение дерева с большей минилаксной ишриной (или любое дерево в случае равных ишрин), за ниы — оптимальное упорядочение другого дерева, за ними— вершина ю.
$ З.З. РАСКРАСКА ВЕРШИН ГРАФА. ОБЩЕЕ ИССЛЕДОВАНИЕ 133 Рнс. 3.9. К доказательству теоремы 6 о) Упорядочение Еез смешнввния. 6) Упорядоченне со смешнваннеы. Д о к а з а т е л ь с т в о. Случай а) тривиален, так как, имея Оптимальное упорядочение дерева Т(о), мы его наращиваем ааключительной вершиной гв однозначно, ширина добавленного сечения равна единице н не может быть больше уже достигнутой минимансиой ширины я. Рассмотрим случай б). На рис. 3.9, а) схематически показано упорядочение дерева Т(иг) без смешивания поря)(ков Т(о,) и Т(ие), а на рис.
3.9, б) — со смешиванием. Очевидно, что если я,) я, то упорядочение, требуемое условием теоремы, будет оптимальным, так как информационные свяан деревьев 3, 5г Т(о,) и Т(Р,) при упорядочении без смешивания не конкурируют, а достигаемая ширина, равная тт + 1 в одном из сечений 5г при вычислениях на дереве Т(иг), не превзойдет ширины е, как раз и являющейся по тео- Тг реме минимаксной шириной зг г всей формулы.
Если же я, = я, то минимаксной шириной ока- ог ег, зывается е,+1. Любое яте упорядочение со смешением порядков Т(от) и Т(Р,) может лишь и Ю увеличить ширину, достигае- м 6 мую при упорядочении согласно условию теоремы, так как при этом в дополнение к новой связи от и, к гя становятся конкурирующими некоторые связи внутри деревьев . Т(и,) и Т(Р»). туту На основе доказанной теоремы алгоритм оптимального упорядочения приобретает следующий вид. Сначала на вершинах деревьев строится по индукции функция ширины. Для висячих вершин она с очевидностью полагается равной единице, а затем, по правилу теоремы, находится для очередной вершины дерева, используя уже найденные значения функции ширины ее предшественников. Затем дерево упорядочивается от корня к висячим вершинам: ваяв корень, ставим перед ним его единственного предшественника (для случая одноместной операции).
В случае двух предшественников и, и о ставим перед корнем вершину Р, (если я, ( е ), а вершину Р» запоминаем. Затем «корнем» становится вершина ь„и все повторяется, пока не дойдем до висячей вершины. ' Поместив на место висячую вершину, берем в качестве «корня» последнюю из запомненных вершин. На рис. 3.10 приведены два ГЛ. 3. АЛГОРИТМИЗАПИЯ ц о ф Ю щ о Ь' о И.'С Ф до о ~ ц ° до Ф З о В й о й а й о .с о,о о од а о с5 о , С-. Ф Р ь $3.3. Раскраска ВБРшин РРАФА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
