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