Классические задачи динамического программирования для большого числа решений на каждом шаге

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

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

1.5.1. Общая задача нахождения кратчайшего пути (Shortest Path)

Рис. 19. Пример графа для задачи кратчайшего пути

Рассмотрим граф, в котором дуги имеют длины. Требуется определить длину кратчайшего пути из одного узла в другой. Прямое решение, основанное на минимизации отдельных шагов может дать неверный результат: например, выбрав в узле (1) путь в узел (3), можно пропустить кратчайший: (1, 2, 5).

Формально задача описывается так. Имеется граф G(V, E) с узлами v_i i=1,... n и дугами e_j, которые попарно соединяют некоторые узлы. Каждой дуге приписано неотрицательное число – «длина дуги».

В задаче нужно построить матрицу L размером n ´ n, где L(i, j) является кратчайшим расстоянием между узлами i и j графа.

Алгоритм, который решает задачу, конструирует последовательность матриц L₀, L₁,..., L_k,..., L_n.

L_k (i, j) представляет кратчайший путь из i в j при условии, что путь может использовать только промежуточные узлы v₁... v_k.

По способу задания последовательности L_n = L и будет решением задачи.

L₀ инициализируется так:

L₀ (i, i) = 0;

L₀ (i, j) = расстоянию между i и j; или + ¥, если между ними дуги нет.

Предположим, мы сконструировали L_k для любого k < n. Как теперь построить L_k+1?

Как и во всех задачах динамического программирования используется идея разделения на две части. Кратчайший путь от i до j только с узлами v₁... v_k+1:

1) может не содержать v_k+1, тогда L_k+1(i, j) = L_k(i, j).

2) содержит v_k+1, тогда L_k+1(i, j) = L_k (i, k+1) + L_k (k+1, j).

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

L_k+1 (i, j) = min (L_k (i, j), L_k (i, k+1) + L_k(k+1, j))

При реализации алгоритма оказывается достаточно только одной матрицы L размером n ´ n, так как после построения L_k+1 матрица L_k оказывается больше ненужной.

Рис. 20. Программа нахождения минимального пути

# define L(i,j) A[i][j]

 

void shortest_path_length (int *A[], int n)

{

for (int k=1; k<=n; k++)

  for (int i=1; i<=n; i++)

   for (int j=1; j<=n; j++)

    if (i!= k && j!=k && L(i, j) > L(i, k)+L(k, j))

     L(i,j) = L(i,k)+L(k,j);

}

 

Этот алгоритм для выполнения требует порядка O(n^3) операций.

Эту же идею можно использовать для построения числа путей, ведущих из узла i в узел j. Для этого L₀(i, j) инициализируется так:

L₀(i, j) = 0, если пути из i в j нет;

L₀(i, j) = 1, если путь есть.

Рис. 21. Программа нахождения числа путей в графе

for (int k=1; k<=n; k++)

for (int i=1; i<=n; i++)

   for (int j=1; j<=n; j++)

    if (i!= k && j!=k)

     L(i,j) += L(i,k)*L(k,j);

 

Последнее произведение – из общего принципа комбинаторики: если из i в k ведет l  путей, а из k в j – m, то общее число путей из i в j составит l ´ m.

Сжатие информации с использованием словарного метода

Словарь – список таких слов, которые, как ожидается, будут часто использоваться в текстах. В исходном тексте группы последовательных символов, которые есть в словаре, при сжатии заменяются на индекс этого «слова» в словаре[6]. Задача – произвести такую замену, чтобы в результате текст стал самым коротким. Индексы в примерах показывают номер заменяемого слова в словаре.

Например, словарь: { ab, bde, efg }, текст: babeefg, замена дает: «b 1 e 3», то есть текст разбивается на b- ab- e- efg. Если в тексте 7 символов, то после сжатия остается 4.

Стратегии разбора

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

Например, словарь: { ab, bdef }, текст: abdef тщательный разбор дает: «ab- d- e- f» – четыре символа, а оптимальный – «a- bdef» – два символа. То есть в оптимальном разборе мы отказались на первом шаге получить самый большой выигрыш.

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

Например, для словаря { aa, aaaa, ab, baa, bccb, bccba } и текста aaabccbaaaa такая стратегия сначала определяет bccba как самый длинный фрагмент, имеющийся в словаре. Окончательный разбор строки: «a a- a- bccba- aa- a», то есть текст кодируется 5-ю символами. Тщательный разбор дает «aa-ab-c-c-baa-aa» 6 символов, тогда как оптимальный разбор есть «aa-a-bccb-aaaa» – 4 символа.

Возникает вопрос, как найти оптимальный разбор из всех существующих? Здесь также помогает метод динамического программирования. Пусть разбираемый текст имеет длину m. В каждой букве текста может быть выбор – варианты разбиения. Например, в словаре есть { abcd, ab,...}.

