План:

Введение

• 1 Алгоритм
  • 1.1 Сохранение кратчайших путей
  • 1.2 Изменение веса
  • 1.3 Основная процедура
• 2 Сложность
Литература

Введение

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

1. Алгоритм

Дан граф G = (V ,E ) с весовой функцией . Если веса всех рёбер ω в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся рёбра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество рёбер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов рёбер , должно удовлетворять следующим свойствам.

1.1. Сохранение кратчайших путей

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

Пусть - произвольный путь из вершины v 0 в вершину v k . p является кратчайшим путем с весовой функцией ω тогда и только тогда, когда он является кратчайшим путем с весовой функцией , то есть равенство равносильно равенству . Кроме того, граф G содержит цикл с отрицательным весом с использованием весовой функции ω тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции .

1.2. Изменение веса

1.3. Основная процедура

В алгоритме Джонсона используется алгоритм Беллмана - Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возврашает обычную матрицу D = d i j размером , где , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

Алгоритм Джонсона

Строится граф G " if Bellman_Ford = FALSE then print «Входной граф содержит цикл с отрицательным весом» else for для каждой do присвоить величине h (v ) значение , вычисленное алгоритмом Беллмана - Форда for для каждого ребра do for для каждой вершины do вычисление с помощью алгоритма Дейкстры величин для всех вершин for для каждой вершины do return D

2. Сложность

Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона равно O (V 2 logV + V E ) . При более простой реализации неубывающей очереди с приоритетами время работы становится равным O (V E logV ) , но для разреженных графов эта величина в асимптотическом пределе ведёт себя лучше, чем время работы алгоритма Флойда - Уоршелла.

скачать
Данный реферат составлен на основе статьи из русской Википедии . Синхронизация выполнена 20.07.11 23:27:10
Похожие рефераты:

Ссылки

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. - 2-е изд. - М .: Издательский дом «Вильямс» , 2007. - С. 726. - ISBN 5-8459-0857-4.
• Томас Х. Кормен и др. Алгоритмы: построение и анализ. - 1-е изд. - М .: МЦНМО , 2004. - С. 523. - ISBN 5-900916-37-5.

