Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Математический факультет
Кафедра МПМ
Реферат
Динамическое программирование, алгоритмы на графах
Исполнитель:
Студентка Старовойтова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент Лебедева М.Т.
Гомель 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 и т. ............