Обозначим L(m) длину оптимального разбиения последних m символов текста.

Таблица 3. Определение оптимального разбора строки текста

Текст	abcdefgh	Длина разбора	L(8)
вар. 1	abcd -разбор(efgh)	1 + разбор efgh	1+ L(4)
вар. 2	ab -разбор(cdefgh)	1 + разбор cdefgh	1+ L(6)
вар. 3	a -разбор(bcdefgh)	1 + разбор bcdefgh	1+ L(7)

Формула, определяющая длину разбора:

L(8) = 1 + min(L(4), L(6), L(7))

Понятно, что можно так же, как и в остальных задачах динамического программирования идти двумя путями: прямым ходом (рекурсивно) и обратным ходом. Во втором случае разбор начинается справа – для текста длиной 1, 2,...

Очевидно, для текста длиной в один символ L(1) = 1.

Для текста длиной m (m = 2...) нужно перебрать возможные с его начала слова и найти наименьший разбор остальной части.

L(m) = 1 + min (L(m-l₁), L(m-l₂),...)

1.6. Применение динамического программирования в теории игр на примере игры Ним

Ним – математическая игра[7], в которой два игрока по очереди вынимают предметы из кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. В стандартном варианте игры выигрывает тот, кто берёт последний предмет, а число кучек равно трём. Эта игра появилась в Китае, название ей дал Чарльз Бутон, который разработал современную математическую теорию.

Однако, как показывает анализ, реализация стратегии игры вполне возможна и на основе динамического программирования. В этой игре при начальном распределении предметов по кучкам I, J, K возможно I ´ J ´ K различных состояний игры. В некоторых состояниях у игрока, который выполняет ход, не существует стратегии, которая приведет к выигрышу, например, в конце игры при распределении по кучкам (0, 0, 1) у игрока единственный ход, и он приводит к проигрышу. Обозначим такие состояния знаком «–».

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

Матрица состояний игры w(i, j, k) может быть легко построена, исходя из следующих соображений:

1. w(i, j, k) = w(j, i, k) = w(k, i, j) =... и т.д. в силу того, что ни у одной кучки нет преимуществ, поэтому можно получать w(i, j, k) только для i<= j<= k.

2. w(0,0,1) = «–»

3. w (i, j, k) = «+», если существует такое m, что w(i- m, j, k), w(i, j- m, k) или w(i, j, k- m) = «–», в противном случае w(i, j, k) = «–».

Программа заполнения таблицы и выполнения оптимального представлена на (Рис. 23).

Задание. Построить матрицу состояний для игры с двумя кучками по 4 предмета (решение на Рис. 22).

Рис. 22. Матрица состояний игры Ним для двух кучек

 

w	0	1	2	3	4
0	+	–	+	+	+
1	–	+	+	+	+
2	+	+	–	+	+
3	+	+	+	–	+
4	+	+	+	+	–

 

Очевидно, что выигрышной стратегией для такой матрицы является следующая: для любого состояния (i, j) ищется по строке или столбцу состояние '–', если оно существует, то выбираются предметы в первой (по строке) или второй (по столбцу) кучке, чтобы достичь такого состояния. Если в строке или столбце '–' не существует, это значит, что мы сейчас находимся в таком состоянии '–', при любой нашей игре и при правильной игре противника мы проиграем.

Рис. 23. Нахождение оптимального хода для игры Ним

void init ()                    // Инициализация

{

w[0][0][0] =’+’;

w[0][0][1] = w[0][1][0] = w[1][0][0] = ’–’;

for (i=0; i<=N; i++)

for (j=0; j<=i; j++)

for (k=0; k<=j; k++)

{

   c = ’–’;

   for (m = 0; m<i; m++)

     if (w[m][j][k]== ’–’) c = ’+’;

   for (m = 0; m<j; m++)

     if (w[i][m][k]== ’–’) c = ’+’;

   for (m = 0; m<k; m++)

     if (w[i][j][m]== ’–’) c = ’+’;

   w[i][j][k] =

   w[i][k][j] =

   w[k][i][j] =

   w[j][i][k] =

   w[k][j][i] =

   w[j][k][i] = c;

}

}

void step (int &i, int &j, int &k) // Выполнение хода

{

if (w[i][j][k]==’–’)

{

if (i) i--; else if (j) j--; else if (k) k--;

return;

}

int m;

for (m = 0; m<i; m++)

if (w[m][j][k]== ’–’) {i = m; return;}

for (m = 0; m<j; m++)

if (w[i][m][k]== ’–’) {j = m; return;}

for (m = 0; m<k; m++)

if (w[i][j][m]== ’–’) {k = m; return;}

}

 

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

Задание. Изменить текст программы, чтобы она могла играть с четырьмя кучками предметов.