Задача о наибольшей общей подпоследовательности

СОДЕРЖАНИЕ

     ВСТУПЛЕНИЕ 5

     1 МАТЕМАТИЧНА ПОСТАНОВКА ЗАДАЧІ 6

     2 ПРИКЛАДИ ЗМІСТОВИХ ПОСТАНОВОК ЗАДАЧІ 8

     3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О ПЕРЕМНОЖЕНИИ МАТРИЦ 10

       3.1 Метод північно-західного кута 12

       3.2 Метод найменшого часу 13

       3.3 Оцінка складності алгоритмів 14

     4 ПРИКЛАДИ РОЗВ’ЯЗАННЯ ЗАДАЧ «ВРУЧНУ» 15

     5 РОЗВ’ЯЗАННЯ ЗАДАЧІ З ДОПОМОГОЮ EXCEL 26

     6 ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМУ 31

     ВИСНОВОК 33

     ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 34

     Додаток А 34

       Лістинг програми 34

 

ВСТУПЛЕНИЕ

      Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи—на более мелкие подзадачи и так далее, а затем собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подподзадачи по нескольку раз. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.

      В типичном случае динамическое программирование применяется к задачам оптимизации. Примерами задач динамического программирования являются задача о перемножении матриц и задача о нахождении найбольшей общей подпоследовательности. Эти задачи и методы их решения будут рассмотрены в данной работе.

 

1 ОБЩАЯ СХЕМА АЛГОРИТМА ДП

      У задачи, решаемой методом динамического программирования, может быть много возможных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи). Вообще говоря, оптимум может достигаться для нескольких разных решений.

      Общая схема алгоритма динамического  программирования:

а) описать строение оптимальных решений;

б) выписать рекуррентное соотношение, связывающее оптимальные значения параметра для подзадач;

в) двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач;

г) пользуясь полученной информацией, построить оптимальное решение.

     Основную часть работы составляют шаги а-в. Если нас интересует только оптимальное значение параметра, шаг г не нужен. Если же шаг г необходим, для построения оптимального решения иногда приходится получать и хранить дополнительную информацию в процессе выполнения шага в.

 

2 ПРИМЕРЫ СОДЕРЖАТЕЛЬНЫХ ПОСТАНОВОК ЗАДАЧ

  Задача 1. Задача об умножении последовательности матриц. Дана последовательность из n матриц <A₁,A₂,…,A_n> заданных размеров (матрица A_i, имеет размер p_i-1 р_i,); требуется найти такую (полную) расстановку скобок в произведении А₁А₂•…•A_n , чтобы вычисление произведения требовало наименьшее числа умножений.

  Задача 2. Подпоследовательность получается из данной последовательности, если удалить некоторые её элементы (сама последовательность также считается своей подпоследовательностью). Формально: последовательность Z= <z₁,z₂,…,z_n> называется подпоследовательностью последовательности Х=<x₁,x₂,…,x_n> если существует строго возрастающая последовательность индексов <i₁,i₂,…,i_k>, для которой z_j=x_ij. при всех j=1,2,...,k.

      Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей Х и Y, если Z является подпоследовательностью как X, так и Y.

        Задача о наибольшей общей  подпоследовательности (сокращенно НОП) состоит в том, чтобы найти общую подпоследовательность наибольшей длины для двух данных последовательностей Х и Y. 

 

