Алгоритм построения и использования таблицы оптимальных путей транспортной сети
Таблица оптимальных путей (ТОП) на транспортной сети – это табличное представление всех оптимальных путей от одной или нескольких заданных вершин до всех остальных вершин транспортной сети. Достоинством Топ является компактность записи оптимальных путей, которая, в отличии, например от матричной формы, позволяет описать все оптимальные пути, а не только путь между двумя заданными вершинами транспортной сети.
Для i-ой вершины по таблице находится предшествующая, для нее – своя предшествующая вершина и т.д., до тех пор, пока не будет определена начальная вершина маршрута, для которой не задана предшествующая вершина. Потенциал каждой вершины равен расстоянию от начальной вершины до данной вершины при движении по оптимальному маршруту.
Алгоритм построения ТОП состоит из следующих действий:
- заполнить первый и второй столбцы ТОП номерами вершин транспортной сети в порядке их возрастания. Во втором столбце одну или несколько начальных вершин пометить, например, знаком минус перед номерами вершины. Третий столбец заполнить исходными потенциалами вершин. Исходные потенциалы начальных вершин равны нулю, а всех остальных вершин – числу М или максимально большому числу;
- для всех дуг, исходящих из помеченной вершины, проверяется условие оптимальности дуги pppj−> i ij , т.е. разность потенциалов конечной и начальной вершин дуги должна быть больше оценки дуги между этими вершинами. Выполнение этого условия говорит о выгодности движения по данной дуге. Тогда в качестве предшествующей вершины для конечной вершины дуги (второй столбец ТОП) указывается номер вершины i (с пометкой). Потенциал конечной вершины определяется как сумма потенциала начальной вершины дуги и оценки этой дуги, т.е. pj= pp i + ij ;
- если условие оптимальности дуги не выполняется, то проверяется следующая дуга, исходящая из помеченной вершины;
- если условие оптимальности проверено для всех дуг, исходящих из помеченной вершины, то метка с этой вершины снимается, и рассматриваются дуги, исходящие из любой следующей помеченной вершины, то все действия, начиная со второго, повторяются. Построения оптимальных маршрутов повторяется до тех пор, пока в ТОП имеется хотя бы одна помеченная вершина.
В процессе построения ТОП возможна многократная корректировка потенциалов вершин и номеров предшествующих вершин, поэтому принято строить несколько таблиц с переносом в новую таблицу результатов предыдущих построений.
- Назначение и классификация складов
- Требования к транспортированию и хранению массовых грузов
- Автоматическая идентификация грузов
- Пломбирование и индикация грузов
- Силы, действующие на груз при транспортировке
- Причины недостачи грузов
- Естественная убыль грузов и ее нормирование
- Виды несохранности грузов при перевозке
- Транспортная маркировка грузов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу