- •Сеть дорог можно представить в виде графа с положительными весами. Вершины
- •ПОИСК В ГРАФАХ
- •ПОИСК В ГРАФАХ
- •Кратчайшим путем между двумя вершинами s и d в сети называется такой направленный
- •Задаа́ча о кратчаа́йшем пути— задача́
- •ПОИСК КРАТЧАЙЧЕГО ПУТИ В
- •Существуют различные постановки задачи о кратчайшем пути:
- •кратчайший путь (А,B,D,F)
- •Алгоритм Дейкстры
- •Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
- •Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
- •Алгоритм Дейкстры. Поиск оптимальныхмаршрутов на графе S
- •S повтор
- •Пример
- •Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
- •Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
- •Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
- •Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
- •. Поиск оптимальных маршрутов на графе
- •Алгоритм
- •• Алгоритм Джонсона — позволяет найти кратчайшие пути между всеми парами вершин взвешенного
- •Такая весовая функция строится с помощью так называемой потенциальной функции
- •Задача о кратчайшем пути - задача поиска самого короткого пути (цепи) между двумя
- •ПОСТАНОВКА ЗАДАЧИ: Дано
- •Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени
- •Построение алгоритма
- •Построение алгоритма
- •Построение алгоритма
- •Построение алгоритма
- •Построение алгоритма
- •Построение алгоритма
- •Тем самым, мы :
- •Можно упростить сортировку.
- •Тем самым мы получаем другую форму алгоритма: отсортировать детали по минимуму из
- •Повтор
- •Повтор Алгоритм Джонсона
- •ПРИМЕР
- •ОБОЗНАЧЕНИЯ ДЛЯ ФОРМАЛЬНОЙ ПОСТАНОВКИ ЗАДАЧИ
- •Формальная постановка задачи
- •Алгоритм решения задачи Джонсона (первые 6 шагов)
- •Алгоритм Джонсона. Задача о двух станках
- •Пример. Пусть информация о времени обработки задана таблицей:
- •В итоге упорядоченная информация принимает вид
- •Время простоя второй машины (сотрудника/тестировщика) при первичном порядке равно:
- •Пример . Пусть информация о
- •Самостоятельно
- •Задача распределения работы между сотрудниками
- •Решение
- •Рассчитываем общие затраты времени на
- •Данные заносим в табл:
- •Распределение задач по командам/сотрудникам
- •Построим диаграмму Ганта
- •Построим диаграмму Ганта
- •Тогда имеем
Г
Р
А
Ф
Ы
Сеть дорог можно представить в виде графа с положительными весами. Вершины
являются дорожными развязками, а ребра дорогами, которые их соединяют. Веса ребер могут соответствовать
протяженности данного участка, времени необходимому для его преодоления или стоимости путешествия по нему.
Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например, автомагистрали). Она была формализована в понятии (идее) о магистралях.
Для реализации подхода, где одни дороги важнее других, существует множество алгоритмов. Они решают задачу поиска кратчайшего пути намного быстрее, чем аналогичные на обычных графах. Подобные алгоритмы состоят из двух этапов:
• этап предобработки. Производится предварительная обработка графа без учета начальной и конечной вершины. Обычно выполняется один раз и потом
используются полученные данные.
• этап запроса. Осуществляется запрос и поиск кратчайшего пути, при этом известны начальная и конечная вершина.
ПОИСК В ГРАФАХ
1. Поиск в глубину
Поиск в глубину стремится проникнуть подальше от исходной вершины.
Идея этого метода следующая. На каждом шагу метода:
•С текущей вершины движемся в первую вершину, смежную с текущей, в которой мы еще не были, если таковая имеется.
•Если таковой нет, то возвращаемся в вершину, с которой мы попали в текущую.
•Если же таковой нет и мы оказались в исходной вершине (возвращаться некуда), то это означает, что перебор вершин графа закончен.
ПОИСК В ГРАФАХ
2. Поиск в ширину
Этот алгоритм поиска в графе также
называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны.
Волна растекается равномерно во все стороны с одинаковой скоростью.
На i-ом шаге будут выписаны все вершины, достижимые за i ходов, если ходом считать
переход из одной вершины в другую. Метод поиска в ширину выходит из
программы поиска в глубину, если мы
заменим стек возврата на очередь.
Эта простая замена модифицирует порядок обхода вершин так, что обход идет равномерно во все стороны, а не внутрь как при поиске в
глубину.
Кратчайшим путем между двумя вершинами s и d в сети называется такой направленный простой путь из s в d, который имеет наименьший вес.
Задаа́ча о кратчаа́йшем пути— задача́
поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Значимость данной задачи определяется её различными практическими применениями. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между двумя перекрёстками. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Если сумма длин дорог между перекрёстками минимальна, тогда найденный путь самый короткий.