|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[105] Рис. 16.4 Две триангуляции выпуклого семиугольника. Каждая делит семиугольник на 7 - 2 = 5 треугольников с помощью 7 - 3 = 4 диагоналей. имеет га сторон vqV\, щщ, , vn-\vn. Здесь vn - то же самое, что vo (удобно нумеровать вершины га-угольника вычетами по модулю га). Если Vi и Vj - две вершины, не являющиеся соседними, отрезок npvj называется диагональю (chord) многоугольника. Диагональ npvj разбивает многоугольник на два: (иг-, ..., Vj) и (vj, Vj+i,..., Vi). Триангуляция (triangulation) многоугольника - это набор диагоналей, разрезающих многоугольник на треугольники; сторонами этих треугольников являются стороны исходного многоугольника и диагонали триангуляции. На рис. 16.4 изображены две триангуляции семиугольника. (Триангуляцию можно также определить как максимальное множество диагоналей, не пересекающих друг друга.) Во всех триангуляциях га-угольника одно и то же число треугольников (сумма всех углов многоугольника равна произведению 180° и числа треугольников в триангуляции), а именно га - 2. При этом используются га -3 диагонали (проводя диагональ, мы увеличиваем число частей на 1). Задача об оптимальной триангуляции (optimal triangulation problem) состоит в следующем. Дан выпуклый многоугольник Р = (vo, v\,..., vn-\) и весовая функция w, определённая на множестве треугольников с вершинами в вершинах Р. Требуется найти триангуляцию, для которой сумма весов треугольников будет наименьшей. Естественный пример весовой функции - функция w(AviVjVk) = \vtv3\ + \vjVk\ + \vkVi\, где \viVj\ обозначает (евклидово) расстояние между иг- и Vj. Мы построим алгоритм решения этой задачи, который применим для 16-5.3 Рис. 16.5 Деревья разбора, (а) Дерево разбора для ((АДАгАзААбАб))), соответствующее также триангуляции на рис. 16.4а. (б) Соответствие между триангуляцией многоугольника и бинарным деревом. Матрица А, соответствует стороне v,-iv, (г = 1,2,..., 6). (в) Триангуляция и соответствующая ей расстановка скобок. любой весовой функции. Триангуляции и расстановки скобок Существует удивительная связь между триангуляциями многоугольника и расстановками скобок (скажем, в произведении последовательности матриц). Проще всего объяснить эту связь с помощью деревьев. Полной расстановке скобок соответствует так называемое дерево разбора (parse tree) выражения. На рис. 16.5а изображено дерево разбора для В его листьях стоят матрицы-сомножители, а в вершинах - их произведения: в каждой вершине стоит произведение двух выражений, стоящих в её детях. Триангуляцию выпуклого многоугольника (г>о, v±,..., vn-\) также можно изобразить в виде дерева. Листьями его будут стороны многоугольника (кроме vovn-\). Остальные вершины - это диагонали триангуляции плюс сторона vovn-\; эту последнюю объявим корнем. Построение дерева (на примере триангуляции рис. 16.5а) показано на рис. 16.56. Для начала мы смотрим, в какой треугольник попал корень vovn-\. В нашем случае это Диозб- Детьми корня (((АзАзЖААб))). будем считать две другие стороны этого треугольника. Триангуляция состоит из этого треугольника и двух триангуляции оставшихся частей ({vo, v\, v3) и (v3, V4, v$, vq), рис. 16.56), причём диагонали, являющиеся детьми корня, являются сторонами этих многоугольников (Щуйз и V3V6 на рис. 16.56). Повторим для каждой из них ту же конструкцию: рассмотрим треугольник триангуляции нового многоугольника, содержащий выделенную сторону, две другие стороны этого треугольника объявим её детьми и т. д. В конце концов мы придём к бинарному дереву с га - 1 листом. Действуя в обратном порядке, можно по бинарному дереву построить триангуляцию. Построенное соответствие между триангуляциями и бинарными деревьями является взаимно однозначным. Вспоминая, что полные расстановки скобок в произведении га сомножителей находятся во взаимно однозначном соответствии с бинарными деревьями с га листьями, получаем взаимно однозначное соответствие между полными расстановками скобок в произведении га матриц и триангуляциями (га + 1)-угольника. При этом матрица А{ в произведении А\А2 ... Ап соответствует стороне vTZTvi, а диагональ Vi \Vj (1 г < j га) соответствует произведению Это соответствие можно понять и без деревьев. Напишем на всех сторонах триангулированного многоугольника, кроме одной, по сомножителю. Далее поступаем так: если в треугольнике две стороны уже помечены, то на третьей мы пишем их произведение. На первоначально непомеченной стороне появится полная расстановка скобок (см. пример на рис. 16.5в). Заметим, что задача о перемножении матриц является частным случаем задачи об оптимальной триангуляции. Пусть нам нужно вычислить А\А2 .. .Ап, где А{ является Pi-\ X рг-матрицей. Рассмотрим (га + 1)-угольник Р = (vq, v\, ..., vn) и весовую функцию Тогда стоимость триангуляции будет равна числу умножений при соответствующей расстановке скобок. Хотя задача о перемножении матриц является лишь частным случаем задачи об оптимальной триангуляции, оказывается, что алгоритм Matrix-Chain-Order из раздела 16.1 легко приспособить для решения задачи о триангуляции. Надо только в его заголовке заменить р на v и строку 9 заменить на такую: 9do q <- m[i, k] + m[k + 1, j] + w(Avi iVkVj) В результате работы алгоритма m[l,ra] станет равным весу оптимальной триангуляции. А. w(AviVjVk) = PtPjPk- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||