Алгоритм поиска кратчайших путей на неориентированном графе.
(2 задачи, время выполнения - почти пара) Решить задачу поиска кратчайших путей. (Презентация ИССЛЕДОВАНЕ ОПЕРАЦИЙ)
Алгоритм.
Начало.
1) В стартовой вершине Sставим (0,-) –ВЕЧНАЯ МЕТКА (Она читается 0 «из ниоткуда»).
2)Из стартовой вершины мы рассылаем ВО все соседние ВЕРШИНЫ ВРЕМЕННЫЕ МЕТКИ «метастазы» - в них ставится сумма 0 (из позиции (0,-)) и расстояния до стартовой вершины S.
Все временные метки, чтобы их отличать от вечных пишутся в круглых скобках.
Повторяем до исчерпания вершин – пока все вершины не заимеют вечные метки
а)На каждом этапе из всех имеющихся в графе к настоящему моменту временных меток выбирается лучшая – меньшая. Она объявляется вечной. (При оформлении такую метку надо зачеркнуть и написать над ней точно такую же, но уже в круглых скобках).
б)Только новорождённая временная метка
Образец оформления
Образец ответа
Сетевое планирование. Ребро-работа.
(СПУ1) Рассчитать минимальное время выполнения проекта.
Сетевое планирование. Представление узел-работа.
(СПУ2): чтобы не производить сложных расчетов – заменим в предыдущем условии ВСЕ веса на их разности с 10, взятые по модулю(таким образом все веса положительны). Перейдём в представление УЗЕЛ-РАБОТА. (построить граф на весь лист, предварительно повернув его альбомно) Пользуясь 10ти компонентным представлением отразить сведения о работе (название, центр-длительность, времена начала-окончания в углах. Запасы в серединах сторон. По одной из этих задач построить график Ганта. Задача обязательна по дисциплине управление проектами.
Теория сетевого планирования.
Расчёт длиннейшего - критического пути (задача сетевого планирования) ведется в идеологии предшествующего примера, с небольшой разницей –
ПРВЫЙ ПРОХОД Метка Тр=0 ставится в левой стартовой вершине проекта. Рассчитываются любые вершины, которым предшествуют только уже рассчитанные вершины (и никакие более). В каждой вершине суммируется время предшествующей вершины и длина работы, от неё отделяющее. Среди всех таких сумм мы находим максимум, мотивировка которого в том, что, для того чтобы состоялось событие и могли стартовать работы исходящие из вершины должны закончится все входящие в неё работы. Четкую структуру слоёв в ГРАФЕ ПРОЕКТА на первый взгляд обычно выделить не удаётся (хотя можно выделить слои по этапам расчёта). Расчет ведется до тех пор, пока не будут рассчитаны все вершины.
Критический путь восстанавливается с концевой вершины по меткам (галочкам). Он сам и его длина (Тр концевой вершины) пишется в ответ.
ОБРАТНЫЙ ПРОХОД. На концевой вершине копируется значение стоящей в ней метки Тр=.. в Тп=.. Это позднее время наступления события. Рассчитываются поздние времена наступления событий. Всё также как в предыдущем первом проходе, но для расчёта должны быть рассчитаны поздние времена Тп в последующих вершинах. Расчет производится на минимум: вычитается длина работы до каждого ранее рассчитанного последующего события из позднего времени его наступления, худшая,т.е. минимальная из этих разностей и есть максимально возможное – т.е. самое позднее время наступления события, не приводящее к срыву максимально возможно ранних сроков сдачи проекта, рассчитанных в первом проходе. Критический путь не рассчитывается галочки не ставятся.
В третьей части для двенадцати работ не лежащих на криическом пути и не являющихся ни начальными ни концевыми считаются полный, собственный, ранний и поздний резервы времени.
Для студентов специализации СПУ строится график Ганта.
