Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
| Выбор кратчайшего пути
Кроме транспортной задачи, являющейся классической сетевой задачей, можно укажем ещё некоторые задачи на сетях: задача назначений, выбор кратчайшего пути, задача коммивояжера. Математическая постановка задачи назначений выглядит следующим образом: , где cij – сложность выполнения i-ой работы j-ым исполнителем. Основные особенности данной задачи: число уравнений 2n-1, число переменных n2.Так как работы делить нельзя, то из 2n-1 заполненной клетки n клеток содержат «1», а в остальных n-1 клетках содержатся «0», считаясь при этом заполненными. В остальном решение как в случае транспортной задачи. Рассмотрим более подробно решение задачи выбора кратчайшего пути в сетевой модели. На рис. изображен пример сетевой модели. Величины cijможет выражать длину пути из пункта i в пункт j, стоимость переезда из пункта i в пункт j, время переезда из пункта i в пункт j. При этом, если узлы i и j не связаны друг с другом, то cij=. Таким образом, задача о выборе кратчайшего расстояния является частным случаем задачи о назначениях: Алгоритм Форда. Выделяется некоторая вершина, и указываются длины всех дуг. Требуется для любой вершины найти кратчайший путь, ведущий от выделенной вершины к данной или убедиться в том, что не существует путей, ведущих из исходной вершины в данную вершину. Суть метода Форда заключается в присваивании каждой вершине двойной метки (, x), где - некоторое число, а x – другая вершина, связанная с данной. В дальнейшем эти метки изменяются. Начальный шаг. Выделенной вершине x0 присваивается метка (0;x) и остается неизменной. Каждой из остальных вершин графа присваивается метка (+;x), которая может меняться. Общий шаг. Поочередно рассматриваются вершины с конечными значениями меток . Вначале имеется лишь одна такая вершина x0. Выберем вершину xj, имеющую конечную метку j. Рассмотрим все дуги xjxm, выходящие из вершины xj и имеющие длину ljm. Сравниваем имеющиеся уже метки с числом j+ljm, где j+ljm – сумма метки вершины xj и длины дуги, ведущей из xj в xm. Если mj+ljm, то метка xm сохраняется. Если m>j+ljm, то вершине xm присваивается новая метка (j+ljm;xm). Этот шаг прекращается, пока для любой дуги xjxm разность меток вершин не будет превосходить длину дуги m-jljm. Вычисление длины кратчайшего пути. Длина кратчайшего пути из выделенной вершиныx0 в вершину xj равна окончательной метке вершины xj. Если j=+, то не существует пути из вершины x0 в xj. Построение кратчайшего пути. Данное построение осуществляется из xj путем прохождения через вершины, из которых получена окончательная метка. В обратном направлении полученные вершины и образуют искомый кратчайший путь. Задача. Построить сеть, заданную следующей таблицей, и найти кратчайшие пути из вершины x0 в каждую вершину сети.
жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
|