2. Алгоритмизация описанного процесса на основе (2) и (3).

Алгоритм, основанный на формулах (2)-(3), может быть реализован:

а) Схема «сверху вниз». Построение рекурсивного алгоритма.

б) Схема «снизу вверх». Построение безрекурсивного алгоритма.

Алгоритм а)

Вход: n, p[0..n]

Выход: матрица S и оптимальное значение mopt.

1. m:=∞

2. mopt:=RP(1,n)

RP(i,j) – рекурсивное перемножение матриц. Процедура возвращает значение m[i, j].

1. if m[i,j]<∞ then Return m[i, j]

2. if i=j then m[i,j]=0

3. else for k:=1 to j-1do

4. q:=RP(i,k)+RP(k+1,j)+p[i-1]*p[k]*p[j]

5. if m[i,j]>q then

6. m[i,j]:=q; s[i,k]:=k

7. return m[i,j].

Алгоритм б)

Заполняет элементы матрицы М последовательно: сначала диагональные элементы, затем наддиагональные и так далее выше. Таким образом, последним будет заполнен элемент m[1,n].

Вход: n, p[0..n]

Выход: матрица S и оптимальное значение mopt.

1. for i:=1 to n do m[i,j]=0

2. for l:=2 to n do

3. for i:=1 to n-l+1 do

4. j:=i+l-1

5. m[i,j]:=∞

6. for k:=1 to j-1 do

7. q:=m[i,k]+m[k+1,j]+c(i-1,k,j)

8. if q<m[i,j]

9. then m[i,j]:=q; s[i,j]:=k;

10. OPT:=m[1,n]

Сложность алгоритма Т(А) = О(n³).

Пример:

n=5, p=(4, 6, 5, 8, 3, 5)

Матрица М:

	1	2	3	4	5
1	0	120	280	282	342
2		0	240	210	300
3			0	120	195
4				0	120
5					0

Матрица S:

	1	2	3	4	5
1	0	1	2	1	4
2		0	2	2	4
3			0	3	4
4				0	4
5					0

m[1,2]=120, s[1,2]=1

m[2,3]=240, s[2,3]=2

m[3,4]=120, s[3,4]=3

m[4,5]=120, s[4,5]=4

m[1,3] = min = min{432, 280}=280

m[2,4] = min = min{210, 384}=210

m[3,5] = min = min{320, 195}=195

и так далее, вычислив все элементы, получаем, что m[1,5] = 342

=>

mopt=342.

A_1..5 = (A_1..4*A₅) = ( (A₁*A_2..4)*A₅) = ( (A₁*(A₂*A_3..4))*A₅) = ( (A₁*(A₂*(A₃*A₄)))*A₅).

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

Пусть задан выпуклый многоугольник со своими вершинами, перечисленными в порядке против часовой стрелки.

Определение: Триангуляцией такого многоугольника называется множество диагоналей, не имеющих общих точек, кроме вершин, разбивающих многоугольник на треугольники.

Для каждого треугольника:

T={<i, j>}_i<j={<i, j, k>}_i<j<k

{<i, j>}_i<j – множество диагоналей. Причем, мощность этого множества (то есть количество диагоналей) |{<i, j>}_i<j | = n-3.

{<i, j, k>}_i<j<k – множество всевозможных треугольников. Причем, мощность этого множества (то есть количество треугольников) |{<i, j, k>}_i<j<k | = n-2.

На множестве всех треугольников задана весовая функция C:

C : {<i, j, k>}R⁺

p : {1..n} R⁺

Приведем несколько способов задания весовой функции:

a) c(i, j, k) = |p_i-p_j|+|p_i-p_k|+|p_k-p_j|

b) c(i, j, k) = p_i* p_j* p_k

Задача: Найти триангуляцию, сумма весов треугольников которых будет минимальна.

Будем решать, используя динамическое программирование.

Теорема. («Структура оптимального решения»).