Просмотр этого шаблона Алгоритмы поиска на графах Неинформированные методы Информированные методы – Ваше святейшество, Вы прекрасно владеете латынью... В таком случае Вы должны знать, что слово «HАERESIS» по латыни означает ВЫБОР или АЛЬТЕРНАТИВА? Как же Вам удаётся совмещать два столь несовместимых понятия?.. Что-то не видно чтобы Вы оставляли кому-то право свободного выбора! Или хотя бы уж малейшую альтернативу?.. – горько воскликнула я. – Человек ДОЛЖЕН иметь право верить в то, к чему тянется его душа. Вы не можете ЗАСТАВИТЬ человека верить, так как вера идёт от сердца, а не от палача!.. Караффа минуту удивлённо разглядывал меня, как будто перед ним стояло какое-то невиданное животное... Потом, стряхнув с себя оцепенение, тихо сказал: – Вы намного опаснее, чем я думал, мадонна. Вы не только слишком красивы, Вы также слишком умны. Вы не должны существовать за пределами этих стен... Или не должны существовать вообще, – и уже обернувшись к палачу, – Продолжай! Крики Джироламо проникали в самые глубокие уголки моей умирающей души и, взрываясь там ужасающей болью, рвали её на части... Я не знала, сколько Караффа намеревался мучить его, перед тем, как уничтожить. Время ползло нескончаемо медленно, заставляя меня тысячу раз умирать... Но почему-то, несмотря ни на что, я всё ещё оставалась живой. И всё ещё наблюдала... Страшные пытки заменялись пытками пострашней. Этому не было конца... От прижиганий огнём перешли к дроблению костей... А когда закончили и это, начали уродовать плоть. Джироламо медленно умирал. И никто не объяснил ему – за что, никто не счёл нужным хотя бы что-то сказать. Его просто-напросто методично медленно убивали на моих глазах, чтобы заставить меня делать то, что желал от меня новоизбранный глава святой христианской церкви... Я пыталась мысленно говорить с Джироламо, зная, что уже не удастся что-то по-другому ему сказать. Я хотела проститься... Но он не слышал. Он был далеко, спасая свою душу от нечеловеческой боли, и никакие мои старания не помогали... Я посылала ему свою любовь, стараясь окутать ею его истерзанное тело и хоть как-то уменьшить эти нечеловеческие страдания. Но Джироламо лишь смотрел на меня помутневшими от боли глазами, будто цеплялся за единственную тончайшую ниточку, связывающую его с этим жестоким, но таким дорогим ему, и уже ускользавшим от него миром... Караффа бесился. Он никак не мог понять, почему я оставалась спокойной, так как прекрасно знал, что своего мужа я очень и очень любила. «Святейший» Папа горел желанием меня уничтожить... Но не физически. Он хотел всего лишь растоптать мою душу, чтобы полностью подчинить моё сердце и ум своим странным и необъяснимым желаниям. Видя, что мы с Джироламо не спускаем друг с друга глаз, Караффа не выдержал – он заорал на палача, приказывая выжечь моему мужу его чудесные глаза... Мы со Стеллой застыли... Это было слишком ужасно, чтобы наши детские сердца, какими бы закалёнными они не являлись, смогли это принять... Бесчеловечность и ужас происходящего пригвоздили нас на месте, не позволяя дышать. Этого не могло происходить на Земле!!! Просто не могло! Но бесконечная тоска в золотых глазах Изидоры нам кричала – могло!!! Ещё как могло!.. И мы лишь бессильно наблюдали дальше, не решаясь вмешиваться, задавая какие-нибудь глупые вопросы. На какое-то мгновение, моя душа упала на колени, прося пощады... Караффа, сразу же это почувствовав, удивлённо впился в меня горящими глазами, не веря в свою победу. Но тут же понял, что слишком быстро обрадовался... Сделав над собой невероятное усилие и собрав всю свою ненависть, я взглянула прямо ему в глаза... Караффа отшатнулся, получив сильнейший мысленный удар. На секунду в его чёрных глазах промелькнул испуг. Но так же быстро исчез, как и появился... Он был на редкость сильным и волевым человеком, который восхитил бы, если бы не был до такой степени ужасным... Моё сердце сжалось в дурном предчувствии... И тут же, получив одобрительный кивок от Караффы, палач, как мясник, спокойно нанёс прямо в сердце беспомощной жертвы точный удар... Мой любимый муж, мой нежный Джироламо перестал существовать... Его добрая душа улетела туда, где не было боли, где было всегда спокойно и светло... Но я знала, что он будет ждать меня и там, когда бы я не пришла.

В задаче Джонсона общее время производственного цикла зависит от порядка запуска деталей в обработку. Пусть имеется n деталей, каждая из которых должна последовательно пройти обработку сначала на первом, затем на втором станке. Предполагается заданным время t ij обработки i -й детали на j -м станке (i=1,2,...,n; j=1,2). Требуется определить такой порядок запуска деталей, при котором общая длительность их обработки на обоих станках будет минимальной.

Назначение сервиса . С помощью онлайн калькулятора можно решить задачу Джонсона для частного варианта ее постановки, когда число станков n=2 . При этом рассчитывается длительность совокупного производственного цикла для найденной оптимальной очередности запуска деталей в обработку. Результаты вычислений оформляются в отчете формата Word (Пример оформления).

ИНСТРУКЦИЯ . Для решения задачи необходимо задать количество деталей (строк).

Количество строк

Вставьте данные из Excel (A - первый столбец,B - второй столбец), нажмите Далее.

Правило Джонсона

