|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[106] Строение оптимальной триангуляции Докажем последнее утверждение. Пусть Г - оптимальная триангуляция (га + 1)-угольника Р = (vo, v\,..., vn). Ребро vqvu входит в один из треугольников триангуляции. Пусть это треугольник AvoVkVn, где 1 k га - 1. Тогда вес триангуляции Г равен весу AvoVkVn плюс сумма весов триангуляции многоугольников (г>о, v\,..., Vk) и (vk, Vk+i,..., vn). Следовательно, триангуляции указанных многоугольников обязаны быть оптимальными, и если оптимальные стоимости для таких многоугольников (при разных к) уже вычислены, то остаётся выбрать оптимальное значение к. Рекуррентная формула Другими словами, имеет место следующая рекуррентная формула. Пусть m[i,j] - вес оптимальной триангуляции многоугольника Vi,..., Vj), где 1 г < j га. Вес оптимальной триангуляции всего многоугольника равен т[1, га]. Будем считать, что «двуугольники» (vi i,Vi) имеют вес 0. Тогда m[i, i] = 0 для г = 1,2,..., га. Если j - г 1, то у многоугольникаvi, , vj) имеется не менее трёх вершин, и нам необходимо найти минимум (по всем к из промежутка г к j - 1) такой суммы: вес Avj-ivvj, плюс вес оптимальной триангуляцииvi, •, vk), плюс вес оптимальной триангуляции (v, Vk+i,..., Vj). Поэтому Единственное отличие этой формулы от формулы (16.2) - более общий вид весовой функции. Стало быть, алгоритм Матшх-Chain-Order с указанными выше изменениями вычисляет вес оптимальной триангуляции; время работы 0(га3), объём используемой памяти 0(га2). Упражнения 16.4-1 Докажите, что всякая триангуляция выпуклого га-угольника разбивает его на га - 2 треугольника с помощью га - 3 диагоналей. 16.4-2 Профессор предполагает, что для случая, когда вес треугольника равен его площади, алгоритм нахождения оптимальной триангуляции можно упростить. Не обманывает ли его интуиция? min {m[i, к] + m[k + + w(Avi iVkVj)} при г < j. при г = j, (16.7) 16.4-3 Пусть весовая функция определена на множестве диагоналей многоугольника, и триангуляция считается оптимальной, если сумма весов входящих в неё диагоналей минимальна. Как свести эту задачу к разобранной нами (в которой веса приписывались не диагоналям, а треугольникам)? 16.4-4 Найдите оптимальную триангуляцию правильного восьмиугольника на евклидовой плоскости для случая, если весом треугольника считается его периметр. Задачи 16-1 Битоническая евклидова задача коммивояжёра Евклидова задача коммивояжёра (euclidean traveling-salesman problem) состоит в нахождении кратчайшего замкнутого пути, соединяющего данные га точек на плоскости (см. пример на рис. 16.6а, где га = 7). Эта задача является NP-полной, так что вряд ли её можно решить за полиномиальное время (см. главу 36). Дж. Бентли предложил упростить задачу, рассматривая только битонические пути (bitonic tours), т.е. пути, начинающиеся в крайней левой точке, затем идущие слева направо до крайней правой точки, а затем возвращающиеся справа налево в исходную точку. (На рис. 16.66 изображён кратчайший битонический путь через те же семь точек). Эта задача проще: постройте алгоритм решения этой задачи, требующий времени О (га2). Вы можете считать, что абсциссы всех точек различны. (Указание: просматривая точки слева направо, храните для текущей точки X и для всех предыдущих точек У длину кратчайшего пути, битонически соединяющего X с У с проходом через крайнюю левую точку.) Рис. 16.6 Семь точек на плоскости в узлах единичной решётки, (а) Кратчайший замкнутый путь (длины и 24,88), обходящий эти точки. Этот путь не является битоническим. (б) Кратчайший битонический путь, обходящий те же точки, длина и 25,58. Задачи к главе 16 329 16-2 Разбиение абзаца на строки Абзац текста состоит из п слов длиной /i,/2,...,/га (длина слова - число символов в нём). Считая, что все символы имеют равную ширину (как на пишущей машинке), мы хотим оптимальным образом разбить его на строки длиной не более М символов. Оптимальность при этом определяется так: посчитаем число «лишних» пробелов в каждой строке (то есть посмотрим, на сколько длина строки меньше М, если между словами ставить по одному пробелу) и сложим кубы этих чисел для всех строк, кроме последней: чем больше эта сумма, тем хуже абзац. Используя динамическое программирование, разработайте алгоритм оптимального разбиения абзаца на строки; оцените время его работы и требуемый объём памяти. 16-3 Стоимость редактирования Мы хотим преобразовать строку символов х[1. .то] в новую строку у[1..га] с помощью следующих операций: перенос символа из исходной строки в новую, перенос двух соседних символов из исходной строки в новую с одновременной их перестановкой («транспозиция»), добавление символа (справа) к новой строке, удаление первого символа из старой строки, замена (удаление символа из исходной строки и добавление другого символа в новую строку), наконец, удаление остатка старой строки. Вот, например, как с помощью этих операций преобразовать строку algorithm в строку altruistic: ОперацияНовая строка Старая строка перенос aalgorithm перенос 1algorithm замена g на taltorithm удаление оaltrithm перенос raltrithm добавление ualtruithm добавление ialtruiithm добавление saltruisithm транспозиция it в ti altruistihm добавление сaltruistichm удаление остаткаaltruistic Каждой из операций («перенос», «транспозиция», «добавление», «удаление», «замена» и «удаление остатка») приписана стоимость (мы предполагаем, что стоимость замены меньше, чем суммарная стоимость добавления и удаления, иначе замена была бы лишней). |
Среды: 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 | ||