3 АЛГОРИТМ  РЕШЕНИЯ ЗАДАЧИ О УМНОЖЕНИИ МАТРИЦ

     Шаг 1: строение оптимальной расстановки скобок

     Для начала нужно описать строение оптимальных решений. Обозначим для удобства через A_i..j матрицу, являющуюся произведением A_iA_i+1•…•A_j. Оптимальная расстановка скобок в произведении А₁А₂•…•A_n разрывает последовательность между А_k и A_k+1 для некоторого k, удовлетворяющего неравенству 1 k n. Иными словами, при вычислении произведения, диктуемом этой расстановкой скобок, мы сначала вычисляем произведения A_1..k и A_k+1..n, а затем перемножаем их и получаем окончательный ответ A_i..n. Стало быть, стоимость этой оптимальной расстановки равна стоимости вычисления матрицы A_1..k плюс стоимость вычисления матрицы A_k+1..n плюс стоимость перемножения этих двух матриц.

      Чем меньше умножений нам потребуется  для вычисления A_1..k и A_k+1..n, тем меньше будет общее число умножений. Стало быть, оптимальное решение задачи о перемножении последовательности матриц содержит оптимальные решения задач о перемножении её частей.

      Шаг 2: рекуррентное соотношение.

      Теперь  надо выразить стоимость оптимального решения задачи через стоимости оптимальных решений её подзадач. Такими подзадачами будут задачи об оптимальной расстановке скобок в произведениях A_i..j=A_iA_i+1 … A_j. Обозначим через m[i,j] минимальное количество умножений, необходимое для вычисления матрицы A_i..j; В частности, стоимость вычисления всего произведения A_i..n есть m[1,n].

      Числа m[i,j] можно вычислить так. Если i = j, то последовательность состоит из одной матрицы А_i..i=А_i и умножения вообще не нужны. Стало быть, m[i,i]=0 для i=1,2,…,m. Чтобы подсчитать m[i,j] для i< j, мы воспользуемся информацией о строении оптимального решения, полученной на шаге 1. Пусть при оптимальной расстановке скобок в произведении А_iА_i+1•…•A_j последним идет умножение А_i•…• A_k на А_k+1 •…• A_j, где i£ k£ j. Тогда m[i,j] равно сумме минимальных стоимостей вычисления произведений A_i..k и A_k+1..j плюс стоимость перемножения этих двух матриц. Поскольку для вычисления произведения A_i..kA_k+1..j требуется p_i-1p_kp_j умножений,

m[i,j]=m[i,k]+m[k+1,j]+p_ip_kp_j.

      В этом соотношении подразумевается, что оптимальное значение k нам  известно; на деле это не так. Однако число k может принимать всего лишь j-i различных значений: i, i+1,…,j-1. Поскольку одно из них оптимально, достаточно перебрать эти значения k и выбрать наилучшее. Получаем рекуррентную формулу:

  (16.2)

      Числа m[i,j]—стоимости оптимальных решений подзадач. Чтобы проследить за тем, как получается оптимальное решение, обозначим через s[i,j] оптимальное место последнего умножения, то есть такое k, что при оптимальном вычислении произведения А_iА_i+1•…•A_j последним идет умножение A_i•…•A_k на A_k+1•…•A_j. Иными словами, s[i,j] равно числу k, для которого m[i,j]=m[i,k]+m[k+1,j] +p_i-1p_kp_j,.

