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

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

О чём речь

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

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

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

Но такой вариант оказался сложным для конструирования вложенностей и для проверки условий. Если бы у нас было не 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 + ' км.)');

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

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

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

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

// таблица с расстояниями между городами
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 города, то Вселенная сломается. Не рискуйте зря.