|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[100] Шаг 2: рекуррентное соотношение Теперь надо выразить стоимость оптимального решения задачи через стоимости оптимальных решений её подзадач. Такими подзадачами будут задачи об оптимальной расстановке скобок в произведениях Aj-..j = AjAi+i ... Aj для 1 г j га. Обозначим через m[i,j] минимальное количество умножений, необходимое для вычисления матрицы Aj-..j; в частности, стоимость вычисления всего произведения Ai..n есть га[1,га]. Числа га [г, j] можно вычислить так. Если г = j, то последовательность состоит из одной матрицы Аг-..г- = Аг- и умножения вообще не нужны. Стало быть, га[г, г] = 0 для г = 1,2,..., га. Чтобы посчитать m[i,j] для г < j, мы воспользуемся информацией о строении оптимального решения, полученной на шаге 1. Пусть при оптимальной расстановке скобок в произведении A8A8+i ... Aj последним идет умножение Аг-... А на A+i .. .Aj, где г k < j. Тогда m[i,j] равно сумме минимальных стоимостей вычисления произведений A4-..jt и Ajt+i..j плюс стоимость перемножения этих двух матриц. Поскольку для вычисления произведения A4-..jtAjt+i..j требуется pi-ipkPj умножений, В этом соотношении подразумевается, что оптимальное значение к нам известно; на деле это не так. Однако число к может принимать всего лишь j - г различных значений: г, г + 1,..., j - 1. Поскольку одно из них оптимально, достаточно перебрать эти значения к и выбрать наилучшее. Получаем рекуррентную формулу: Числа m[i,j] - стоимости оптимальных решений подзадач. Чтобы проследить за тем, как получается оптимальное решение, обозначим через s[i,j] оптимальное место последнего умножения, то есть такое к, что при оптимальном вычислении произведения АгАг 1 • • • Aj последним идет умножение Аг-.. .Аь на A+i ... Aj. Иными словами, s[i, j] равно числу к, для которого m[i, j] = m[i, к]-\-т[к + + рг 1РкрГ Шаг 3: вычисление оптимальной стоимости Пользуясь соотношениями (16.2), теперь легко написать рекурсивный алгоритм, определяющий минимальную стоимость вычисления произведения А\А2 .. .Ап (т.е. число га[1,га]). Однако время m[i,j] га[г, к] + т[к + 1, j] + рг-Хркрг )npHZ=j, min {m[i, к] + т[к + + pi-iPkPj} при i < j. (16.2) работы такого алгоритма экспоненциально зависит от га, так что этот алгоритм не лучше полного перебора. Настоящий выигрыш во времени мы получим, если воспользуемся тем, что подзадач относительно немного: по одной задаче для каждой парыдля которой 1 г j га, а всего С2 + га = 0(га2). Экспоненциальное время работы возникает потому, что рекурсивный алгоритм решает каждую из подзадач по многу раз, на разных ветвях дерева рекурсии. Такое «перекрытие подзадач» - характерный признак задач, решаемых методом динамического программирования. Вместо рекурсии мы вычислим оптимальную стоимость «снизу вверх». В нижеследующей программе предполагается, что матрица А{ имеет размер Pi-\ Xpi при г = 1, 2,..., га. На вход подаётся последовательность р = (ро, pi,..., рп), где length[p] = га + 1. Программа использует вспомогательные таблицы то[1. .га, 1. .га] (для хранения стоимостей m[i,j]) и s[l. .га, 1. .га] (в ней отмечается, при каком к достигается оптимальная стоимость при вычислении m[i,j]). Matrix-Chain-Order (р) 1га <- length\p] - 1 2for г <- 1 to га 13 return то, s Заполняя таблицу то, этот алгоритм последовательно решает задачи об оптимальной расстановке скобок для одного, двух, ... , га сомножителей. В самом деле, соотношение (16.2) показывает, что число m[i,j] - стоимость перемножения j - г + 1 матриц - зависит только от стоимостей меньшего (чем j - г + 1) числа матриц. Именно, для к = г, г + 1,..., j - 1 получается, что Аг-.. - произведение к - г + 1 < j - г + 1 матриц, a Ajt+i..j - произведение j - к < j - г + 1 матриц. Сначала (в строках 2-3) алгоритм выполняет присваивания га [г, г] <- 0 для г = 1, 2,..., га: стоимость перемножения последовательности из одной матрицы равна нулю. При первом исполнении цикла (строки 4-12) вычисляются (с помощью соотношений (16.2)) значения то[г, г+1] для г = 1,2,..., га-1 - это минимальные стоимости для последовательностей длины 2. При втором проходе вычи- 3 4 5 6 7 8 9 10 11 12 for / if q < то[г, j] Рис. 16.1 Таблицы шиз, вычисляемые процедурой matrix-chain-order для п = 6 и матриц следующего размера: матрица размер Ав 20 х 25 Таблицы повёрнуты так, что главная диагональ горизонтальна. В таблице т используются только клетки, лежащие не ниже главной диагонали, в таблице s - только клетки, лежащие строго выше. Минимальное количество умножений, необходимое для перемножения всех шести матриц, равно то[1, 6] = 15 125. Пары клеточек, заштрихованных одинаковой светлой штриховкой, совместно входят в правую часть формулы в процессе вычисления т[2,5] (строка 9 процедуры Matrix-Chain-Order): {то[2, 2] + то[3, 5] +pip2p5 = 0 + 2500 + 35 • 15 • 20 = 13000, то[2, 3] + то[4, 5] + pipsps = 2625 + 1000 + 35 • 5 • 20 = 7125, то[2, 4] + то[5, 5] + pipips = 4375 + 0 + 35 • 10 • 20 = 11375. сляются m[i, г + 2] для г = 1,2,..., га - 2 - минимальные стоимости перемножения последовательностей длины 3, и так далее. На каждом шаге значение m[i,j], вычисляемое в строках 9-12, зависит только от вычисленных ранее значений m[i, к] и т[к + На рис. 16.1 показано, как это происходит при га = 6. Поскольку мы определяем m[i,j] только для г j, используется часть таблицы, лежащая над главной диагональю. На рисунке таблицы повёрнуты (главная диагональ горизонтальна). Внизу выписана последовательность матриц. Число m[i,j] - минимальная стоимость перемножения подпоследовательности AjAi+\ .. .Aj - находится на пересечении диагоналей, идущих вправо-вверх от матрицы Ai и влево-вверх от матрицы Aj. В каждом горизонтальном ряду собраны стоимости перемножения подпоследовательностей фиксированной длины. Для заполнения клетки m[i,j] нужно знать произведения pi \pkPj для к = i, i + 1,..., j - 1 и содержимое клеток, лежащих слева-внизу и справа-внизу от m[i,j]. Аг А2 А3 А4 А5 30 х 35 35 х 15 15 х 5 5 х 10 10 х 20 |
Среды: 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 | ||