Динамическое программирование, алгоритмы на графах (стр. 2 из 4)

Приведем программу для решения этой задачи, но использующую вместо “длинной арифметики” тип данных extended, сохраняющий максимально возможное количество значащих цифр (попробуйте модернизировать программу самостоятельно). То есть не для всех значений N ответ будет вычислен точно. Но, так как для получения результата используется только сложение целых чисел, потери точности при промежуточных вычислениях не будет, по крайней мере пока ответ не станет превышать 2⁶³.

{$N+}

const magic: array [1..3, 1..3] of byte =

((1, 2, 4),

(2, 8, 16),

(4, 16, 32));

var n,i,j,k,l,code: longint;

can: array [1..3, 1..3] of boolean;

total: array [0..1, 1..3, 0..63] of extended;

answer: extended;

procedure readdata;

var s: string;

i, j: byte;

begin

readln(n);

fillchar(can, sizeof(can), false);

for i:= 1 to 3 do

begin

readln(s);

for j:= 1 to 3 do

if upcase(s[j]) = 'Y' then

begin

can[i, j]:= true;

can[i, j]:= true

end

end

end;

procedure findcode;

var i, j: byte;

begin

{переводим диаграмму смежности в число}

code:= 0;

for i:= 1 to 3 do

for j:= i to 3 do

if can[i, j] then

code:= code + magic[i, j]

end;

begin

assign(input, 'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

readdata;

findcode;

fillchar(total, sizeof(total), 0);

{количество полосок длины 1}

for i:= 1 to 3 do

total[1, i, 0]:= 1;

for i:= 2 to n do

for j:= 0 to 63 do

for k:= 1 to 3 do

{cчитаем полоски длины i,

c диаграммой смежности j

и оканчивающиеся цветом k}

begin

total[i mod 2, k, j]:= 0;

for l:= 1 to 3 do

{цикл по конечному цвету

полосок длины i - 1}

if magic[k, l] and j <> 0 then

{цвета l и k могут соседствовать

согласно диаграмме смежности j}

begin

total[i mod 2, k, j]:=

total[i mod 2, k, j] +

total[1 - i mod 2, l, j];

total[i mod 2, k, j]:=

total[i mod 2, k, j] +

total[1 - i mod 2, l, j - magic[k, l]]

end

end;

answer:= 0;

{суммируем количество полосок с диаграммой

смежности code и различными окончаниями}

for i:=1 to 3 do

answer:=answer + total[n mod 2, i, code];

writeln(answer:0:0)

end.

Похожая задача (“Симпатичные узоры”) предлагалась и на I-ой Всероссийской командной олимпиаде по программированию. Ее условие и решение можно прочитать в [2].

Задача 11. Паркет (Задача VI Всероссийской олимпиады по информатике, 1994 г.)

Комнату размером N´M единиц требуется покрыть одинаковыми паркетными плитками размером 2´1 единицу без пропусков и наложений (1 £N£ 20, 1 £M£ 8). Требуется определить количество всех возможных способов укладки паркета для конкретных значений N и M.

Решение. Пусть M — ширина комнаты, которую мы зафиксируем. Попытаемся выразить искомое количество укладок паркета для комнаты длины N, через количество укладок для комнаты длиной N – 1. Однако очевидно, что сделать это не удастся, так как существует еще множество укладок, в которых часть плиток пересекает границу между такими комнатами. Следовательно нам опять придется решать дополнительное число подзадач. А именно, введем обобщенное понятие укладки комнаты длиной N – 1: первая часть комнаты длиной N – 2 уложена плотно, а в (N – 1)-й единице измерения длины комнаты могут находиться пустоты (в N-й единице измерения паркета нет). Если наличие плитки в (N – 1)-й единице измерения обозначить 1, а ее отсутствие — 0, то количество различных окончаний подобных укладок можно пронумеровать двоичными числами от 0 до 2^M – 1. Если количество укладок для каждого из окончаний нам известно (часть из них могут оказаться нереализуемыми, то есть соответствующее количество укладок будет равно 0), то мы сможем подсчитать количество различных укладок комнаты длины N. При этом придется проверять совместимость окончаний. Окончания будем считать совместимыми, если путем добавления целого числа плиток к укладе длиной N – 1 с окончанием j, таких что каждая из них увеличивает длину укладки до N, мы можем получить окончание i укладки длиной N. Если способ совмещения укладок существует, то по построению он единственен. Тогда для определения количества укладок с окончанием i длиной N необходимо просуммировать количества укладок длиной N – 1 с совместимыми окончаниями. Для комнаты нулевой длины будем считать количество укладок равным 1. Формирование динамической схемы закончено. Количество хранимых в программе значений при этом равно 2´2^M=2^M+1, то есть оно экспоненциально зависит от одного из параметров задачи и существенно его увеличить не представляется возможным. В нашем случае оно равно 512, то есть применение табличного метода решения оказывается реальным. Ответ на вопрос задачи будет получен на N-м шаге алгоритма в элементе таблицы с номером 2^M – 1. При максимальном по условию задачи размере комнаты для получения ответа опять потребуется “длинная арифметика”.

Схему программы для решения этой задачи, которая проще предыдущей, можно найти, например, в [3].

После рассмотрения задач 9-11 может сложиться впечатление, что к данному классу относятся лишь задачи подсчета количеств тех или иных конфигураций, в том числе комбинаторных. Конечно же это не так. Примером оптимизационной задачи, решение которой основано на аналогичных идеях, служит задача “Бизнес-классики”, предлагавшаяся на XIII Всероссийской олимпиаде по программированию (см. [4]).

Многие прикладные и олимпиадные задачи легко сформулировать в терминах такой структуры данных как граф. Для ряда подобных задач хорошо изучены эффективные (полиномиальные) алгоритмы их решения. Рассмотрим в данной лекции те из них, которые используют идеи динамического программирования. Но прежде необходимо познакомиться с некоторыми терминами, встречающимися при описании этой структуры.

2. Основные определения теории графов

Графом называется пара

, где V – некоторое множество, которое называют множеством вершин графа, а E – отношение на V ( ) - множество ребер графа. То есть все ребра из множества E соединяют некоторые пары точек из V.

Если отношение E симметричное (т.е.

), то граф называют неориентированным, в противном случае граф называют ориентированным. Фактически для каждого из ребер ориентированного графа указаны начало и конец, то есть пара (u, v) упорядочена, а в неориентированном графе (u, v) = (v, u).

Если в графе существует ребро (u, v), то говорят, что вершина vсмежна с вершиной u (в ориентированном графе отношение смежности несимметрично).

Путем из вершины u в вершину v длиной k ребер называют последовательность ребер графа

. Часто тот же путь обозначают последовательностью вершин . Если для данных вершин u, v существует путь из u в v, то говорят, что вершина vдостижима из u. Путь называется простым, если все вершины в нем различны. Циклом называется путь, в котором начальная вершина совпадает с конечной. При этом циклы, отличающиеся лишь номером начальной точки, отождествляются.

Граф называется связанным, если для любой пары его вершин существует путь из одной вершины в другую.

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

При программировании вершины графа обычно сопоставляют числам от 1 до N, где

- количество вершин графа, и рассматривают . Ребра нумерую числами от 1 до M, где . Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, т.е. двумерного массива, скажем A, где для невзвешенного графа (или 1), если и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти памяти был достаточен для хранения N² значений, даже если ребер в графе существенно меньше, чем N². Это не позволяет построить алгоритм со временем порядка O(N) для графов, имеющих O(N) ребер.