Метод динамического программирования

Var

Begin

Var

Тип Variant

Else

If4 inB then

Else

writeln('4 Is Not in C');

writeln(' 4 Is in B')

writeln('4 Is Not in B');

ShowElementsOfSet('A', A);

ShowElementsOfSet('B', B);

P:= A + B;

ShowElementsOfSet('A+B', P);

P:= A - B;

ShowElementsOfSet('A-B', P);

ShowElementsOfSet('A*B', A * B + [0]);

readln;

end.

V1, V2, V3, V4: Variant;

I: Integer; D: Double; S: string;

V1:= 1; // integer value, integer type

V2:= 1234.5678; // real value, real type

V3:= ‘1000’; // string value, string type

V4:= V1 + V2 + V3; // double value 2235.5678, double type

I:= V1;

D:= V2;

S:= V3; // S=’1000’

I:= V4; // I = 2236

end;

Delphi: Help, “ Variant type conversions ”

VB6, VBA-MS/Office: Тип Variant разрешен.

VBScript: Все переменные есть переменные типа Variant.

VB.Net: Тип Variant запрещен.

Тип «Денежный»

x: Currency;

Диапазон изменения: –922337203685477.5808 .. 922337203685477.5807

Объем памяти: 8 байт.

Пример. Найти наиболее «дешевый» путь от элемента матрицы размера до элемента . Второй способ решения задачи.

Проект ProjectBoth прилагается. В нём реализованы оба подхода к решению задачи.

Идея метода динамического программирования состоит в следующем. Для каждого элемента строится оптимальный путь от него до конца пути. Сначала это делается для всех элементов, которые в одном шаге от конца пути. Затем для всех элементов, которые в двух шагах от конца пути. Затем для всех элементов, которые в трёх шагах от конца пути. И так далее.

Пусть матрица цен имеет размер и выглядит так:

Пусть есть цена оптимального пути от элемента до конца пути.

Множество предпоследних элементов (1-я волна):

, двигаться можно только вниз;

, двигаться можно только вправо.

Множество «предпредпоследних» элементов (2-я волна):

, двигаться можно только вниз;

, двигаться лучше вправо;

, двигаться можно только вправо.

Множество «предпредпредпоследних» элементов (3-я волна):

, двигаться можно только вниз;

, двигаться лучше вниз;

, двигаться лучше вправо;

, двигаться можно только вправо.
Таким образом, можно найти цены и начальное направления оптимального пути для всех «волн», а значит, и для всех элементов матрицы, заканчивая элементом . Результат поиска показан в виде постановки при каждом элементе матрицы двух индексов: цена оптимального пути от этого элемента до конца (нижний индекс), направление оптимального пути от этого элемента (верхний индекс).

Дата добавления: 2014-01-04