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

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

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

К. С. Подшивалова, Э. Р. Домке, С. Ф. Подшивалов, С. А. Жесткова ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ КОМБИНАЦИИ МАРШРУТОВ С СОВМЕСТНЫМ ЦЕНТРОМ ИСПОЛЬЗОВАНИЕ ФИКТИВНЫХ УЗЛОВ Аннотация. <...> Предложено совершенствование метода ветвей и границ, позволяющее посещать вершины графа несколько раз. <...> Представлено решение задачи маршрутизации для комбинации маршрутов с симметричной матрицей весов, выходящих из одного центра. <...> Введение Задача поиска оптимальных маршрутов на взвешенном графе имеет самый общий характер. <...> На практике выбор оптимального маршрута при решении задачи коммивояжера подразумевает однократное появление каждого события. <...> Наиболее сложные и интересные задачи стоят перед исследователями в областях, где события могут накладываться друг на друга, повторяться и связаны с поиском оптимальной комбинации одновременно нескольких маршрутов на графе. <...> Постановка задачи В классической задаче коммивояжера необходимо посетить все вершины графа один раз так, чтобы вес маршрута был наименьший. <...> Когда маршрут начинается и заканчивается в одном и том же пункте, решение сводится к поиску замкнутого гамильтонового контура. <...> В незамкнутой задаче коммивояжера, когда не требуется возвращаться к исходной вершине, находится гамильтонов путь. <...> Определение гамильтонового контура относится к трудно разрешимой задаче дискретной математики, которая для полного графа может и не иметь решения. <...> Поволжский регион Следует отметить, что гамильтонов контур не всегда является кратчайшим маршрутом. <...> Граф оптимального маршрута Требуется найти оптимальный маршрут из пункта 1 через все узлы графа и вернуться в исходную вершину 1. <...> В данной статье предлагается метод расчета, позволяющий находить оптимальную комбинацию для нескольких маршрутов, выходящих из одного общего центра, при симметричной матрице весов. <...> Для разделения графа на маршруты вводим дополнительно фиктивные узлы в исходную матрицу весов. <...> Фиктивным будем называть <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт