Динамическое программирование, алгоритмы на графах (стр. 1 из 4)
Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Математический факультет
Кафедра МПМ
Реферат
Динамическое программирование, алгоритмы на графах
Исполнитель:
Студентка Старовойтова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент Лебедева М.Т.
Гомель 2007
Содержание
Введение
1. Алгоритмы, использующие решение дополнительных подзадач
2. Основные определения теории графов
3. Поиск пути между парой вершин невзвешенного графа
4. Пути минимальной длины во взвешенном графе
Заключение
Литература
Введение
Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.
Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.
Иногда решение основной задачи приходится формулировать в терминах несколько модифицированных подзадач. Именно такие проблемы рассматриваются в данной работе.
1. Алгоритмы, использующие решение дополнительных подзадач
Задача 9. Требуется подсчитать количество различных разбиений числа N на натуральные слагаемые. Два разложения считаются различными, если одно нельзя получить из другого путем перестановки слагаемых.
Решение. Для того чтобы подсчитать количество различных разбиений числа N на произвольные натуральные слагаемые, предварительно подсчитаем количества разбиений на следующие группы слагаемых: 1) разбиения только на единицы (очевидно, что для любого числа такое разбиение единственно); 2) разбиения на единицы и двойки такие, что хотя бы одна двойка в разбиении присутствует и т.д. Последнюю группу представляет само число N. Очевидно, что каждое разбиение числа N можно приписать только к одной из рассмотренных групп, в зависимости от значения j — максимального слагаемого в том или ином разбиении. Обозначим количество разбиений в каждой из групп t(N, j). Тогда искомое количество разбиений равно сумме разбиений по всем возможным группам. Введение таких подзадач приводит к несложному способу подсчета числа разбиений. А именно, так как в любом из разбиений j-ой группы присутствует число j, то мы можем вычесть из N число j и сложить разбиения уже числа N – j на слагаемые, не превосходящие j. То есть мы пришли к следующему рекуррентному соотношению:
Теперь очевидно, что если мы имеем возможность завести двумерный массив размером N´N, и будем заполнять его в порядке возрастания номеров строк, то задача будет легко решена. Однако легко заметить, что решения части подзадач никак не участвуют в формировании решения. Например, при вычислении количества разбиений числа 10 на слагаемые будут получены, но не использованы значения t(9, j) для j = 2..9 и т. д. Для того чтобы не производить лишних вычислений, применим динамическое программирование “сверху вниз” (все предыдущие задачи решались “снизу вверх”). Для этого задачу будем решать все же рекурсивно, используя формулу (*), но ответы к уже решенным подзадачам будем запоминать в таблице. Первоначально таблица пуста (вернее заполним элементы, значение которых по формуле (*) равно 0 или 1, а остальные значения, например, числом -1). Когда в процессе вычислений подзадача встречается первый раз, ее решение заносится в таблицу. В дальнейшем решение этой подзадачи берется из таблицы. Таким образом мы получили прием улучшения рекурсивных алгоритмов, а “лишние” подзадачи теперь решаться не будут.
Приведем программу для решения этой задачи.
var i,j,k,n:byte;
sum:longint;
table:array[1..120,1..120] of longint;
function t(n,k:byte):longint;
var i,s:byte;
begin
if table[n,k]<0 then
{остальные элементы не пересчитываем}
begin
table[n,k]:=0;
for i:=1 to k do
inc(table[n,k],t(n-k,i))
end;
t:=table[n,k]
end;
begin
read(n);
fillchar(table,sizeof(table),0);
for i:=1 to n do
begin
table[i,i]:=1;
table[i,1]:=1
end;
{неопределенные элементы метим –1}
for i:=2 to n do
for j:=2 to i-1 do
table[i,j]:=-1;
sum:=0;
for i:=1 to n do
sum:=sum+t(n,i);
writeln('sum=',sum)
end.
Задача 10. Плитки (Чемпионат школьников по программированию, Санкт-Петербург, 1999 г.).
У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1´1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:
| К | К | К | С | З | К | К | З | К | С |
(Буквой К обозначена красная плитка, С – синяя, З – зеленая)
После этого Петя заполняет следующую таблицу, которая в данном примере выглядит так:
| Красный | Синий | Зеленый | |
| Красный | Y | Y | Y |
| Синий | Y | N | Y |
| Зеленый | Y | Y | N |
В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Помогите Пете узнать, сколько различных полосок имеет определенную диаграмму смежности (заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска
| С | К | З | К | К | З | С | К | К | К |
не совпадает с полоской, приведенной в начале условия.)
Первая строка входного файла содержит число N. (
). Следующие три строки входного файла, содержащие по три символа из набора {“Y”, “N”}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.Выведите в выходной файл количество полосок длины N, имеющих приведенную во входном файле диаграмму смежности. Ниже дан пример входного и выходного файлов.
| Input.txt | Output.txt |
| 10YYYYNYYYN | 4596 |
Решение. Очевидно, что перебор всех возможных полосок в данной задаче невозможен, так как их количество может составить 2100, поэтому следует попытаться найти динамическую схему решения. Понятно, что для того чтобы подсчитать количество полосок длины N, удовлетворяющих заданной диаграмме смежности, необходимо знать количество допустимых полосок длины N – 1, а также количество полосок, в диаграмме смежности которых один диагональный элемент или два симметричных недиагональных элемента равны “N” вместо “Y” в исходной диаграмме. Далее, при рассмотрении полосок длины N – 2, потребуется знать количество полосок, удовлетворяющих еще большему количеству диаграмм смежности и т. д. В результате на каком то шаге нам может понадобиться информация о количестве полосок практически со всеми возможными диаграммами. Общее количество последних составляет 26 = 64 (уникальными, то есть не повторяющимися, а, значит, определяющими количество различных диаграмм, являются только 6 элементов). Так как при увеличении длины полоски диаграмма может измениться в зависимости от сочетания цветов в последнем (новом) и предпоследнем элементах, подсчитывать полоски следует отдельно для трех различных конечных элементов. Таким образом количество хранимой информации возрастает до 64´3 = 192 значений. Столько же значений будет получено в результате пересчета. Но благодаря тому, что количество полосок длины i выражается только через количество полосок длины i – 1, хранить нужно лишь эти 2´192 = 384 значения. Несмотря на малый размер таблицы (массив total в программе) следует отметить, что ее размер экспоненциально зависит от одного из входных параметров — количества цветов k, а именно: 2´k´2k(k+1)/2. Например, для 8 цветов необходимо было бы хранить 240 элементов, что нереально. Этим данная задача отличается от рассмотренных ранее.
Осталось обсудить некоторые технические приемы, позволяющие написать довольно простую программу, реализующую описанный алгоритм. Если мы поставим в соответствие каждому из уникальных мест в диаграмме смежности свою степень двойки от 20 до 25 (см. массив констант magic в программе), то каждой диаграмме может быть поставлен в соответствие номер от 0 до 63, равный сумме тех степеней двоек, которые соответствуют значениям “Y” (см. процедуру findcode). Если мы подсчитываем количество полосок для диаграммы с номером j, то совместимость добавляемого цвета k стоявшему ранее последним цвету l согласно диаграмме j можно проверить так: magic[k, l] and j <> 0. Данное условие, построенное с помощью битовой операции над целыми числами and, означает наличие в j-ой диаграмме смежности элемента “Y” на пересечении k-й строки и l-го столбца (соответствующая степень двойки массива magic содержится в двоичном представлении числа j). Выражение j - magic[k, l] соответствует замене в диаграмме с номером j упомянутого элемента “Y” на “N” (по другому это выражение можно было бы записать как j xor magic[k, l]). Подробнее о битовых операциях над целыми числами можно прочитать в [1]. Последний прием заключается в том, что мы не будем на каждом шаге переприсваивать полученные значения элементам массива, предназначенного для хранения результатов предыдущего шага. Для этого результаты для полосок четной длины i будем помещать в половину массива total с первым индексом 0, а нечетные — с индексом 1. В любом из этих случаев значения предыдущего шага доступны по индексу [1 – i mod 2]. Кроме того, ответ на решение этой задачи при всех N, удовлетворяющих условию, требует самостоятельной организации вычислений с помощью так называемой “длинной арифметики” (см., например, [1, 3]).