Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[104]

Рис. 16.3 Таблицы с и Ь, созданные алгоритмом LCS-LENGTH при X = (А, В, С, В, D, А, В) и Y = (В, D, С, А, В, А). В клетке с координатами записаны число с[г, j] и стрелка b[i,j]. Число 4 в правой нижней клетке есть длина НОП. При i,j > 0 значение с[г, j] определяется тем, равны ли х, и и вычисленными ранее значениями с[г - 1, j], c[i,j - 1] и с[г - 1, j - 1]. Путь по стрелкам, ведущий из с[7, 6], заштрихован. Каждая косая стрелка на этом пути соответствует элементу НОП (эти элементы выделены).

LCS-Length(X, У)

1

т <- length[X]

2

п <- length\Y]

3

for г <- 1 to т

4

do c[i, 0] f

- 0

5

for j <- 0 to n

6

do c[0,j]<

- 0

7

for г <- 1 to m

8

do for j f-

- 1 to ra

9

do

if хг =

Уз

10

then

4hj] +

- c[i -

1,J-

1] + 1

11

b[i,j] f

- «\»

12

else

if c[i -

Ф, j

-1]

13

then

- c[i

14

b[i,j] i

- «j»

15

else

Ф, j] <

- Ф,

J-l]

16

b[i,j] i

- «<-

»

17

return c, 6

На рис. 16.3 показана работа LCS-Length для X = (А, В, С, В, D,A,B)nY = (В, D, С, А, В, А).

Алгоритм LCS-Length требует времени О (ran): на каждую клетку требуется 0(1) шагов.


Построение НОП

Таблица Ь, созданная процедурой LCS-Length, позволяет быстро найти НОП последовательностей X = (х\, ж2,..., хт) и Y = (у\, у2, , уп)- Для этого надо пройти по пути, указанному стрелками, начиная с Ь[т,п]. Пройденная стрелка \ в клетке (i,j) означает, что жг- = yj входит в наибольшую общую подпоследовательность. Вот как это реализовано в рекурсивной процедуре Print-LCS (НОП для X и Y печатается при вызове Print-LCS(6,X, length[X], length[Y})):

print-LCS(6,X,i,j)

1if г = 0 или j = О

2then return

6elseif b [i, j] = <ф>

7then PRiNT-LCS(6,X,i-l,j)

8else PRiNT-LCS(6,X,i,j - 1)

Будучи применённой к таблице рис. 16.3, эта процедура напечатает ВС В А. Время работы процедуры есть 0(m + ra), поскольку на каждом шаге хотя бы одно из чисел тип уменьшается.

Улучшение алгоритма

После того, как алгоритм разработан, нередко удаётся сделать его более экономным. В нашем примере можно обойтись без таблицы Ь. В самом деле, каждое из чисел c[i, j] зависит от с[г - 1, j], c[i,j - 1] и c[i - 1, j - 1]. Зная c[i, j], мы можем за время 0(1) выяснить, какая из этих трёх записей использовалась. Тем самым можно найти НОП за время О (то + га) с помощью одной только таблицы с (в упражнении 16.3-2 мы попросим вас это сделать). При этом мы экономим О(тога) памяти. (Впрочем, асимптотика не меняется: объём таблицы с есть также О (тога).)

Если нас интересует только длина наибольшей общей подпоследовательности, то столько памяти не нужно: вычисление c[i,j] затрагивает только две строки с номерами г и г - 1 (это не предел экономии: можно обойтись памятью на одну строку таблицы с плюс ещё чуть-чуть, см. упражнение 16.3-4). При этом, однако, саму подпоследовательность найти (за время 0(то+ га)) не удаётся.

3

4 5

if Ь [г, j] = «\»

then PRiNT-LCS(6,X,i

напечатать жг-


Упражнения

16.3-1 Найдите НОП последовательностей (1,0,0,1,0,1,0,1) и (0,1,0,1,1,0,1,1,0).

16.3-2 Разработайте алгоритм, строящий НОП для X = (жь ж2,..., хт) и У = (j/i, г/2, • • •, Уп) за время 0(т + га), исходя только из таблицы с.

16.3-3 Разработайте рекурсивный вариант алгоритма LCS-Length с запоминанием ответов, требующий времени О (ran).

16.3-4 Покажите, как можно вычислить длину НОП, используя память размера 2 тш(то, га) +0(1) и храня лишь часть таблицы с. А как это сделать, используя память тш(то, га) + 0(1)?

16.3-5 Разработайте алгоритм, находящий наибольшую возрастающую подпоследовательность данной последовательности из га чисел и работающий за время О (га2).

16.3-6* Разработайте алгоритм, решающий предыдущую задачу за время О (га log га). (Указание. Храним для каждого г наименьший из последних элементов возрастающих подпоследовательностей длины г. Как меняются эти числа при добавлении нового элемента?)

16.4. Оптимальная триангуляция многоугольника

Несмотря на свою геометрическую формулировку, эта задача очень близка к задаче о перемножении матриц.

Многоугольник (polygon) - это замкнутая кривая на плоскости, составленная из отрезков, называемых сторонами (sides) многоугольника. Точка, в которой сходятся две соседние стороны, называется вершиной (vertex). Несамопересекающийся многоугольник (только такие мы и будем, как правило, рассматривать) называется простым (simple). Множество точек плоскости, лежащих внутри простого многоугольника, называется внутренностью (interior) многоугольника, объединение его сторон называется его границей (boundary), а множество всех остальных точек плоскости называется его внешностью (exterior). Простой многоугольник называется выпуклым (convex), если для любых двух точек, лежащих внутри или на границе многоугольника, соединяющий их отрезок целиком лежит внутри или на границе многоугольника.

Выпуклый многоугольник можно задать, перечислив его вершины против часовой стрелки: многоугольник Р = (vq, v\, ..., fra i)



[стр.Начало] [стр.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] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]