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

Печать Предыдущая страница Стартовая страница Следующая страница

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

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

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

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

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

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

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

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

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

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

 

ic_8488 Задача коммивояжера в режиме загрузки точек из файла

Решение задачи коммивояжера в режиме загрузки точек из файла отличается только способом указания узлов, которые надо посетить в туре. В этом режиме они загружаются из выбранного текстового файла.

В тестовом файле построчно должны быть записаны названия узлов так, как они определены в семантике «Собственное название» объекта узла карты графа. Поэтому для поиска узлов в этом режиме при построении карты графа семантика «Собственное название» должна быть помечена как семантика, копируемая в узлы.