Алгоритмы - построение и анализ (1021735), страница 86
Текст из файла (страница 86)
Определим величину е [г, Я как математическое ожидание стоимости поиска в оптимальном бинарном дереве поиска с ключами Ц,..., !с . В конечном итоге нужно вычислить величину е [1, и]. Если 7' = с' — 1, то все просто. В этом случае имеется всего один фиктивный ключ 4 и и математическое ожидание стоимости поиска равно е [т, 1 — Ц = йя ь Если 7' > 1, то среди ключей /с,,..., /су нужно выбрать корень !с„, а потом нз ключей !с;,..., /с„з составить левое оптимальное бинарное дерево поиска, а из ключей к,+ы..., !су — правое оптимальное бинарное дерево поиска.
Что происходит с математическим ожиданием стоимости поиска в поддереве, когда оно становится поддеревом какого-то узла? Глубина каждого узла в поддереве возрастает на единицу. Согласно уравнению (! 5.16), математическое ожидание стоимости поиска в этом поддереве возрастает на величину суммы по всем вероятностям поддерева. Обозначим эту сумму вероятностей, вычисленную для поддерева с ключами й;,...,Й,, так: Глава 15. Динамическое программирование 431 Величины е [г, з) — это математическое ожидание стоимостей поиска в оптимальных бинарных деревьях поиска. Чтобы было легче следить за структурой оптимального бинарного дерева поиска, обозначим через гоо1 [г', з] (где 1 < 1 < < з < и) индекс т узла lс„, который является корнем оптимального бинарного дерева поиска, содержащего ключи Ц,..., /с . Скоро мы узнаем, как вычисляются величины гоо1 [г, з], а способ восстановления из этих величин оптимального бинарного дерева поиска оставим до того момента, когда придет время выполнить упражнение 15.5-1.
Этап 3: вычисление математического ожидания стоимости поиска в оптимальном бинарном дереве поиска На данном этапе некоторые читатели, возможно, заметили некоторое сходство между характеристиками задач об оптимальных бинарных деревьях поиска и о перемножении цепочки матриц. Во вспомогательных задачах обеих задач индексы элементов изменяются последовательно. Прямая рекурсивная реализация уравнения (15.19) может оказаться такой же неэффективной, как и прямая рекурсивная реализация алгоритма в задаче о перемножении цепочки матриц.
Вместо этого будем сохранять значения е [с, з] в таблице е [1..и+ 1,0..п]. Первый индекс должен пробегать не и, а п + 1 значений. Это объясняется тем, что для получения поддерева, в который входит только фиктивный ключ 4,„понадобится вычислить и сохранить значение е [п+ 1, и]. Второй индекс должен начинаться с нуля, поскольку для получения поддерева, содержащего лишь фиктивный ключ с(о, нужно вычислить и сохранить значение е [1, О]. Мы будем использовать только те элементы е [г, Я, для которых з > 1 — 1.
Кроме того, будет использована таблица гоо1 [г, з], в которую будут заноситься корни поддеревьев, содержащих ключи Ц,..., /с . В этой таблице задействованы только те записи, для которых 1<г<з<и. Для повышения эффективности понадобится еще одна таблица. Вместо того чтобы каждый раз при вычислении е [г, з] вычислять значения со (г, з) "с нуля", для чего потребуется 6 (з — 1) операций сложения, будем сохранять эти значения в таблице и [1 ..п + 1, О..п).
В базовом случае вычисляются величины ю [с', 1 — 1) = = д; 1 для 1 ( 1 ( и + 1. Для з' > 1 вычисляются величины ю [г, з] = и [с', з' — 1] + р + д . (15.20) Таким образом, каждое из 9 [пз) значений матрицы со [г, з] можно вычислить за время 9 (1). Ниже приведен псевдокод, который принимает в качестве входных данных вероятности рм..., р„и до,..., д„и размер п и возвращает таблицы е и гоо1. Часть |Ч. Усовершенствованные методы разработки и анализа 432 ОРТ!мА!. ВБТ[р, 9, и) 1 Гогг' — 1 1о и+1 2 до е[г,1 — 1] — рн 3 ю[ю',г — Ц вЂ” о; 1 4 1ог! — 1 то и 5 Йо 1ог 1 — 1 Го и — 1+ 1 б йо 7' -1+1 — 1 7 е[г, Я оо 8 ю[г',Я вЂ” ю[т,7' — 1] + ру + 93 9 Гог т — г' 1о 7' 1О йо 1 — е(г, т — 1] + е[т+ 1, 7] + ю[1, 7] !1 !Г! < е[1,2] !2 Феп е[Г,Я вЂ” Х 13 тоо8[з, Я вЂ” т !4 гегпгп е и тоо1 Благодаря приведенному выше описанию и аналогии с процедурой МАтк!х СнА!н Оюеа, описанной в разделе 15.2, работа представленной выше процедуры должна быть понятной.
Цикл 1ог в строках 1-3 инициализирует значения е [1,1 — 1] и ю (1,1 — Ц. Затем в цикле 1ог в строках 4-13 с помощью рекуррентных соотношений Г!5.19) и 115.20) вычисляются элементы матриц е [г, Я и ю [г, Я для всех индексов 1 < ! < 7' < и. В первой итерации, когда ! = 1, в этом цикле вычисляются элементы е [г, 1) и ю [г, 1] для 1 = 1, 2,..., и.
Во второй итерации, когда 1 = 2, вычисляются элементы е [1,1+ 1) и ю [г, Г + 1] для Г = 1, 2,..., и — 1 и т.д. Во внутреннем цикле Гог Гстроки 9 — 13) каждый индекс т апробируется на роль индекса корневого элемента )с„оптимального бинарного дерева поиска с ключами )с,,..., й~. В этом цикле элементу тоо1 [1, 7] присваивается то значение индекса т, которое подходит лучше всего. На рис. 15.8 показаны таблицы е [г, Я, ю (з, Я и тоо! [г, 7], вычисленные с помощью процедуры ОРт!мль ВБТ для распределения ключей из табл. 15.!. Как и в примере с перемножением цепочки матриц, таблицы повернуты так, чтобы диагонали располагались горизонтально.
В процедуре ОРт!мл!. ВБТ строки вычисляются снизу вверх, а в каждой строке заполнение элементов производится слева направо. Время выполнения процедуры ОРт!мл!. ВБТ, как и время выполнения процедуры МАтих СнА!н Оюна, равно 91и~). Легко увидеть, что время работы составляет О [из), поскольку циклы 1ог этой процедуры трижды вложены друг в друга, и индекс каждого цикла принимает не более и значений. Далее, индексы циклов в процедуре ОРт!мА!. ВБТ изменяются не в тех же пределах, что и индексы циклов в процедуре МАта!х Снл!н Оюек, но во всех направлениях они принимают по крайней мере одно значение. Таким образом, процедура ОРт!мА!. ВБТ, как и процедура МАта!х Снлпч Оюпк, выполняется в течение времени Г) [из).
Глава 15. Динамическое программирование 433 Рис. 15.8. Таблицы с~!,1), и ~1,Я н гоо! ~г,Я, вычнслснныс процедурой Огть мль ВЯТ для распрсдслсния ключсй из табл. !5.1 Упражнения 15.5-1. Напишите псевдокод для процедуры Соызтиг!ст Опт!ми. ВБТ(гоо!), которая по заданной таблице гоп! выдает структуру оптимального бинарного дерева поиска. Для примера, приведенного на рис.
15.8, процедура должна выводить структуру, соответствующую оптимальному бинарному дереву поиска, показанному на рис. 15.76: Йз — корень Й! — левый дочерний элемент Йз дс — левый дочерний элемент й! с!1 — правый дочерний элемент !с1 1св — правый дочерний элемент Йз Й~ — левый дочерний элемент Йз йз — левый дочерний элемент к4 г!з — левый дочерний элемент йз с!з — правый дочерний элемент Йз о4 — правый дочерний элемент Й4 Ыь — правый дочерний элемент 1сз Часть 1Ч. Усовершенствованные методы разработки и анализа 434 15.5-2. Определите стоимость и структуру оптимальною бинарного дерева поиска для множества, состоящего из и = 7 ключей, которым соответствуют след уюшие вероятности: 15.5-3.
Предположим, что вместо того, чтобы поддерживать таблицу и [г, Я„значение ш (г, з) вычисляется в строке 8 процедуры Огт!мА!. ВБТ непосредственно из уравнения (15.17) и используется в строке 1О. Как это изменение повлияет на асимптотическое поведение времени выполнения этой процедуры? * 15.5-4. Кнут (184! показал, что всегда существуют корни оптимальных поддеревьев, такие что гоо1[г, З вЂ” 1] < гоо1[1, Я < гоо1[1 + 1,Я для всех 1 < 1 < з < и. Используйте этот факт для модификации процедуры Огт!млг.
ВБТ, при которой время ее выполнения станет равным 9 (п~). Задачи 15-1. Битоиическая евклидова задача о коммивояжере Евклидова задача о коммивояжере (епс!Ыеап 1гаче11!пй-за1еашап ргоЬ1еш) — это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из и точек на плоскости.
На рис. 15.9а приведено решение задачи, в которой имеется семь точек. В общем случае задача является Ыр-полной, поэтому считается, что для ее решения требуется время, превышающее полиномиальное (см. главу 34). Бентли (1.1.. Вепг!еу) предположил, что задача упрощается благодаря ограничению интересуюших нас маршрутов ботаническими (Ь!гоп!с 1опг), т.е. такими, которые начинаются в крайней левой точке, проходят слева направо, а затем — справа налево, возвращаясь прямо к исходной точке. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
