Построение минимального пути между указанными точками (задача коммивояжера)

       Задача коммивояжера заключается в поиске самого выгодного маршрута, проходящего по заданным узлам. Поиск оптимального тура выполняется полным перебором вариантов, поэтому обрабатываемое количество узлов ограничено 13.

После нажатия кнопки запуска задачи необходимо указать на карте узлы, которые необходимо посетить. Выбор узлов заканчивается «Ctrl + Левая кнопка мыши» или двойным нажатием левой кнопки мыши. При двойном нажатии ближайший к точке нажатия узел добавляется в список узлов.

После выбора точек вызывается диалог настройки параметров.

Диалог настройки параметров задачи коммивояжера аналогичен диалогу построения маршрута, только добавлен переключатель «Закончить маршрут», определяющий, где заканчивается тур – в первом или последнем введённом узле.

После нажатия кнопки «Построить» выполняется поиск оптимального тура. Поиск тура состоит из поиска маршрутов между всеми парами точек и затем поиска оптимального сочетания этих маршрутов. Название этапа и процент обработки показывается в группе «Состояние обработки». Прервать обработку можно, нажав кнопку «Прервать». После окончания обработки в диалоге открывается закладка «Статистика».

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

Под таблицей показывается общая длина тура и время его проезда.

Сохранение тура в объект выполняется при нажатии кнопки «Сохранить маршрут в объект». Не рекомендуется сохранять тур на карту графа, потому что при выполнении следующей поисковой задачи будет повторно пересоздаваться двоичный файл WMN образа графа.

После анализа тура можно его перестроить, изменив настройки на вкладке «Параметры» или закрыть диалог кнопкой «Выход».

При закрытии диалога найденный тур показывается красным пунктиром.