Новое решение задачи коммивояжёра

Новое решение задачи коммивояжёра

Призываем на помощь рекурсию

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

О чём речь

Коротко напомним:

  1. Есть виртуальный коммивояжёр (торговый представитель). Есть города, в которые он должен приехать.
  2. Эти города как-то разбросаны по карте с какими-то расстояниями друг от друга.
  3. Коммивояжёру нужно найти стартовый город и из него построить маршрут через все остальные города.
  4. В каждом городе можно побыть один раз.
  5. Задача — найти самый короткий маршрут.

Решение в лоб — много вложенных циклов

Первое, что мы сделали, — вложенными циклами сгенерировали все возможные комбинации городов и проверили длину каждого пути.

Но такой вариант оказался сложным для конструирования вложенностей и для проверки условий. Если бы у нас было не 5, а 10 городов, то нужно делать 10 вложенных циклов и проверять 55 условий. Представьте, каково это — отлаживать и проверять программу с таким количеством циклов и вложенных проверок.

// таблица с расстояниями между городами
var towns = [
	[0, 5, 6, 14, 15],
	[5, 0, 7, 10, 6],
	[6, 7, 0, 8, 7],
	[14, 10, 8, 0, 9],
	[15, 6, 7, 9, 0]
];

// массив, где будут храниться все просчитанные маршруты
var path =[];

// порядковый номер текущего маршрута
var counter = 0;

// самый короткий путь — сразу ставим заведомо большим, чтобы уменьшать его по мере работы алгоритма
var minPath = 10000;

// номер самого короткого маршрута
var minCounter;

// перебираем все варианты перемещения по городам
for (var i1 = 0;  i1 <=4; i1++) {
	for (var i2 = 0;  i2 <=4; i2++) {
		for (var i3 = 0;  i3 <=4; i3++) {
			for (var i4 = 0;  i4 <=4; i4++) {
				for (var i5 = 0;  i5 <=4; i5++) {

					// нельзя посещать один и тот же город больше одного раза
					if (
						(i1 != i2) && (i1 != i3) && (i1 != i4) && (i1 != i5) &&
						(i2 != i3) && (i2 != i4) && (i2 != i5) &&
						(i3 != i4) && (i3 != i5) &&
						(i4 != i5)
						)
						{
							// запоминаем текущий путь
							path[counter] = (i1+1) + ' → ' + (i2 + 1) +' → ' + (i3 + 1) + ' → ' + (i4 + 1) + ' → ' + (i5 + 1);
							// выводим его в консоль
							console.log(path[counter]);
							// если общее расстояние этого пути меньше минимального
							if ( (towns[i1][i2] + towns[i2][i3] + towns[i3][i4] + towns[i4][i5]) < minPath) {
								// то мы запоминаем это минимальное расстояние
								minPath = towns[i1][i2] + towns[i2][i3] + towns[i3][i4] + towns[i4][i5];
								// выводим его в консоль
								console.log(minPath);
								// запоминаем номер этого маршрута с минимальным расстоянием
								minCounter = counter;
						}
						// когда всё сделали, увеличиваем номер маршрута
						counter +=1;
					}
				}
			}
		}
	}
};
// когда прошли все варианты, выводим найденное решение
console.log('Путь с самой короткой длиной маршрута: ' + path[minCounter] + '(' + minPath + ' км.)');

Решение проще — использовать рекурсию

Недавно мы рассказывали про перестановки и то, как их найти с помощью рекурсии. Логика такая:

  1. Делаем цикл, который по шагам равен длине массива с данными.
  2. Внутри него пишем рекурсивную функцию, которая сама раз за разом будет дробить массив и переставлять элементы местами.
  3. Получим полный список возможных маршрутов.
  4. Проверим каждый маршрут и узнаем самый короткий путь.

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

Для реализации такого алгоритма единственное, что нам понадобится из предыдущего кода, — это переменные:

// таблица с расстояниями между городами
var towns = [
  [0, 5, 6, 14, 15],
  [5, 0, 7, 10, 6],
  [6, 7, 0, 8, 7],
  [14, 10, 8, 0, 9],
  [15, 6, 7, 9, 0]
];
// порядковый номер текущего маршрута
var counter = 0;

// самый короткий путь — сразу ставим заведомо большим, чтобы уменьшать его по мере работы алгоритма
var minPath = 10000;

// номер самого короткого маршрута
var minCounter;