Шаг 3: вычисление оптимальной стоимости

      Пользуясь соотношениями (16.2), теперь легко написать рекурсивный алгоритм, определяющий минимальную стоимость вычисления произведения A₁A₂•…•A_n (т.е. число m[1,n]). Однако время работы такого алгоритма экспоненциально зависит от та, так что этот алгоритм не лучше полного перебора. Настоящий выигрыш во времени мы получим, если воспользуемся тем, что подзадач относительно немного: по одной задаче для каждой пары (i,j), для которой 1£i£ j£n, а всего С²_n + n = Q(n²). Экспоненциальное время работы возникает потому, что рекурсивный алгоритм решает каждую из подзадач по многу раз, на разных ветвях дерева рекурсии. Такое «перекрытие подзадач»— характерный признак задач, решаемых методом динамического программирования.

      Вместо  рекурсии мы вычислим оптимальную стоимость  «снизу вверх». В нижеследующей программе предполагается, что матрица A_i имеет размер р_i-1´p_i при i=1,2,..., п. На вход подаётся последовательность р=<p₀,p₁,…,p_n>, где length[p]=n+1. Программа использует вспомогательные таблицы m[l..n,1..n] (для хранения стоимостей m[i,j]) и s[l..n,1..n] (в ней отмечается, при каком k достигается оптимальная стоимость при вычислении m[i,j]). 

   Заполняя  таблицу m, этот алгоритм последовательно решает задачи об оптимальной расстановке скобок для одного, двух, ..., n сомножителей. В самом деле, соотношение (16.2) показывает, что число m[i,j]—стоимость перемножения j-i+1 матриц — зависит только от стоимостей перемножения меньшего (чем j-i+1) числа матриц. Именно, для k=i,i+1,…,j-1 получается, что A_i..k - произведение k-i+1<j-i+1 матриц, a A_k+1..j — произведение j-k<j-i+1 матриц.

   Сначала (в строках 2-3) алгоритм выполняет присваивания m[i,i] ¬0 для i =1,2,…, m: стоимость перемножения последовательности из одной матрицы равна нулю. При первом исполнении цикла (строки 4-12) вычисляются (с помощью соотношений (16.2)) значения m[i,i+1] для i=1,2,…,n-1—это минимальные стоимости для последовательностей длины 2. При втором проходе вычисляются m[i,i+2] для i=1,2,…,п-2—минимальные стоимости перемножения последовательностей длины 3, и так далее. На каждом шаге значение m[i,j], вычисляемое в строках 9-12, зависит только от вычисленных ранее значений m[i,k] и m[k+l,j].

   На  рис. 16.1 показано, как это происходит при n=6. Поскольку мы определяем m[i,j] только для i£j, используется часть таблицы, лежащая над главной диагональю. На рисунке таблицы повёрнуты (главная диагональ горизонтальна).

   Внизу выписана последовательность матриц. Число m[i,j]—минимальная стоимость перемножения А_iА_i+1•…•A_j—находится на пересечении диагоналей, идущих вправо-вверх от матрицы A_i и влево-вверх от матрицы A_j. В каждом горизонтальном ряду собраны стоимости перемножения подпоследовательностей фиксированной длины. Для заполнения клетки m[i,j] нужно знать произведения p_i+1p_kp_j для k=i,i+1,…,j-1 и содержимое клеток, лежащих слева-внизу и справа-внизу от m[i,j].

   Простая оценка показывает, что время работы алгоритма matrix-chain-order есть O(п³). В самом деле, число вложенных циклов равно трём, и каждый из индексов l,i и k принимает не более та значений. В упражнении 16.1-3 мы

     

 

предложим вам показать, что время работы этого алгоритма есть Q(n³). Объём памяти, необходимый для хранения таблиц т и s, есть Q(n²). Тем самым этот алгоритм значительно эффективнее, чем требующий экспоненциального времени перебор всех расстановок.

Шаг 4: построение оптимального решения

      Алгоритм Matrix-Chain-Order находит минимальное число умножении, необходимое для перемножения последовательности матриц. Осталось найти расстановку скобок, приводящую к такому числу умножений.

1. Для этого мы. используем таблицу s[1..п, 1..n]. В клетке s[l,n] записано место последнего умножения при оптимальной расстановке скобок; другими словами, при оптимальном способе вычисления A_1..n последним идёт умножение A_1..s[1,n] на A_s[1,n]+1..n. Предшествующие умножения можно найти рекурсивно: значение s[1,s[l,n]] определяет последнее умножение при нахождении A_1..s[1.n], a s[s[1,n]+1,n] определяет последнее умножение при вычислении _As[1,n]+1..n .Приведённая ниже рекурсивная процедура вычисляет произведение A_i..j имея следующие данные: последовательность матриц А=<A₁,А₂,…,A_n>, таблицу s, найденную процедурой matrix-chain-order, а также индексы i и j. Произведение A₁A₂ ×… ×A_n равно Matrix-Chain-

 

((A₁(A₂A₃))((A₄A₅)A₆).                     (16.3) 

 

4 ПРИКЛАДИ  РОЗВ’ЯЗАННЯ ЗАДАЧ «ВРУЧНУ»

      Приклад 1. Маємо 4 пункти виготовлення продукції  і 4 пункти споживання. На рисунку 4.1 вхідні дані до задачі. Верхні числа означають час перевезень. Нижня цифра – початковий базис, визначений методом північно-західного кута. Якщо по маршруту не перевозиться продукція, то в відповідних комірках стоять нулі.