Вначале детали, подлежащие обработке, условно делят на две группы. В первую группу относят детали, для которых время обработки на первом станке не превышает времени обработки на втором станке. Остальные детали образуют вторую группу. Вначале следует обрабатывать детали первой группы в порядке возрастания длительности их обработки на первом станке. Затем должны обрабатываться детали второй группы в порядке убывания времени их обработки на втором станке.

Алгоритм Джонсона

1. В обработку сначала запускают детали, требующие минимальное время обработки на первом станке в порядке возрастания этого времени.
2. В обработку запускаются сначала детали, требующие максимальное время обработки на последнем станке в порядке убывания этого времени.
3. В обработку запускаются сначала детали, у которых “узкое место” находится дальше от начала процесса обработки (“узким местом” для данной детали называется станок, на котором обработка этой деталей занимает наибольшее время).
4. Обрабатываются вначале детали, у которых суммарное время обработки на всех станках максимальное в порядке убывания этого времени.

Исходные данные и искомые величины при составлении расписаний. Понятие регулярного критерия.

Постановка задачи в ТР начинается с описания система устройств и множества работ. Для простого процесса обслуживания система обслуживающих устройств(ОУ) описывается их числом, то есть есть m устройств, n работ. F[i] – работа, а i номер работы в расписании. Исходные данные:

ti – длительность выполнения операции, то есть длина интервала времени, требуемого iым устройством для выполнения работы(аргумент)

Регулярные критерии позволяют сравнивать расписания
3. Упорядочение работ для одной машины. Искусственные простои и прерывания. Перестановочные расписания.

Система состоит из 1 обслуживающего устройства. На входе стоят n работ. Время выполнения каждой работы известно. Надо составить расписание, минимизирующее среднее время пребывания работы в системе, под которым будем понимать величину, состоящую из:

Время ожидания

Время обслуживания

3. Минимизация среднего времени пребывания работ в системе n|1.

Соотношение между длительностью прохождения и средним числом работ в системе.

5. Составление расписаний в случае критерия с учетом веса в системе n|1.

Составление расписаний в соответствии с плановым сроком. Теорема Джексона.

7. Расписания с упорядочением работ в виде цепочек, которые не могут разрываться в системах n|1.

Пусть есть n работ, которые объединены в k цепочек. Цепочки разрывать нельзя при составлении расписаний, то есть, если началась выполняться первая работа из цепочки, то должны выполняться остальные работы в цепочке. Надо составить расписание, минимизирующее время пребываний работ.

ti – время выполнения цепочки

Fi – время пребывания в системе цепочки

hj – расстояние между последней работой в цепочке и jой

Fij = Fi – hij

Нужно минимизировать:

Так как hij не зависит от расписания, то сумма по hij тоже не зависит. Чтобы (*) минимизировать надо минимизировать:

В расписании, минимизирующем среднее время пребывания в том случае, когда цепочки сгруппированы и их разрывать нельзя:

8. Составление расписаний в системах n|1 при заданном отношении предшествования (цепочки, которые можно разрывать).

9. Расписания для систем конвейерного типа. Теорема о порядке выполнения на двух первых машинах. Теорема о порядке выполнения на двух первых и двух последних машинах в системе n|m|F|F max .

Задача Джонсона. Теорема Джонсона. Алгоритм, основанный на теореме Джонсона.

Алгоритм:

1) Выбрать работу с мин длительностью прохождения на устройстве А

2) Выбрать работу с мин длительностью прохождения на устройстве В

3) Если А

4) Вынесенную в итоговое расписание работуиз списка доступных вычеркнуть

5) Повторять 1-4 до тех пор, пока все работы не выйдут из списка доступных(то есть будет готовое расписание)

11. Оптимальные расписания для системы n|m|F|F max .

Но если m>3, то составление расписания сложно. Схемы:

Полный перебор(из-за факториального роста вычислительной сложности не применяется)

Динамическое программирование(путём разбиения сложных задач на более простые подзадачи)

Метод ветвей и границ

