Задача о торговом представителе - решим?

Задача о торговом представителе: Решение и практическое применение

The article was posted: 10/30/2021| 4 min read

---

Вообще, в учебниках эта задача называется "задача о коммивояжере". Коммивояжер это не совсем торговый представитель, но для более приближенного к нашим реалиям понимания, скажем, что это торговый представитель на авто. Ему нужно посетить несколько городов и вернуться в исходную точку, но есть одна загвоздка: он хочет сделать это, пройдя минимальный путь.

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

В чем сложность задачи?

Для понимания проблемы представьте, что у нас есть 3 города. Коммивояжер может начать путешествие из любого из них, что дает 3 возможных стартовых города. Для каждого стартового города есть 2 варианта для следующего города, и наконец, остается один город для последнего этапа. Это значит, что общее количество маршрутов (перестановок) равно 3! = 3 × 2 × 1 = 6. ! это факториал, тот самый, который учили в школе. Можно открыть приложение калькулятор на телефоне, только переключить его в инженерный режим, где есть больше функций. Клавиша с ! и есть факториал.

Для 4 городов количество возможных маршрутов уже составляет 4! = 24, а для 10 городов — 10! = 3628800. При таком росте числа возможных маршрутов проверка каждого из них становится практически невозможной для больших значений n (число городов).

Решение на языке JavaScript

Чтобы решить эту задачу, мы можем использовать простой и наглядный метод — перебор всех возможных маршрутов. Хотя это не самый быстрый способ, он понятен и помогает лучше разобраться в сути задачи.

Допустим, у нас есть четыре города, расположенных в точках A, B, C и D. Коммивояжер стартует из точки A и хочет посетить все остальные города и вернуться обратно.

const cities = [
  { name: "A", x: 0, y: 0 },
  { name: "B", x: 2, y: 2 },
  { name: "C", x: 4, y: 0 },
  { name: "D", x: 6, y: 3 }
];

// Функция для вычисления расстояния между двумя городами
function distance(city1, city2) {
  return Math.sqrt((city1.x - city2.x) ** 2 + (city1.y - city2.y) ** 2);
}

// Функция для нахождения кратчайшего маршрута
function findShortestPath(cities) {
  let shortestDistance = Infinity;
  let bestRoute = [];

  function permute(route, remainingCities) {
    if (remainingCities.length === 0) {
      // Добавляем путь обратно к началу
      route.push(route[0]);
      let totalDistance = 0;
      for (let i = 0; i < route.length - 1; i++) {
        totalDistance += distance(route[i], route[i + 1]);
      }
      if (totalDistance < shortestDistance) {
        shortestDistance = totalDistance;
        bestRoute = [...route];
      }
      route.pop(); // Убираем возвращение в начало для дальнейших вычислений
    } else {
      for (let i = 0; i < remainingCities.length; i++) {
        permute([...route, remainingCities[i]], remainingCities.filter((_, index) => index !== i));
      }
    }
  }

  permute([], cities);
  return { bestRoute, shortestDistance };
}

// Поиск кратчайшего маршрута
const result = findShortestPath(cities);
console.log("Кратчайший маршрут:", result.bestRoute.map(city => city.name));
console.log("Минимальное расстояние:", result.shortestDistance);

Вы, наверное, можете сказать, что это слишком сложно и что не может быть так много вариантов, если мы имеем так мало городов. Приведу пример. У нас всего два города, Николаев и Одесса, и торговому представителю нужно вернуться обратно в тот город, откуда он выехал. Так вот расстояние туда и обратно практически никогда не будут равны. Например, в одну сторону дорога перекрыта дорожной службой, они ложат асфальт, торговому представителю приходится объезжать. Или он едет по автобану, а съезды с автобанов не очень часты. Можно проехать 30 км и больше до ближайшего съезда. Или мы едем по улице с односторонним движением, но, когда мы будем возвращаться обратно, мы уже не сможем вернуться по этой же улице, а должны выбрать другой маршрут.

Где мне это может понадобиться?

Естественно, в логистике, планировании перевозок, в планировании маршрутов мусоровозок. Интернет, по сути, это тоже точки с маршрутами между ними. Даже токарь станка ЧПУ на заводе "Заря", сам того не зная, сталкивается с этим алгоритмом, потому что резец также двигается между точками на изделии и оптимизация его передвижения позволяет сэкономить на времени работы и износе железа.