Пусть Т^* - оптимальная триангуляция n-угольника. T^*={<i, j, k>}. Пусть в этой триангуляции сторона (1,n) принадлежит треугольнику <1, k^*,n> ==>

==>

1) Если k^*=2, то часть исходной триангуляции T^*\{< 1, 2, n>} является оптимальной для многоугольника с вершинами {2, 3,…, n}.

2) Если k^*=n-1, то часть исходной триангуляции T^*\{< 1, n-1, n>} является оптимальной для многоугольника с вершинами {1, 2,…, n-1}.

3) Если 2< k^*<n-1, то исходная триангуляция состоит из оптимальных триангуляций

Т : 1..k^* и Т : k^*..n. Т Т = T^*\{< 1, k^*, n>}.

Доказательство.

Докажем свойство 3), так как свойства 1) и 2) являются частными случаями.

3)Доказывать будем методом от противного.

с(Т^*) = с(Т ) + с(Т ) + с(< 1, k^*, n>)

Если предположить, что Т -не оптимальна, то можем найти лучшую триангуляцию Т

=> первое слагаемое уменьшается, то есть получится противоречие, что Т^* - оптимальна.

Теорема доказана. ●

Убедимся, что число различных подзадач, которые возникают в ходе указанного разбиения, полиномиально зависит от размерности n (числа вершин).

T^*_1..n – триангуляция исходного многоугольника.

Надо находить оптимальные решения таких подзадач: Т^*_1..k и T^*_k..n , где k =

T^*_1..n

Т^*_1..k T^*_k..n

…

T^*_1..l T^*_l..k

Можем посчитать число таких подзадач.

1 < l <n-2

l₁ < k n

Скорость роста – квадратичная О(n²).

Вывод рекуррентного соотношения. Уравнение Беллмана.

Целевая функция – вес триангуляции. Подзадача на номере k..l.

m[k,l] – минимальное нахождение критерия на такой подзадаче. (k<l).

m[1,n] – оптимальное значение исходной задачи.

Из теоремы вытекает, что:

m[i, j] = (*)

Вводим матрицу S:

s[i,j] =

Используя (*), запишем две схемы алгоритма («сверху вниз» - рекурсивная, «снизу вверх» - безрекурсивная).

Алгоритм по схеме «Сверху вниз».

Вход: n - число вершин, с(i,j,k) –весовая функция.

Выход: матрица S, OPT.

1.m:=∞

2.OPT:=RP(1,n)

RP(i,j)

1. if m[i,j]<∞ then Return m[i,j]

2. if i=j-1 then Return 0

3. if i=j-2 then m[i,j]:=c(i, i+1, i+2)

4. else for k:=i+1 to j-1 do

5. q:=RP(i,k)+RP(k,j)+c(i,k,j)

6. if q<m[i,j]

7. then m[i,j]:=q

8. s[i,j]:=k

9. Return m[i,j]

Алгоритм по схеме «Снизу вверх».

Вход: n - число вершин, с(i,j,k) –весовая функция.

Выход: матрица S, OPT.

1. for i:=1 to n-1 do m[i,i+1]=0

2. for l:=2 to n-1 do

3. for i:=1 to n-l do

4. j:=i+l

5. m[i,j]:=∞

6. for k:=i+1 to j-1 do

7. q:=m[i,k]+m[k,j]+c(i,k,j)

8. if q<m[i,j]

9. then m[i,j]:=q; s[i,j]:=k;

10. OPT:=m[1,n]

Рассмотрим пример:

c(i,j,k) = |p_i-p_j|+|p_i-p_k|+|p_k-p_j|

Массив p[1..n] – веса вершин 1..n соответственно.

n=6

p=(3, 2, 4, 1, 5, 4)

Матрица М:

	2	3	4	5	6
1	0	4	10	16	16
2		0	6	14	14
3			0	8	10
4				0	8
5					0

Матрица S:

	2	3	4	5	6
