Изменения

Перейти к: навигация, поиск

Задача о порядке перемножения матриц

230 байт добавлено, 08:27, 12 декабря 2011
Нет описания правки
Как мы видим, первый способ гораздо эффективней. Теперь стало понятно, что нам надо найти оптимальную расстановку скобок в нашем выражении из <tex>n</tex> матриц.
Как бы это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнения этого алгоритма будет расти экспоненциально от <tex>n</tex> количества матриц, так как навскидку в каждую позицию мы можем поставить открывающуюся и закрывающуюся скобку, то асимптотика будет равна ''n''­-ому числу Каталана или <tex>O(2^nC_n )</tex>. Решение данной задачи, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидим, что с помощю решения однократного решения подзадачи и повторного использования ответа, мы сможем заметно сократить асимптотику.
Например, если у нас есть четыре матрицы ''ABCD'', то мы посчитаем для (''A'')(''BCD''), (''AB'')(''CD''), и (''ABC'')(''D''), делая рекурсивные вызовы на отрезках ''ABC'', ''AB'', ''CD'', и ''BCD'', чтобы найти минимальную стоимость. Потом среди них мы выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость.
Однако, если мы применим этот алгоритм, то мы обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей! Что пошло не так? Ответом на этот вопрос является то факт, что мы делаем значительное количество ненужной работы. Например, в выше описанном алгоритме, мы делали рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета ''ABC'' и ''AB''. Но нахождение наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется ''n''–ому числу Каталана (то есть <tex>O(C_n)</tex>).
=== Оптимизации динамическим программированием ===
90
правок

Навигация