- •Структуры и алгоритмы обработки данных
- •Алгоритмы. Основные определения
- •От задачи к программе
- •Написание программы.
- •Типы данных, структуры данных и абстрактные типы данных
- •Указатели и курсоры
- •Время выполнения программ
- •Измерение времени выполнения программы
- •Степень (порядок) роста
- •Вычисление времени выполнения программ
- •Линейные абстрактные типы данных атд «Список»
- •Реализация списков посредством массивов
- •Реализация списков с помощью указателей
- •Атд «Стек»
- •Атд «Очередь»
- •Реализация очередей с помощью циклических массивов
- •Нелинейные абстрактные типы данных Деревья
- •Порядок узлов
- •Прямой, обратный и симметричный обходы дерева
- •Помеченные деревья и деревья выражений
- •Представление деревьев с помощью массивов
- •Специальные виды множеств атд “Дерево двоичного поиска”
- •Атд "Словарь", основанный
- •Представление ориентированных графов
- •Атд для ориентированных графов
- •Задача нахождения кратчайшего пути
- •Int **c, // массив стоимостей
- •Int *d) // массив кратчайших
- •Остовные деревья минимальной стоимости
- •Обход графов
- •Поиск в ширину
- •Поиск в глубину
- •Сортировка
- •Простые схемы сортировки Метод «пузырька»
- •Сортировка вставками
- •Быстрая сортировка
- •Пирамидальная сортировка
- •«Карманная» сортировка
- •Порядковые статистики
- •Методы разработки алгоритмов. Типы алгоритмов
- •Алгоритмы «разделяй и властвуй» (метод декомпозиции)
- •Баланс подзадач
- •Динамическое программирование
- •Перемножение нескольких матриц
- •Шаг 1: строение оптимальной расстановки скобок
- •Шаг 2: рекуррентное соотношение
- •Шаг 3: вычисление оптимальной стоимости
- •Void MatrixChainOrder(int n, // кол-во матриц
- •Int p[], // размеры матриц
- •Int **s) // оптимальное k
- •Шаг 4: построение оптимального решения
- •Int **s, // таблица, полученная
- •Int I, // индексы
- •Когда применимо динамическое программирование?
- •Оптимальность для подзадач
- •Перекрывающиеся подзадачи
- •«Жадные» алгоритмы
- •"Жадные" алгоритмы как эвристики
- •Когда применим жадный алгоритм?
- •Принцип жадного выбора
- •Оптимальность для подзадач
- •Поиск с возвратом
- •Функции выигрыша
- •Метод ветвей и границ
- •Структуры данных и алгоритмы для внешней памяти
- •Внешняя сортировка
- •Хранение данных в файлах
- •Простая организация данных
- •Хешированные файлы
- •Индексированные файлы
- •Содержание
- •Глава I. Линейные абстрактные типы данных 31
- •Глава II. Сортировка 108
Шаг 2: рекуррентное соотношение
Выразим стоимость оптимального решения задачи через стоимости оптимальных решений её подзадач. Обозначим через m[i][j] минимальное количество умножений, необходимое для вычисления матрицы Аi…j, в частности, стоимость вычисления всего произведения А1…n есть m[1][n].
Числа m[i][j] можно вычислить так. Если i=j, то последовательность состоит из одной матрицы и умножения вообще не нужны. Если i<j, воспользуемся информацией полученной на шаге 1. Стоимость оптимальной расстановки равна стоимости вычисления матрицы Аi…k (это m[i][k]) плюс стоимость вычисления матрицы Аk+1…j (это m[k+1][j]) плюс стоимость перемножения этих двух матриц (это pi-1pkpj). И нам ещё нужно найти такое k, при котором вся эта сумма будет минимальной. Получаем рекуррентную формулу
Обозначим через s[i][j] оптимальное значение k для последовательности Аi…j, т.е. то k при котором значение суммы будет минимальным.
Шаг 3: вычисление оптимальной стоимости
Теперь легко написать рекурсивный алгоритм, определяющий минимальную стоимость вычисления произведения матриц (т.е. число m[1][n]). Однако, время работы такого алгоритма экспоненциально зависит от n, так что этот алгоритм ничуть не лучше полного перебора. Настоящий выигрыш по времени мы получим, если воспользуемся тем, что подзадач относительно немного: по одной задаче для каждой пары (i,j), для которой 1 i j n, а всего . Экспоненциальное время возникает потому, что рекурсивный алгоритм решает каждую из подзадач помногу раз, на разных ветвях дерева рекурсии.
Такое «перекрытие задач» – характерный признак задач, решаемых методом динамического программирования.
Вместо рекурсии мы вычислим оптимальную стоимость «снизу вверх».
Void MatrixChainOrder(int n, // кол-во матриц
long **m, // вспом. таблица для
// хранения стоимостей
Int p[], // размеры матриц
Int **s) // оптимальное k
{
int i, j, k, u;
long q;
for( i=1; i<=n; i++)
m[i][i]=0; // стоимость перемножения одной матрицы
// равна 0
for(u=2; u<=n; u++)
{
for(i=1; i<= n – u + 1; i++)
{
j=i+u-1;
m[i][j]= 1e10;// очень большое число
for(k=i;k<j;k++)
{
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
{
m[i][j] = q;
s[i][j] = k; // запоминаем место умножения
} // if
} // for k
} // for i
} // for u
} // окончание функции
Сначала алгоритм заполняет диагональные элементы матрицы m нулями, так как стоимость перемножения последовательности из одной матрицы равна 0. При первом исполнении цикла по u вычисляются значения для m[i][i+1] для i=1,2,…,n-1 – это минимальные стоимости для последовательностей длины 2. При втором проходе вычисляются m[i][i+2] для i=1,2,…,n-2 – минимальные стоимости перемножения последовательностей длины 3, и т.д. На каждом шаге значение m[i][j] зависит только от вычисленных ранее значений m[i][k] и m[k+1][j].
Вот как это происходит для n=6. Матрицы m и s:
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
|
|
2 |
3 |
4 |
5 |
6 |
|
0 |
15759 |
7875 |
9375 |
11875 |
15125 |
A1 |
|
1 |
1 |
3 |
3 |
3 |
1 |
|
0 |
2625 |
4375 |
7125 |
10500 |
A2 |
|
|
2 |
3 |
3 |
3 |
2 |
|
|
0 |
750 |
2500 |
5375 |
A3 |
|
|
|
3 |
3 |
3 |
3 |
|
|
|
0 |
1000 |
3500 |
A4 |
|
|
|
|
4 |
5 |
4 |
|
|
|
|
0 |
5000 |
A5 |
|
|
|
|
|
5 |
5 |
|
|
|
|
|
0 |
A6 |
|
|
|
|
|
|
|
Поскольку мы определяем m[i][j] только для i<=j, используется часть таблицы, лежащая над главной диагональю. m[i][j] – минимальная стоимость перемножения последовательности Аi*Аi+1*…*Аj.
Простая оценка показывает, что время работы алгоритма есть О(n3). Тем самым этот алгоритм значительно эффективнее, чем требующий экспоненциального времени перебор всех расстановок.