1	0	2	2	3	3
2		0	3	3	3
3			0	4	5
4				0	5
5					0

m[i,i+2]=c(i,i+1,i+2)

s[i,i+2]:=i+1

m[1,3]=4, s[1,3]=2

m[2,4]=6, s[2,4]=3

m[3,5]=8, s[3,5]=4

m[4,6]=8, s[4,6]=5

m[1,4] = min = min{10,11}=10

m[2,5] = min = min{14,14}=14

m[3,6] = min = min{14,10}=10

m[1,5] = min = min{20,16,18}=16

m[2,6] = min = min{14,22,20}=14

m[1,6] = min = min{18,16,24,20}=16

OPT:=m[1,6]=16.

Алгоритм, который выдает на печать оптимальную триангуляцию.

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

Чтобы напечатать все треугольники поступим следующим образом: рассмотрим многоугольник i..j и его оптимальную триангуляцию T_i..j. Она состоит из треугольников

и оптимальных триангуляций:

<i, s[i,j], j>

T^*_i..s[i,j] T^*_s[i,j]..j ,

но только в том случае, если i+1 < s[i,j] < j-1.

Если s[i,j]=i+1 , то оптимальная триангуляция распадается на треугольник <i, i+1, j> и оптимальную триангуляцию T^*_i+1..j.

Если s[i,j]=j-1 , то оптимальная триангуляция распадается на треугольник <i, j-11, j> и оптимальную триангуляцию T^*_i..j-1. (i j-2)

Выдача на печать.

Вход: n, s[1..n,1..n]

Выход: на печать.

1. Рекурсивная процедура печать RPP(1,n).

RPP(i,j)

1. if i<j-1

2. then print(i,s[i,j],j)

3. if s[i,j]<j-1

4. then RPP(i,s[i,j])

5. if s[i,j]>i+1

6. then RPP(s[i,j],i)

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

Рассмотрим многоугольник i..j и его оптимальную триангуляцию T_i..j.

Во всех случаях, когда и , i..j - дает диагональ.

Вход: n, s[1..n,1..n]

Выход: на печать.

1. Рекурсивная процедура печать RPP1(1,n).

RPP1(i,j)

1. if i j-2 then

2. if i 1 j n

3. then print(i,j)

4. RPP1(i, s[i,j])

5. RPP1(s[i,j],j)

Т^*_1..6

T^*_1..3 T^*_3..6

T^*_1..2 T^*_2..3 T^*_3..5 T^*_5..6

-- -- --

T^*_3..4 T^*_4..5

-- --

То есть на печать будут выданы диагонали: <1,3>, <3,6>, <3,5>.

О связи оптимальной триангуляции с задачей перемножения матриц.

Задача о перемножении матриц – частный случай задачи оптимальной триангуляции.

Рассмотрим перемножение n-матриц A_1..n.

Поставим в соответствие всем этим матрицам многоугольник с (n+1)-вершиной, приписав каждой вершине вес.

p₀ A_1..n p_n

A₁ A_n

p₁ p_n-1

A₂ A_n-1

p₂ … … p_n-2

Весовая функция c(i, j, k) = p_i-1* p_j-1* p_k-1. Покажем, что оптимальная триангуляция решает задачу перемножения матриц. Сопоставим ребру (i, i+1) матрицу А_i, а ребру (n, n+1) –результат A_1..n.

Любой диагонали (i,j) (где i<j-1) сопоставим в соответствие матрицу A_i..j-1.

A_i A_i..j-1

p_i p_j-1

m[i,j]=m[i, k^*]+m[k^*,j]+c(i, k^*,j)

В обозначениях матрицы имеем:

m’[i, j-1]=m’[i, k^*-1]+m’[k^*,j-1]+ p_i-1* p_j-1* p_k-1.

Но p_i-1* p_j-1* p_k-1 – это формула для перемножения матриц, то есть связь найдена.