Триангуляции и расстановки скобок

Существует удивительная связь между триангуляциями многоугольника и расстановками скобок (скажем, в произведении последовательности матриц). Проще всего объяснить эту связь с помощью деревьев.

Полной расстановке скобок соответствует так называемое дерево разбора (parse tree) выражения. На рис. 5(а) изображено дерево разбора для

((A₁(A₂A₃))(A₄(A₅A₆))). (6)

Рис. 5. Деревья разбора. (а) Дерево разбора для ((A₁(A₂A₃))(A₄(A₅A₆))), соответствующее также триангуляции на рис. 4(а). (б) Соответствие между триангуляцией многоугольника и бинарным деревом. Матрица А_i соответствует стороне (i = 1, 2,...,6). (в) Триангуляция и соответствующая ей расстановка скобок.

В его листьях стоят матрицы-сомножители, а в вершинах—их произведения: в каждой вершине стоит произведение двух выражений, стоящих в её детях.

Триангуляцию выпуклого многоугольника (v₀,v₁,...,v_n-1) также можно изобразить в виде дерева. Листьями его будут стороны многоугольника (кроме ) Остальные вершины—это диагонали триангуляции плюс сторона ; эту последнюю объявим корнем.

Построение дерева (на примере триангуляции рис. 4(а)) показано на рис. 5(6). Для начала мы смотрим, в какой треугольник попал корень . В нашем случае это . Детьми корня будем считать две другие стороны этого треугольника. Триангуляция состоит из этого треугольника и двух триангуляций оставшихся частей ((v₀,v₁,v₂,v₃) и (v₃,v₄,v₅,v₆), рис. 5(6)), причём диагонали, являющиеся детьми корня, являются сторонами этих многоугольников ( и на рис. 5(6)). Повторим для каждой из них ту же конструкцию: рассмотрим треугольник триангуляции нового многоугольника, содержащий выделенную сторону, две другие стороны этого треугольника объявим её детьми и т. д. В конце концов мы придём к бинарному дереву с п-1 листом. Действуя в обратном порядке, можно по бинарному дереву построить триангуляцию. Построенное соответствие между триангуляциями и бинарными деревьями является взаимно однозначным.

Вспоминая, что полные расстановки скобок в произведении п сомножителей находятся во взаимно однозначном соответствии с бинарными деревьями с листьями, получаем взаимно однозначное соответствие между полными расстановками скобок в произведении п матриц и триангуляциями (п + 1) -угольника. При этом матрица A в произведении A₁A₂...A_n соответствует стороне , а диагональ (1≤i<j≤n) соответствует произведению A_i..j.

Это соответствие можно понять и без деревьев. Напишем на всех сторонах триангулированного многоугольника, кроме одной, по сомножителю. Далее поступаем так: если в треугольнике две стороны уже помечены, то на третьей мы пишем их произведение. На первоначально непомеченной стороне появится полная расстановка скобок (см. пример на рис. 5(в)).

Заметим, что задача о перемножении матриц является частным случаем задачи об оптимальной триангуляции. Пусть нам нужно вычислить A₁...A_n,, где A_i является p_i-1* р_i - матрицей. Рассмотрим (n+1) -угольник Р=(v₀,v₁,...,v _n ) и весовую функцию

Тогда стоимость триангуляции будет равна числу умножений при соответствующей расстановке скобок.

Хотя задача о перемножении матриц является лишь частным случаем задачи об оптимальной триангуляции, оказывается, что алгоритм matrix-chain-order из раздела 1 легко приспособить для решения задачи о триангуляции. Надо только в его заголовке заменить р на v и строку 10 заменить на такую:

q = m[i][ k] + m[k + 1][j] + p[i]p[j]p[k]

В результате работы алгоритма m[1,n] станет равным весу оптимальной триангуляции.

Дата добавления: 2015-12-08