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

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

Содержание

• Содержание
• Введение
• 1. Алгоритмы, использующие решение дополнительных подзадач
• 2. Основные определения теории графов
• 3. Поиск пути между парой вершин невзвешенного графа
• Пусть мы имеем произвольный граф, ориентированный или неориентированный. Если в невзвешенном графе существует путь, то назовем длиной пути количество ребер в нем. Если пути нет вообще, то расстояние считается бесконечным. Путь минимальной длины при этом называется кратчайшим путем в графе. Легко показать, что любые части кратчайшего пути также являются кратчайшими путями между соответствующими вершинами. Ведь если это не так, то есть существует отрезок кратчайшего пути, между концами которого можно построить более короткий путь, то мы можем заменить этот отрезок кратчайшего пути между вершинами u и v на более короткий, тем самым уменьшив и длину кратчайшего пути между u и v, что невозможно. Это свойство кратчайших путей позволяет решать задачу их нахождения методом динамического программирования. Покажем сначала как можно записать “волновой алгоритм” так, что задача поиска кратчайшего пути между двумя вершинами графа будет решаться за O(N2) действий.
• Задача 13. Пусть для некоторых пар переменных известно, что значение одной из них не больше значения другой. Выписать остальные пары из упомянутых переменных, для которых, используя транзитивность операции “”, можно также сказать, значение одной из них не превосходит значение другой.
• 4. Пути минимальной длины во взвешенном графе
• Заключение
• Литература