Made on
Tilda
Задача коммивояжера (Traveling Salesman Problem, TSP) — одна из самых известных задач комбинаторной оптимизации. Её суть заключается в поиске оптимального маршрута, проходящего через заданные точки (города) по одному разу с обязательным возвратом в исходную точку.
Задача относится к классу NP-трудных задач, что означает её высокую вычислительную сложность. При увеличении количества городов время решения растёт факториально.
Задача коммивояжера находит широкое применение в:
Важно отметить, что точные методы эффективны для небольшого количества городов (до 66), в то время как приближённые методы позволяют находить достаточно хорошие решения для задач любого размера с допустимой погрешностью.
Преимущества приближённых методов:
Недостатки приближённых методов:
При выборе метода решения задачи коммивояжера следует учитывать:
Реальные кейсы использования задачи коммивояжера:
Ответьте на следующие вопросы:
Пример: (показаны 2 из 4 необходимых матриц)
Рассмотрим 5 точек в городах России:
| Москва | СПб | Казань | Н.Новгород | Владимир | |
|---|---|---|---|---|---|
| Москва | 0 | 700 | 850 | 430 | 180 |
| СПб | 700 | 0 | 1230 | 430 | 880 |
| Казань | 850 | 1230 | 0 | 390 | 690 |
| Н.Новгород | 430 | 430 | 390 | 0 | 230 |
| Владимир | 180 | 880 | 690 | 230 | 0 |
| Москва | СПб | Казань | Н.Новгород | Владимир | |
|---|---|---|---|---|---|
| Москва | 0 | 8 | 10 | 5 | 2 |
| СПб | 8 | 0 | 13 | 5 | 10 |
| Казань | 10 | 13 | 0 | 4 | 8 |
| Н.Новгород | 5 | 5 | 4 | 0 | 3 |
| Владимир | 2 | 10 | 8 | 3 | 0 |
Суть метода: перебор всех возможных вариантов маршрутов и выбор оптимального по заданному критерию (обычно — минимальная стоимость или расстояние).
Определение количества вариантов:
Для 5 городов количество возможных маршрутов = (5-1)! = 4! = 24 варианта
Это связано с тем, что маршрут циклический (начало и конец в одной точке)
Соответствие букв городам:
Все возможные комбинации маршрутов (24 варианта):
Для расчета расстояния по маршруту:
Маршрут: А → Б → В → Г → Д → А
Расстояния: А-Б (700) + Б-В (1230) + В-Г (390) + Г-Д (230) + Д-А (180) = 2730 км
Алгоритм действий:
Основные шаги:
Основные этапы:
Решить задачу выбора лучшего маршрута для каждой матрицы (4 решения) на основе собственных наборов данных.
Срок сдачи: 11 ноября 2025 г.
Системный анализ предполагает комплексный подход к определению весовых коэффициентов на основе нескольких критериев:
| Критерий | Низкий приоритет | Средний приоритет | Высокий приоритет |
|---|---|---|---|
| Расстояние | 0.2-0.3 | 0.4-0.5 | 0.6-0.7 |
| Время | 0.2-0.3 | 0.4-0.5 | 0.6-0.7 |
| Стоимость | 0.2-0.3 | 0.4-0.5 | 0.6-0.7 |
Предположим, что время в пути важнее расстояния. Введем коэффициенты:
Решить задачу оптимизации маршрута с использованием весовых коэффициентов (обосновнанных для маршрута) на основе собственных наборов данных.
Срок сдачи: 18 ноября 2025 г.
Допустим, для 3 маршрутов имеем следующие показатели:
| Маршрут | Расстояние (км) | Время (ч) | Стоимость (руб) |
|---|---|---|---|
| А → Б → В → А | 500 | 8 | 3000 |
| А → В → Б → А | 450 | 7 | 3200 |
| Б → А → В → Б | 600 | 10 | 2800 |
Приведём все показатели к единому масштабу (от 0 до 1) по формуле:
Для минимизируемых критериев (расстояние, время, стоимость) используем обратную формулу:
| Маршрут | Норм. расстояние | Норм. время | Норм. стоимость |
|---|---|---|---|
| А → Б → В → А | \(1 - \dfrac{500-450}{150} = 0.67\) | \(1 - \dfrac{8-7}{3} = 0.67\) | \(1 - \dfrac{3000-2800}{400} = 0.50\) |
| А → В → Б → А | \(1 - \dfrac{450-450}{150} = 1.00\) | \(1 - \dfrac{7-7}{3} = 1.00\) | \(1 - \dfrac{3200-2800}{400} = 0.00\) |
| Б → А → В → Б | \(1 - \dfrac{600-450}{150} = 0.00\) | \(1 - \dfrac{10-7}{3} = 0.00\) | \(1 - \dfrac{2800-2800}{400} = 1.00\) |
Определим приоритеты критериев:
Сумма коэффициентов: \(0.4 + 0.35 + 0.25 = 1.0\)
Формула: \(C_i = K_1 \cdot x_{1i} + K_2 \cdot x_{2i} + K_3 \cdot x_{3i}\)
| Маршрут | Расчёт | Комплексный показатель (\(C_i\)) |
|---|---|---|
| А → Б → В → А | \(0.4 \cdot 0.67 + 0.35 \cdot 0.67 + 0.25 \cdot 0.50\) | \(0.268 + 0.235 + 0.125 = 0.628\) |
| А → В → Б → А | \(0.4 \cdot 1.00 + 0.35 \cdot 1.00 + 0.25 \cdot 0.00\) | \(0.400 + 0.350 + 0.000 = 0.750\) |
| Б → А → В → Б | \(0.4 \cdot 0.00 + 0.35 \cdot 0.00 + 0.25 \cdot 1.00\) | \(0.000 + 0.000 + 0.250 = 0.250\) |
Сравним полученные комплексные показатели:
Оптимальный маршрут: «А → В → Б → А» (максимальный показатель \(= 0.750\))
Примечание: Чем выше значение \(C_i\), тем предпочтительнее маршрут (так как нормализация выполнена для минимизируемых критериев).
Решить задачу оптимизации маршрута с использованием нормализованных данных и весовых коэффициентов на основе собственных наборов данных.
Срок сдачи: 25 ноября 2025 г.