![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
И использования таблицы оптимальных путей транспортной сетиТаблица оптимальных путей (ТОП) на транспортной сети - это табличное представление всех оптимальных путей от одной или нескольких заданных вершин до всех остальных вершин транспортной сети. Достоинством ТОП является компактность записи оптимальных путей, которая, в отличие от матричной формы, позволяет описать все оптимальные пути, а не только путь между двумя заданными вершинами транспортной сети. Таблица оптимальных путей состоит из трех столбцов. Первый столбец содержит номера вершин транспортной сети i, второй столбец - номера предшествующих вершин Алгоритмпостроения ТОП состоит из следующих действий: 1) заполнить первый и второй столбцы ТОП номерами вершин транспортной сети в порядке их возрастания. Во втором столбце одну или несколько начальных вершин пометить, например, знаком минус перед номерами вершины. Третий столбец заполнить исходными потенциалами вершин. Исходные потенциалы начальных вершин равны нулю, а всех остальных вершин - числу М или максимально большому числу; 2) для всех дуг, исходящих из помеченной вершины, проверяется условие оптимальности дуги p. — pt > piJt то есть разность потенциалов конечной и начальной вершин дуги должна быть больше оценки дуги между этими вершинами. Выполнение этого условия говорит о выгодности движения по данной дуге. Тогда в качестве предшествующей вершины для конечной вершины дуги (второй столбец ТОП) указывается номер вершины i (с пометкой). Потенциал конечной вершины определяется как сумма потенциала начальной вершины дуги и оценки этой дуги, то есть pj — р. + ptj; 3) если условие оптимальности дуги не выполняется, то проверяется следующая дуга, исходящая из помеченной вершины; 4) если условие оптимальности проверено для всех дуг, исходящих из помеченной вершины, то метка с этой вершины снимается, и рассматриваются дуги, исходящие из любой следующей помеченной вершины. Затем все действия, начиная со второго, повторяются. Построения оптимальных маршрутов повторяются до тех пор, пока в ТОП имеется хотя бы одна помеченная вершина. В процессе построения ТОП возможна многократная корректировка потенциалов вершин и номеров предшествующих вершин, поэтому принято строить несколько таблиц с переносом в новую таблицу результатов предыдущих построений.
|