Метод ветвей и границ – метод решения задач дискретной оптимизации, основанный на вычислении оценок и ветвлений. Это пошаговая процедура конструирования расписаний:

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

Иначе говоря, метод ветвей и границ за счет оценок существенно уменьшает полный перебор за счет того, что поиск «лучшего» расписания ведется в группе тех расписаний, которые не хуже остальных. То есть в результате такого перебора найдется расписание, которое не хуже любого другого. В самом плохом случае метод ветвей и границ может привести к полному перебору.

13. Параллельные приборы. Система заданий с древовидной структурой.

Есть система задач, причем:

В этой системе определено отношение предшествования(работа может выполняться только если выполнена предшествующая)

Время выполнения каждой работы одинаково и равно единичке

В определенный момент времени: одни работы готовы(предшественники выполнены) и не готовы(иначе).

Для решения целесообразно использовать уровневую стратегию:

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

Готовое расписание

Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время A i и B i обработки i -й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через X i - время простоя в ожидании i -й детали, то:
A 1
X 1 + X 2 = max(A 1 + A 2 - B 1 , A 1)
X 1 + X 2 + X 3 = max(A 1 + A 2 +A 3 - B 1 - B 2 , A 1 + A 2 - B 1 , A 1)
∑X i = max(∑A i - ∑B i)
Если обозначить через F(t, A k , B k /k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, A k , B k /k = 1..N) = min(A i + F(B i + max(t-A i ,0),A k ,B k =1..N,k≠i))
Если после i -й детали при оптимальном порядке обрабатывается j -я, то:
F(t, A k , B k /k=1..N) = A i + A j + F(t ij , A k , B k /k=1..N; k≠i,j)
где
t ij = B i + max = B i + B j - A i - A j + max
Если max(A i + A j - B i ,A i) < max(A j + A i - B j , A j), то сначала разумнее обрабатывать j -ю деталь.
Можно показать, что указанное условие необходимости перестановки эквивалентно условию:
min(A j , B i) < min(A i , B j)
Соответственно ищем среди всех значений A i и B i наименьшее. Если найденное значение совпадает с некоторым A i , то i -ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi , то последней. Эту процедуру повторяем для всех остальных деталей.

Пример 1. Пусть информация о времени обработки задана таблицей:

Шаг № 2.
Минимальное из значений равно 3 и соответствует B 2: 2-ая деталь обрабатывается последней.

Шаг № 4.
Минимальное из значений равно 5 и соответствует B 4: 4-ая деталь обрабатывается последней.

Шаг № 6.
Минимальное из значений равно 7 и соответствует B 6: 6-ая деталь обрабатывается последней.

В итоге упорядоченная информация принимает вид:

Время простоя второй машины при первичном порядке равно:
max(2 , 2 + 8 - 3 , 2 + 8 + 4 - 3 - 3 , 2 + 8 + 4 + 9 - 3 - 3 - 6 , 2 + 8 + 4 + 9 + 6 - 3 - 3 - 6 - 5 , 2 + 8 + 4 + 9 + 6 + 9 - 3 - 3 - 6 - 5 - 8) = max(2, 7, 8, 11, 12, 13) = 13
Время простоя при оптимальной перестановке равно:
max(2 , 2 + 4 - 3 , 2 + 4 + 6 - 3 - 6 , 2 + 4 + 6 + 9 - 3 - 6 - 8 , 2 + 4 + 6 + 9 + 9 - 3 - 6 - 8 - 7 , 2 + 4 + 6 + 9 + 9 + 8 - 3 - 6 - 8 - 7 - 5) = max(2, 3, 3, 4, 6, 9) = 9

Пример 2. Пусть информация о времени обработки задана таблицей:

Шаг № 2.
Минимальное из значений равно 3 и соответствует B 1: 1-ая деталь обрабатывается последней.

Шаг № 4.
Минимальное из значений равно 4 и соответствует B 6: 6-ая деталь обрабатывается последней.