|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[101] Простая оценка показывает, что время работы алгоритма Matrix-Chain-Order есть О (га3). В самом деле, число вложенных циклов равно трём, и каждый из индексов /, г и к принимает не более га значений. В упражнении 16.1-3 мы предложим вам показать, что время работы этого алгоритма есть ©(га3). Объём памяти, необходимый для хранения таблиц т и s, есть ©(га2). Тем самым этот алгоритм значительно эффективнее, чем требующий экспоненциального времени перебор всех расстановок. Шаг 4: построение оптимального решения Алгоритм Matrix-Chain-Order находит минимальное число умножений, необходимое для перемножения последовательности матриц. Осталось найти расстановку скобок, приводящую к такому числу умножений. Для этого мы используем таблицу s[l. .га, 1. .га]. В клетке s[i,j] записано место последнего умножения при оптимальной расстановке скобок; другими словами, при оптимальном способе вычисления А\.,п последним идёт умножение А1--8[1)Гг] на 4s[ijra]+i..га-Предшествующие умножения можно найти рекурсивно: значение s[l,s[l,ra]] определяет последнее умножение при нахождении А1--8[1)Гг], a s[s[l, га] + 1, га] определяет последнее умножение при вычислении 4s[ijra]+i..ra- Приведённая ниже рекурсивная процедура вычисляет произведение A4-..j, имея следующие данные: последовательность матриц А = (А\, А2,..., Ап), таблицу s, найденную процедурой Matrix-Chain-Order, а также индексы г и j. Произведение AiA2...An равно Matrix-Chain-Multiply (A, s, 1, га). Matrix-Chain-Multiply(A, s, i, j) В примере на рис. 16.1 вызов Matrix-Chain-Multiply(A, s, 1, 6) вычислит произведение шести матриц в соответствии с расстановкой скобок [Техническое замечание: следует позаботиться, чтобы при передаче массива s в процедуру не происходило копирования.] 1 2 3 4 5 if j > г then X <- Matrix-Chain-Multiply(A, s, i, s[i, j]) Y <- Matrix-Chain-Multiply(A, s, s[i, j] + 1, j) return Matrix-Multiply(A, Y) else return A{ Упражнения 16.1-1 Найдите оптимальную расстановку в задаче о перемножении матриц, если р = (5,10, 3,12, 5, 50, 6). 16.1-2 Разработайте алгоритм Print-Optimal-Parens, печатающий оптимальную расстановку скобок. (Таблица s уже вычислена алгоритмом Matrix-Chain-Order.) 16.1-3 Пусть R(i,j) обозначает количество обращений алгоритма Matrix-Chain-Order к элементу m[i,j] таблицы тп с целью вычисления других элементов таблицы [строка 9]. Покажите, что общее количество таких обращений равно 16.1-4 Покажите, что полная расстановка скобок в произведении п множителей использует ровно п-1 пар скобок. В этом разделе мы укажем два признака, характерных для задач, решаемых методом динамического программирования. Оптимальность для подзадач При решении оптимизационной задачи с помощью динамического программирования необходимо сначала описать структуру оптимального решения. Будем говорить, что задача обладает свойством оптимальности для задач (has optimal substructure), если оптимальное решение задачи содержит оптимальные решения её подзадач. Если задача обладает этим свойством, то динамическое программирование может оказаться полезным для её решения (а возможно, применим и жадный алгоритм - см. главу 17). В разделе 16.1 мы видели, что задача перемножения матриц обладает свойством оптимальности для подзадач: каждая скобка в оптимальном произведении указывает оптимальный способ перемножения входящих в неё матриц. Чтобы убедиться, что задача обладает этим свойством, надо (как в разделе 16.1) показать, что, улучшая решение подзадачи, мы улучшим и решение исходной задачи. г = 1 j = l 16.2. Когда применимо динамическое программирование Как только свойство оптимальности для подзадач установлено, обычно становится ясно, с каким именно множеством подзадач будет иметь дело алгоритм. Например, для задачи о перемножении последовательности матриц подзадачами будут задачи о перемножении кусков этой последовательности. Перекрывающиеся подзадачи Второй свойство задач, необходимое для использования динамического программирования, - малость множества подзадач. Благодаря этому при рекурсивном решении задачи мы всё время выходим на одни и те же подзадачи. В таком случае говорят, что у оптимизационной задачи имеются перекрывающиеся подзадачи (overlapping subproblems). В типичных случаях количество подзадач полиномиально зависит от размера исходных данных. В задачах, решаемых методом «разделяй и властвуй», так не бывает: для них рекурсивный алгоритм, как правило, на каждом шаге порождает совершенно новые подзадачи. Алгоритмы, основанные на динамическом программировании, используют перекрытие подзадач следующим образом: каждая из подзадач решается только один раз, и ответ заносится в специальную таблицу; когда эта же подзадача встречается снова, программа не тратит время на её решение, а берёт готовый ответ из таблицы. Вернёмся для примера к задаче о перемножении последовательности матриц. Из рисунка 16.1 видно, что решение каждой из подзадач, записанное в данной клеточке таблицы, многократно используется процедурой Matrix-Chain-Order при решении подзадач из расположенных выше клеточек. Например, га [3,4] используется четырежды: при вычислении га[2,4], га[1,4], га[3, 5] и га[3,6]. Было бы крайне неэффективно вычислять га[3,4] всякий раз заново. В самом деле, рассмотрим следующий (неэффективный) рекурсивный алгоритм, основанный непосредственно на соотношениях (16.2) и вычисляющий m[i,j] - минимальное количество умножений, необходимое для вычисления A4-..j = AiAi+i .. .Aj: Recursive-Matrix-Chain(p, i,j) 1i£i = j 2then return 0 3m[i,j] <- oo 4for k <- i to j - 1 5do g f- Recursive-Matrix-Chain(p, i, k) + + Recursive-Matrix-Chain(p, k + + pi ipkPj 6if q < m[i, j] 7then m[i,j] <- q 8return m[i,j] |
Среды: 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 | ||