Главная Промышленная автоматика.

В Ttj, i<.j, глубина каждого узла в левом и правом поддеревьях на единицу больше глубины того же узла в Tik-i или Т]. Поэтому стоимость Ci] дерева Тц можно выразить так:

Следует брать здесь то значение k, которое минимизирует сумму Cj.h-i+Cfty. Поэтому для нахождения оптимального дерева Тц вычисляют для каждого k, i<.kj, стоимость дерева с корнем а, левым поддеревом Г,, -i и правым поддеревом Tj, а затем выбирают дерево наименьшей стоимости. Приведем соответствующий алгоритм.

Алгоритм 4.2. Построение оптимального дерева двоичного поиска

Вход. Множество S вида {oi, а, . . ., а„}, где ai<a2<. . . <а„. Известны также вероятности q„, qi, . . ., qn и pi, ра, . . ., р„, где qt, li<.n,- вероятность выполнения операции ПРИНАДЛЕЖАТЬ (а, S) для ai<.a<.ai+i, qo-вероятность выполнения операции ПРИНАДЛЕЖАТЬ (а, S) для a<ai, q- вероятность выполнения операции ПРИНАДЛЕЖАТЬ (а, 5)дляа>а„, ар(, 1<1</г,- вероятность выполнения операции ПРИНАДЛЕЖАТЬ (аj, S).

Вьаод. Дерево двоичного поиска для S, обладающее наименьшей стоимостью.

begin

1. for i*-О until п do

begin

2. Wiiqr,

3. Cii<-0 end;

4. for / 1 until n do

5. for i->-0 until n - / do

begin

6. ji + l;

7. W;jWi,j:,+Pj+q/,

8. пусть m-значение k, i <.kj, для которого сумма

i,ft-i + ft; минимальна;

10. rja,

Рис. 4.9. Алгоритм для нахождения корней оптимальных поддеревьев.



000=2 00 = 0

«11= 3 с„ =0

»22-1 52 = 0

азз= 1

Сзз=0

44 = 1 С44= 0

ifoi =9 Со, =9 /"01 = o

и,г = б с,г = 6

/•,2 =

23 = 3

Га = з

34=3 34 =

Шаг = 12 Саг = 18 %= а\

«13 = 8

13 = 11 = -2

«24 = 5 С24=8

24= й4

Шаъ = 14 Соъ = 25 Газ = а,

Шц= 10 С,4 = 18

гео4= 16

Г04= 33

04= Jz

Рис. 4.11. Значения гв;,у, с(у и r/f.

procedure ПОСТРДЕРЕВА(», /): begin

образовать корень v,f дерева T,j\ пометить Vij меткой

пусть т-индекс числа г,у (т. е. rij=a„)\

ifi<m-1 then сделать ПОСТРДЕРЕВА (f, m-1) левым поддеревом узла и,;

if m < / then сделать ПОСТРДЕРЕВА (m, /) правым поддеревом узла

Рис. 4.10. Процедура для построения оптимального дерева двоичного поиска. Метод.

1. Для 0<i</<n вычисляются rjy и C( в порядке возрастания разности /-i с помощью алгоритма динамического программирования, приведенного на рис. 4.9.

2. После вычисления всех вызывается процедура ПОСТРДЕРЕВА (О, п) для рекурсивного построения оптимального дерева для Топ- Процедура ПОСТРДЕРЕВА приведена на рис. 4.10. □




Рис. 4.12. Дерево наименьшей стоимости.

Пример 4.5. Рассмотрим четыре элемента а1<а2<аз<а4 с <7о= = 1/8, 1=3/16, 2=(7з=<?4=1/16 и Pi=l/4, р2=1/8, рз=р,=1/1б. На рис. 4.11 даны значения Wt], и су, вычисленные алгоритмом, приведенным на рис. 4.9. Для удобства записи значения Wtj и Cj в этой таблице были умножены на 16.

Например, чтобы вычислить Гц, надо сравнить значения Сц+с, С12+С34 и C18-I-C44, равные (после умножения на 16) соответственно 8, 9 и П. Таким образом, в строке 8 рис. 4.9 k=2 дает минимум, так что Гц=а2.

Вычислив таблицу рис. 4.11, строим дерево Т„, вызывая ПОСТРДЕРЕВА (О, 4). На рис. 4.12 изображено полученное в результате дерево двоичного поиска. Его стоимость равна 33/16. □

Теорема 4.2. Алгоритм 4.2 строит оптимальное дерево двоичного поиска за время 0(п).

Доказательство. Вычислив таблицу значений rt], мы строим по ней оптимальное дерево за время О (п), вызывая процедуру ПОСТРДЕРЕВА. Эта процедура вызывается только п раз, и каждый вызов занимает постоянное время.

Наиболее дорого стоит алгоритм динамического программирования (рис. 4.9). Строка 8 находит значение k, минимизирующее Ci,ft-i+Cftj, за время 0{j-/). Остальные щаги цикла в строках 5-10 занимают постоянное время. Внешний цикл в строке 4 выполняется л раз, внутренний - не более п раз для каждой итерации внешнего цикла. Таким образом, суммарная сложность составляет 0(п).

Что касается корректности алгоритма, то простой индукцией по /=/-i можно показать, что ги и Cij правильно вычисляются в строках 9 и 10.

Чтобы показать, что оптимальное дерево правильно строится процедурой ПОСТРДЕРЕВА, заметим, что если Vtj- корень поддерева для {Oi+u ai+2, •, aj}, то его левый сын будет корнем оптимального дерева для {Oi+i, Oj+a.....где Ги=а, а правый будет корнем оптимального дерева для {a„+i, а+а, . . ., Uj}.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 [44] 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0023