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

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

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

О чём речь

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

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 + ' км.)');

JavaScript

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

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

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;

JavaScript

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

// массив для результатов перестановок 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; }

JavaScript

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

// получаем все перестановки городов // результаты будут храниться в массиве 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]);

JavaScript

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

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

Источник: thecode.media

Комментарии: