Задача коммивояжера (симметричная)

Задача коммивояжёра (Traveling Salesman Problem) — одна из самых известных и изученных задач комбинаторной оптимизации. Суть задачи: имеется набор городов и известны расстояния между каждой парой городов. Необходимо найти кратчайший замкнутый маршрут, который посещает каждый город ровно один раз и возвращается в начальную точку.

Несмотря на простую формулировку, задача коммивояжёра является NP-трудной, что означает отсутствие известного алгоритма, который мог бы гарантированно найти точное решение за полиномиальное время для больших экземпляров задачи. Количество возможных маршрутов растёт факториально: для n городов существует (n-1)!/2 различных маршрутов в симметричном случае.

Задача имеет широкое практическое применение: планирование маршрутов доставки, оптимизация движения сверла при печатных платах, последовательность выполнения задач на производстве, составление туристических маршрутов, оптимизация работы беспилотных транспортных средств, планирование объезда клиентов службами сервиса.

Теоретические основы

Симметричный граф — граф, в котором расстояние от города A до города B равно расстоянию от B до A. Это соответствует реальной ситуации с географическими расстояниями по прямой (евклидово расстояние) или по дорогам без односторонних улиц.

Асимметричный граф — граф, в котором стоимость маршрута от A до B может отличаться от расстояния от B до A. Примеры: городская транспортная сеть с односторонним движением, авиаперелёты с учётом ветра, доставка с учётом пробок в разных направлениях.

В данном примере рассматривается симметричный случай, так как расстояния вычисляются по формуле евклидова расстояния на плоскости, которое по определению симметрично.

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

Постановка задачи

Дан набор из 100 точек на плоскости со случайными координатами в диапазоне [0, 1000] × [0, 1000]. Необходимо найти кратчайший замкнутый маршрут, проходящий через все точки ровно один раз.

• Каждая вершина должна быть посещена ровно один раз;
• Маршрут должен быть замкнутым (возврат в начальную точку);
• Требуется минимизировать общую длину маршрута.

Решение задачи

1. Выбор модели

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

2. Создание модели

Инициализируется объект модели ограничений.

// Создаем модель ограничений
Модель = О2.Модели()
    .МодельОграничений()
    .СоздатьМодель();

3. Ввод данных

Создаются 100 точек со случайными координатами на плоскости.

// Вводим данные
КоличествоВершин = 100;
Множитель        = 1000;

// Генерируем случайные координаты точек
Точки = Новый Массив();
ГСЧ   = Новый ГенераторСлучайныхЧисел();

Для К = 0 По КоличествоВершин - 1 Цикл
    X = ГСЧ.СлучайноеЧисло(0, 1000);
    Y = ГСЧ.СлучайноеЧисло(0, 1000);
    Точки.Добавить(Новый Структура("X, Y", X, Y));
КонецЦикла;

Вычисление матрицы расстояний.

Это ключевой этап подготовки данных. Для каждой пары точек вычисляется евклидово расстояние по формуле:

d = √((x₂ - x₁)² + (y₂ - y₁)²)

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

