Компьютер сайенс тайм. Сейчас попробуем решить одну из непростых вещей в мире алгоритмов. Эту задачку проходят в технических вузах, чтобы показать мощь алгоритмического мышления, рекурсии и быстрых компьютеров по сравнению с медленными людьми.
О чём речь
Коротко напомним:
- Есть виртуальный коммивояжёр (торговый представитель). Есть города, в которые он должен приехать.
- Эти города как-то разбросаны по карте с какими-то расстояниями друг от друга.
- Коммивояжёру нужно найти стартовый город и из него построить маршрут через все остальные города.
- В каждом городе можно побыть один раз.
- Задача — найти самый короткий маршрут.
Решение в лоб — много вложенных циклов
Первое, что мы сделали, — вложенными циклами сгенерировали все возможные комбинации городов и проверили длину каждого пути.
Но такой вариант оказался сложным для конструирования вложенностей и для проверки условий. Если бы у нас было не 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 города, то Вселенная сломается. Не рискуйте зря.