Теперь добавим сюда новые переменные, с которыми мы будем работать:

// массив для результатов перестановок
var results = [];
// номера городов
var cities = [1,2,3,4,5];
// самый короткий путь
var path;
// вспомогательные переменные
var p1, p2;

Логика будет такая: получаем все перестановки городов и результат отправляем в переменную results. Для этого копируем один в один функцию с рекурсией из статьи про перестановки:

// рекурсивная функция
// на вход получаем текущий массив и массив с памятью предыдущих вычислений
function permute(arr, memo) {
  // переменная для хранения фрагмента массива
  var cur;

  // делаем переменную для хранения промежуточных результатов
  // в программировании это называется «мемоизация»
  var memo = memo || [];

  // какой размер входного массива — такой длины и делаем цикл, чтобы перебрать все элементы
  for (var i = 0; i < arr.length; i++) {

    // получаем новый массив cur, удаляя из входного массива один элемент, начиная с текущей позиции
    // при этом из входного массива этот элемент тоже удалится
    cur = arr.splice(i, 1);

    // если от входного массива ничего не осталось
    if (arr.length === 0) {
      // то приклеиваем текущее значение нарезки к варианту, который лежит в памяти, 
      // и добавляем получившийся результат в итоговый массив
      results.push(memo.concat(cur));
    }

    // вызываем новый виток рекурсии
    // в качестве аргументов передаём копию входящего массива и добавляем к кешу памяти то, что получилось после удаления одного символа из входящего массива
    permute(arr.slice(), memo.concat(cur));

    // возвращаем в исходный массив первый элемент из нового массива, но уже на другую позицию
    arr.splice(i, 0, cur[0]);
  }

  // возвращаем обратно массив с результатами перестановок
  return results;
}

Сразу формируем перестановки:

// получаем все перестановки городов
// результаты будут храниться в массиве results
permute(cities);

А теперь просто перебираем все перестановки и для каждой находим длину маршрута:

// перебираем все варианты перестановок
for (var i =0; i < results.length; i++) {
  // обнуляем длину текущего маршрута
  path = 0;
  // проходим по каждому городу в текущем варианте пути
  for (var j = 1; j < cities.length; j++) {
    // достаём очередную пару городов
    // отнимаем единицу, потому что в массиве towns нумерация ячеек начинается с нуля, а не с единицы
    p1 = results[i][j-1] - 1;
    p2 = results[i][j] - 1;

    // прибавляем это к общей длине текущего маршрута
    path = path + towns[p1][p2];
  }

  // если мы нашли маршрут короче, чем был до этого
  if (path < minPath) {
    // запоминаем, какой это номер в перестановках
    minCounter = i;
    // обновляем минимальную длину маршрута
    minPath = path;
  }
}

// выводим самый короткий маршрут
console.log(results[minCounter]);

Преимущество этого алгоритма в том, что если у нас изменится количество городов, то нам достаточно будет поправить две переменные: список городов и таблицу расстояний. А всё остальное компьютер будет считать сам, не заставляя нас прописывать новые условия.

И помните, что если попробовать решить задачу коммивояжёра, в которой 63 города, то Вселенная сломается. Не рискуйте зря.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Олег Вешкурцев

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
8 интересных задач про цифры
5 интересных задач про цифры

Подборка для тех, кто любит подумать.

medium
Странные программисты говорят про время

Суперзамороченная задача, которая решается в два счёта.

easy
Задача про таблетки и злого гения

Как логика и ограничения помогают найти банку с отравленными таблетками.

medium
Задача про бейсбольную биту

Эта задача решается не так просто, как кажется.

easy
Сложная логическая задача на повышение
Сложная логическая задача на повышение

Как одним вопросом получить ОЧЕНЬ МНОГО информации.

easy
Задача: Сколько стоит капучино?
Сколько стоит капучино?

Находчивый инженер и кофейный автомат.

easy
Загадка 1 000 пробирок
Загадка о тысяче пробирок
hard
Задача про нестандартное взвешивание
Задача про нестандартное взвешивание

Флеш-карты на развес.

easy
Задачка: узнать среднюю зарплату в строгой компании
Задачка: узнать среднюю зарплату в строгой компании

Непростая задачка против звериного оскала капитализма.

easy
За что уволили менеджера?

Иногда невнимательность может стоить работы. Сможете разобраться в ситуации?

medium
hard