// Вычисляем матрицу расстояний между точками
Расстояния = Новый Массив(КоличествоВершин);
Для К = 0 По КоличествоВершин - 1 Цикл
    Расстояния[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К = К1 Тогда
            Расстояния[К][К1] = 0;
        Иначе
            РазностьX         = Точки[К1].X - Точки[К].X;
            РазностьY         = Точки[К1].Y - Точки[К].Y;
            Расстояние        = Sqrt(РазностьX * РазностьX + РазностьY * РазностьY);
            Расстояния[К][К1] = Цел(Расстояние * Множитель);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

Из кода видно, что расстояние вычисляется одинаково для любой пары точек независимо от направления обхода. Евклидово расстояние от точки i до точки j равно расстоянию от j до i, так как формула использует квадрат разностей координат, который не зависит от знака. Математически: d(i,j) = d(j,i) для любых i и j. Это делает граф симметричным.

4. Регистрация переменных

Для каждой возможной дуги графа (перехода из одного города в другой) создаётся булева переменная. Переменная равна 1, если дуга включена в маршрут, и 0 в противном случае. Также создаются специальные объекты «дуга графа», которые связывают переменные с вершинами.

// Регистрируем булевы переменные для дуг графа
Дуги      = Новый Массив(КоличествоВершин);
ДугиГрафа = Новый Массив();

Для К = 0 По КоличествоВершин - 1 Цикл
    Дуги[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            Дуги[К][К1] = Модель.БулеваПеременная();
            Дуга        = Модель.Ограничения().ДугаГрафа(К, К1, Дуги[К][К1]);
            ДугиГрафа.Добавить(Дуга);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

5. Описание ограничений

Ограничение на гамильтонов цикл.

Используется специализированное ограничение ЦиклГрафа, которое гарантирует формирование единственного замкнутого цикла, проходящего через все вершины ровно один раз. Это ограничение автоматически обеспечивает:

• Из каждой вершины выходит ровно одна дуга;
• В каждую вершину входит ровно одна дуга;
• Отсутствие подциклов (изолированных малых циклов);
• Связность маршрута.

// Ограничение: единственный гамильтонов цикл
Модель.Ограничения().ЦиклГрафа(ДугиГрафа);

Это мощное ограничение избавляет от необходимости явно формулировать десятки вспомогательных ограничений, которые потребовались бы в других подходах.

6. Описание целевой функции

Целевая функция — минимизация общей длины маршрута. Каждая булева переменная дуги умножается на расстояние, соответствующее этой дуге.

// Целевая функция: минимизируем общую длину маршрута
ОбщаяДлина = Модель.Выражения().СоздатьПостроительВыражений();
Для К = 0 По КоличествоВершин - 1 Цикл
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            ОбщаяДлина.ДобавитьТерм(Дуги[К][К1], Расстояния[К][К1]);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщаяДлина.ПолучитьВыражение());

7. Решение модели

Для получения решения достаточно вызвать метод Решить объекта модели.

Модель ограничений в данном примере ищет точный оптимум: решатель формирует единственный гамильтонов цикл минимальной длины и, при отсутствии лимитов, стремится доказать его оптимальность. Для крупных экземпляров (например, 100 вершин) это может занимать заметное время.

// Решение модели
Решение = Модель.Решить();

8. Вывод результатов

Результат восстанавливается из булевых переменных дуг. Строится массив потомков (для каждой вершины определяется следующая), затем последовательно обходится цикл, начиная с вершины 0. Длина маршрута делится на множитель для получения реального расстояния.

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
    
    // Восстанавливаем структуру маршрута
    Потомки = Новый Массив(КоличествоВершин);
    Для К = 0 По КоличествоВершин - 1 Цикл
        Потомки[К] = -1;
        Для К1 = 0 По КоличествоВершин - 1 Цикл
            Если К <> К1 И Решение.ЗначениеПеременной(Дуги[К][К1]) = 1 Тогда
                Потомки[К] = К1;
                Прервать;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    // Строим маршрут, следуя по цепочке потомков
    Маршрут        = Новый Массив();
    ТекущаяВершина = 0;
    Для Счетчик = 0 По КоличествоВершин - 1 Цикл
        Маршрут.Добавить(ТекущаяВершина);
        ТекущаяВершина = Потомки[ТекущаяВершина];
        Если ТекущаяВершина = -1 Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;
    
    // Вычисляем общую длину маршрута
    ДлинаМаршрута = 0;
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Начало        = Маршрут[К];
        Конец         = Маршрут[(К + 1) % Маршрут.Количество()];
        ДлинаМаршрута = ДлинаМаршрута + Расстояния[Начало][Конец];
    КонецЦикла;
    ДлинаМаршрута = ДлинаМаршрута / Множитель;
    
    // Формируем строковое представление пути
    Путь = "";
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Путь = Путь + Маршрут[К];
        Если К < Маршрут.Количество() - 1 Тогда
            Путь = Путь + " → ";
        КонецЕсли;
    КонецЦикла;
    Путь = Путь + " → " + Маршрут[0];
    
    Сообщение = СтрШаблон("Задача коммивояжера (%1 вершин)%2", КоличествоВершин, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Общая длина маршрута: %1%2", Формат(ДлинаМаршрута, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Маршрут: %1%2", Путь, Символы.ПС);
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

Полный код решения задачи

Ниже представлен полный код решения. Вы также можете скачать пример в виде готовой обработки.

// Создаем модель ограничений
Модель = О2.Модели()
    .МодельОграничений()
    .СоздатьМодель();

// Вводим данные
КоличествоВершин = 100;
Множитель        = 1000;

// Генерируем случайные координаты точек
Точки = Новый Массив();
ГСЧ   = Новый ГенераторСлучайныхЧисел();

Для К = 0 По КоличествоВершин - 1 Цикл
    X = ГСЧ.СлучайноеЧисло(0, 1000);
    Y = ГСЧ.СлучайноеЧисло(0, 1000);
    Точки.Добавить(Новый Структура("X, Y", X, Y));
КонецЦикла;

// Вычисляем матрицу расстояний между точками
Расстояния = Новый Массив(КоличествоВершин);
Для К = 0 По КоличествоВершин - 1 Цикл
    Расстояния[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К = К1 Тогда
            Расстояния[К][К1] = 0;
        Иначе
            РазностьX         = Точки[К1].X - Точки[К].X;
            РазностьY         = Точки[К1].Y - Точки[К].Y;
            Расстояние        = Sqrt(РазностьX * РазностьX + РазностьY * РазностьY);
            Расстояния[К][К1] = Цел(Расстояние * Множитель);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

// Регистрируем булевы переменные для дуг графа
Дуги      = Новый Массив(КоличествоВершин);
ДугиГрафа = Новый Массив();

Для К = 0 По КоличествоВершин - 1 Цикл
    Дуги[К] = Новый Массив(КоличествоВершин);
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            Дуги[К][К1] = Модель.БулеваПеременная();
            Дуга        = Модель.Ограничения().ДугаГрафа(К, К1, Дуги[К][К1]);
            ДугиГрафа.Добавить(Дуга);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;

// Ограничение: единственный гамильтонов цикл
Модель.Ограничения().ЦиклГрафа(ДугиГрафа);

// Целевая функция: минимизируем общую длину маршрута
ОбщаяДлина = Модель.Выражения().СоздатьПостроительВыражений();
Для К = 0 По КоличествоВершин - 1 Цикл
    Для К1 = 0 По КоличествоВершин - 1 Цикл
        Если К <> К1 Тогда
            ОбщаяДлина.ДобавитьТерм(Дуги[К][К1], Расстояния[К][К1]);
        КонецЕсли;
    КонецЦикла;
КонецЦикла;
Модель.Минимизировать(ОбщаяДлина.ПолучитьВыражение());

// Решение модели
Решение = Модель.Решить();

// Вывод результатов
Если Решение.РешениеНайдено() Тогда
    ФорматВывода = "ЧДЦ=2; ЧН=0; ЧГ=0";
    
    Потомки = Новый Массив(КоличествоВершин);
    Для К = 0 По КоличествоВершин - 1 Цикл
        Потомки[К] = -1;
        Для К1 = 0 По КоличествоВершин - 1 Цикл
            Если К <> К1 И Решение.ЗначениеПеременной(Дуги[К][К1]) = 1 Тогда
                Потомки[К] = К1;
                Прервать;
            КонецЕсли;
        КонецЦикла;
    КонецЦикла;
    
    Маршрут        = Новый Массив();
    ТекущаяВершина = 0;
    Для Счетчик = 0 По КоличествоВершин - 1 Цикл
        Маршрут.Добавить(ТекущаяВершина);
        ТекущаяВершина = Потомки[ТекущаяВершина];
        Если ТекущаяВершина = -1 Тогда
            Прервать;
        КонецЕсли;
    КонецЦикла;
    
    ДлинаМаршрута = 0;
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Начало        = Маршрут[К];
        Конец         = Маршрут[(К + 1) % Маршрут.Количество()];
        ДлинаМаршрута = ДлинаМаршрута + Расстояния[Начало][Конец];
    КонецЦикла;
    ДлинаМаршрута = ДлинаМаршрута / Множитель;
    
    Путь = "";
    Для К = 0 По Маршрут.Количество() - 1 Цикл
        Путь = Путь + Маршрут[К];
        Если К < Маршрут.Количество() - 1 Тогда
            Путь = Путь + " → ";
        КонецЕсли;
    КонецЦикла;
    Путь = Путь + " → " + Маршрут[0];
    
    Сообщение = СтрШаблон("Задача коммивояжера (%1 вершин)%2", КоличествоВершин, Символы.ПС);
    Сообщение = Сообщение + Символы.ПС;
    Сообщение = Сообщение + СтрШаблон("Общая длина маршрута: %1%2", Формат(ДлинаМаршрута, ФорматВывода), Символы.ПС);
    Сообщение = Сообщение + СтрШаблон("Маршрут: %1%2", Путь, Символы.ПС);
    
    Сообщить(Сообщение);
Иначе
    Сообщить("Решение не найдено! Статус: " + Решение.Статус());
КонецЕсли;

  Скачать пример