Динамическое программирование, алгоритмы на графах
Министерство образования Республики БеларусьУчреждение образования«Гомельский государственный университет им. Ф. Скорины»Математический факультетКафедра МПМРефератДинамическое программирование, алгоритмы на графахИсполнитель:Студентка Старовойтова А.Ю.Научный руководитель:Канд. физ-мат. наук, доцент Лебедева М.Т.Гомель 2007СодержаниеВведение1. Алгоритмы, использующие решение дополнительных подзадач2. Основные определения теории графов3. Поиск пути между парой вершин невзвешенного графа4. Пути минимальной длины во взвешенном графеЗаключениеЛитератураВведениеСуществует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач. Иногда решение основной задачи приходится формулировать в терминах несколько модифицированных подзадач. Именно такие проблемы рассматриваются в данной работе.1. Алгоритмы, использующие решение дополнительных подзадачЗадача 9. Требуется подсчитать количество различных разбиений числа N на натуральные слагаемые. Два разложения считаются различными, если одно нельзя получить из другого путем перестановки слагаемых.Решение. Для того чтобы подсчитать количество различных разбиений числа N на произвольные натуральные слагаемые, предварительно подсчитаем количества разбиений на следующие группы слагаемых: 1) разбиения только на единицы (очевидно, что для любого числа такое разбиение единственно); 2) разбиения на единицы и двойки такие, что хотя бы одна двойка в разбиении присутствует и т.д. Последнюю группу представляет само число N. Очевидно, что каждое разбиение числа N можно приписать только к одной из рассмотренных групп, в зависимости от значения j — максимального слагаемого в том или ином разбиении. Обозначим количество разбиений в каждой из групп t(N, j). Тогда искомое количество разбиений равно сумме разбиений по всем возможным группам. Введение таких подзадач приводит к несложному способу подсчета числа разбиений. А именно, так как в любом из разбиений j-ой группы присутствует число j, то мы можем вычесть из N число j и сложить разбиения уже числа N – j на слагаемые, не превосходящие j. То есть мы пришли к следующему рекуррентному соотношению:Теперь очевидно, что если мы имеем возможность завести двумерный массив размером NN, и будем заполнять его в порядке возрастания номеров строк, то задача будет легко решена. Однако легко заметить, что решения части подзадач никак не участвуют в формировании решения. Например, при вычислении количества разбиений числа 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;beginif table[n,k]<0 then{остальные элементы не пересчитываем}begintable[n,k]:=0;for i:=1 to k do
Другие файлы:
Программирование в алгоритмах
Искусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы, как комби...
Алгоритмы на графах
Основные понятия и определения алгоритмов на графах. Связные графы без циклов, свободное дерево или дерево без корня. Ориентированные графы (орграфы),...
Построение и анализ вычислительных алгоритмов
Описание:Классика Computer Science - книга Ахо, Ульмана и Хопкрофта. Шаблоны постороения эффективных алгоритмов, рассмотрены алгоритмы сортировки, пор...
Оптимизация экономических систем. Примеры и алгоритмы в среде Mathcad: Учеб. пособие
Рассматриваются схемы и методы оптимизации статических и динамических моделей экономических систем - линейное программирование, динамическое программи...
Математическое программирование
Монография содержит систематическое изложение основ математического программирования - сложившейся в последние десятилетия новой математической дисцип...
