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

В статье описаны проблемы маршрутизации. Показано, что почти все проблемы маршрутизации дуг могут быть преобразованы в другие проблемы маршрутизации. Это продемонстрировано на примере задачи китайского почтальона в смешанном мультиграфе. Также в статье приведен обзор различных задач китайского почтальона (в зависимости от типа графа, функции стоимости и обязательности прохождения элементов графа). Для каждой проблемы дана математическая постановка. Кроме того, описаны примеры потенциально полезных приложений, где задачи могут быть применены. Приведена таблица различных вариантов задачи китайского почтальона и выбраны параметры для идентификации различных типов задач. Выделено пять параметров: наличие дуг, наличие ребер, наличие обязательных дуг, наличие обязательных ребер, наличие ребер со стоимостью, зависящей от прохода. Показано, что, варьируя эти параметры, можно получить новые задачи, которые могут быть полезны в реальной жизни, однако еще не описаны. Выявлены четыре таких задачи. Показано, что задача китайского почтальона может быть решена путем преобразования в другие задачи маршрутизации. Приведен метод, позволяющий преобразовать задачу в обобщенную задачу коммивояжера. Показаны результаты применения простейших алгоритмов для решения преобразованного варианта задачи (результаты приведены для алгоритмов ближайшего соседа и их модификаций). Исследование еще не завершено, планируется продолжать тестировать алгоритмы решения смежных задач маршрутизации и алгоритмы для преобразований задач в эквивалентные.