Динамическое программирование, алгоритмы на графах - Реферат

Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Теория графов содержит огромное количество определений, теорем и алгоритмов.Для того чтобы подсчитать количество различных разбиений числа N на произвольные натуральные слагаемые, предварительно подсчитаем количества разбиений на следующие группы слагаемых: 1) разбиения только на единицы (очевидно, что для любого числа такое разбиение единственно); 2) разбиения на единицы и двойки такие, что хотя бы одна двойка в разбиении присутствует и т.д. А именно, так как в любом из разбиений j-ой группы присутствует число j, то мы можем вычесть из N число j и сложить разбиения уже числа N - j на слагаемые, не превосходящие j. Первоначально таблица пуста (вернее заполним элементы, значение которых по формуле (*) равно 0 или 1, а остальные значения, например, числом-1). (Очевидно, что таблица симметрична относительно главной диагонали - если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски. Понятно, что для того чтобы подсчитать количество полосок длины N, удовлетворяющих заданной диаграмме смежности, необходимо знать количество допустимых полосок длины N - 1, а также количество полосок, в диаграмме смежности которых один диагональный элемент или два симметричных недиагональных элемента равны “N” вместо “Y” в исходной диаграмме.Графом называется пара , где V - некоторое множество, которое называют множеством вершин графа, а E - отношение на V () - множество ребер графа. ), то граф называют неориентированным, в противном случае граф называют ориентированным. Если в графе существует ребро (u, v), то говорят, что вершина v смежна с вершиной u (в ориентированном графе отношение смежности несимметрично). Путем из вершины u в вершину v длиной k ребер называют последовательность ребер графа . Граф называется связанным, если для любой пары его вершин существует путь из одной вершины в другую.Легко показать, что любые части кратчайшего пути также являются кратчайшими путями между соответствующими вершинами. Ведь если это не так, то есть существует отрезок кратчайшего пути, между концами которого можно построить более короткий путь, то мы можем заменить этот отрезок кратчайшего пути между вершинами u и v на более короткий, тем самым уменьшив и длину кратчайшего пути между u и v, что невозможно. Такой метрополитен удобно описывать с помощью графа, вершины которого есть линии метрополитена (а не станции!!!), а наличие ребра между вершинами i и j графа соответствует наличию пересадочной станции между линиями с номерами i и j. Представим этот граф с помощь массива множеств (переменная ss в программе), в i-м элементе этого массива содержится множество всех линий, на которые можно попасть с линии i за одну пересадку. Заметим, что если вершина n нашего графа достижима из вершины m (говорят, что они находятся в одной компоненте связности), то искомое число пересадок меньше общего количества линий nn.Зачастую суммарный вес пути, состоящего из двух, трех и более ребер может оказаться меньше веса одного ребра, поэтому даже для полного графа (то есть графа, между каждой из пар вершин которого существует ребро, а в случае ориентированного графа - два ребра, направленных в противоположные стороны) задача поиска кратчайших путей имеет смысл. A[i, j] хранится длина кратчайший пути из вершины i в вершину j, который проходит через некоторые вершины с номерами, не превосходящими k - 1. Если же длины пути из вершины i в вершину k и пути из вершины k в вершину j то таковы, что их сумма меньше, чем значение данного элемента матрицы, то его следует переопределить. Если же нам требуется найти сам кратчайший путь, а не его длину, то при каждом улучшении пути между двумя вершинами мы в соответствующем элементе вспомогательного массива (в программе - w) будем запоминать номер той вершины, через которую кратчайший путь проходит, а затем с помощью элегантной рекурсивной процедуры будем его печатать. Идея рекурсии заключается в том, что если мы знаем, что кратчайший путь от вершины i до вершины j проходит через вершину k, то мы можем обратиться к той же самой процедуре с частями пути от i до k и от k до j.Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра.

Содержание

Введение

1. Алгоритмы, использующие решение дополнительных подзадач

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

3. Поиск пути между парой вершин невзвешенного графа

4. Пути минимальной длины во взвешенном графе

Заключение

Литература

Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.

Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.

Иногда решение основной задачи приходится формулировать в терминах несколько модифицированных подзадач. Именно такие проблемы рассматриваются в данной работе.

Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.

Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.

Станкевич А.С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.

Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.

Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.

Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: “Вильямс”, 2000.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.

Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.

Вирт Н. Алгоритмы и структуры данных. Санкт-Петербург: “Невский диалект”, 2001.