11. Динамическое программирование и его практическая реализация на примере зада-чи о порядке перемножения матриц.

 

 

            Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим.

            Из примера 4.2 следует, что если сумма размеров всех подзадач равна an/c для некоторой постоянной a>1, то рекурсивный алгоритм имеет полиномиальную временную сложность. Если же очевидное разбиение задачи размера n сводит ее к n задачам размера n-1, то рекурсивный алгоритм имеет показательную сложность. В этом случае часто можно получить более эффективные алгоритмы с помощью табличной техники, называемой динамическим программированием.

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

            В качестве примера рассмотрим вычисление произведения n матриц:

М=М1* М2*...* Мn,

где Мi - матрица с ri-1 строками и ri столбцами. Таким образом, размерности перемножаемых матриц описываются последовательностью чисел r1, r2,..., rn. Порядок, в котором перемножаются эти матрицы, может существенно сказаться на общем числе операций, требуемых для вычисления М, независимо от алгоритма, применяемого для умножения матриц.

            Обычный метод умножения [p*q]- матрицы на [q*r]-матрицу требует pqr операций. Рассмотрим произведение

М=М1 [10*20]*М2 [20*50]*М3 [50*1]*М4 [1*100].

            Порядок М=М1*2*3*М4)) потребует совершить 5000+100000+20000=125000 операций, тогда как порядок М=(М1*2*М3))*М4 потребует совершить всего 1000+200+1000=2200 операций.

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

Мi* Мi+1*...* Мj,       (1<=i<=j<=n).

При i<>j выберем k (i<=k<j). Выразим sij через sik и sk+1,j - минимальные сложности вычисления матрицы Мi* Мi+1*...* Мk с размерностью [ri-1*rk] и матрицы Мk+1* Мk+2*...* Мj с размерностью [rk*rj] соответственно.

 

 

 

            Величины sij вычисляются в порядке возрастания разностей индексов. Начинают с вычисления sii для каждого i, затем вычисляют все значения si,i+1, затем si,i+2 и т.д. Так как

(k-i)<(j-i) и (j-(k+1))<(j-i),      то при вычислении sij значения sik и sk+1,j  будут уже известны.

            На рис. 2.4 представлена программа, позволяющая определить тот порядок перемножения матриц, при котором потребуется совершить наименьшее количество операций.

Program matrix;

uses  crt;

const n0=4; r:array [0..4] of longint=(10,20,50,1,100);

type  hard=array  [1..n0,1..n0] of longint; order=array [1..n0,1..n0] of string[72];

var   s:hard; p:order;

 

Procedure found_min(i,j:integer; var k0:integer);

  var k:integer; sum:longint;

  begin

    s[i,j]:=s[i,i]+s[i+1,j]+r[i-1]*r[i]*r[j]; k0:=i;

    for k:=i+1 to j-1 do

      begin

        sum:=s[i,k]+s[k+1,j]+r[i-1]*r[k]*r[j];

        if sum<s[i,j] then

            begin s[i,j]:=sum; k0:=k end;

      end;

  end;

 

Procedure build_order(i,j,k0:integer);

  begin

      p[i,j]:='('+p[i,k0]+','+p[k0+1,j]+')'

  end;

 

var n,i,j,l,k0:integer;

BEGIN

  clrscr; n:=n0;

  for i:=1 to n do begin s[i,i]:=0; str(i,p[i,i]) end;

  for l:=1 to n-1 do

    for j:=l+1 to n do

      begin i:=j-l; found_min(i,j,k0);    

                build_order(i,j,k0) end;

  writeln(' Min number of actions: ',s[1,n],

               ';  Order of actions: ',p[1,n]);

  readln

END.

 

            Рис. 2.4.

 

            Таблица 2.1 иллюстрирует работу программы, представленной на рис. 2.4. Индексы указывают порядок заполнения таблицы.

 

Таблица 2.1.

sij

1

2

3

4

1

01

100005

12008

220010

2

 

02

10006

30009

3

 

 

03

50007

4

 

 

 

04