Решаем задачу коммивояжёра простым перебором
Что такое «задача коммивояжёра»
Решаем задачу коммивояжёра простым перебором

Вче­ра мы рас­ска­зы­ва­ли, что такое зада­ча ком­ми­во­я­жё­ра. Если корот­ко — это класс задач на поиск крат­чай­ше­го марш­ру­та сре­ди несколь­ких горо­дов. Или марш­ру­та по горо­ду. Или поиск опти­маль­ной квар­ти­ры для арен­ды по несколь­ким пара­мет­рам. В общем — это зада­чи о том, как при­ни­мать реше­ния в ситу­а­ци­ях со мно­же­ством переменных. 

Сего­дня мы попро­бу­ем решить клас­си­че­скую зада­чу ком­ми­во­я­жё­ра самым про­стым спо­со­бом — про­стым пол­ным перебором.

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

Города и расстояния

Допу­стим, у нас есть 5 горо­дов, каж­дый из кото­рых соеди­нён с другим:

Решаем задачу коммивояжёра простым перебором

Из-за релье­фа мест­но­сти близ­кие горо­да не все­гда соеди­не­ны по пря­мой, но для про­сто­ты мы нари­со­ва­ли так. Теперь про­ста­вим вре­мя, кото­рое тре­бу­ет­ся для пере­ез­да из горо­да в город:

Решаем задачу коммивояжёра простым перебором

Что­бы было удоб­но поль­зо­вать­ся рас­сто­я­ни­я­ми, сде­ла­ем табличку:

Решаем задачу коммивояжёра простым перебором

Нуле­вые ячей­ки озна­ча­ют, что здесь нет марш­ру­та, пото­му что это путь из одно­го и того же горо­да и обрат­но. Осталь­ные чис­ла — это рас­сто­я­ния меж­ду горо­да­ми. Напри­мер, рас­сто­я­ние меж­ду пер­вым и тре­тьим горо­дом — 6 кило­мет­ров, а меж­ду чет­вёр­тым и вто­рым — 10 километров.

На язы­ке JavaScript это будет выгля­деть так:

// таблица с расстояниями между городами
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]
];

Логика работы

Наша зада­ча — най­ти такой марш­рут, в кото­ром сум­ма кило­мет­ров будет минимальной. 

Скрипт пол­но­го пере­бо­ра будет рабо­тать так:

  1. С помо­щью 5 вло­жен­ных цик­лов мы смо­жем пере­брать все вари­ан­ты маршрутов. 
  2. В каж­дом цик­ле про­хо­дим от 0 до 4, пото­му что у нас 5 горо­дов. Если бы у нас было 10 горо­дов, нам нуж­но было бы сде­лать 10 вло­жен­ных цик­лов и в каж­дом цик­ле про­хо­дить от 0 до 9, что­бы пере­брать все воз­мож­ные рас­сто­я­ния для это­го города.
  3. На каж­дом шаге про­ве­ря­ем, что­бы у нас не повто­ря­лись горо­да в марш­ру­те, пото­му что в каж­дом мож­но побы­вать толь­ко один раз.
  4. Если это усло­вие выпол­ня­ет­ся, то запо­ми­на­ем оче­ред­ной марш­рут и счи­та­ем его длину. 
  5. Если дли­на полу­чи­лась мень­ше, чем наи­мень­шая до это­го — зна­чит, сей­час у нас полу­чил­ся самый корот­кий марш­рут. Воз­мож­но, на сле­ду­ю­щих шагах цик­ла мы най­дём марш­рут ещё коро­че, но пока мини­маль­ный — этот. Дела­ем эту дли­ну наи­мень­шей и запо­ми­на­ем номер маршрута.
  6. Так про­го­ня­ем все ком­би­на­ции городов.
  7. Выво­дим най­ден­ный мини­маль­ный марш­рут и его длину.

Скрипт

Для рабо­ты скрип­та нам пона­до­бят­ся такие переменные:

  • Мас­сив, где мы будем хра­нить все про­счи­тан­ные маршруты.
  • Поряд­ко­вый номер теку­ще­го марш­ру­та. Как толь­ко обра­ба­ты­ва­ем оче­ред­ной марш­рут, будем уве­ли­чи­вать номер на еди­ни­цу, что­бы сохра­нить новый марш­рут под новым номером.
  • Пере­мен­ная, где хра­нит­ся самый корот­кий путь. Что­бы уже на пер­вом шаге у нас было с чем срав­ни­вать дли­ну марш­ру­та, поме­стим в неё заве­до­мо боль­шое чис­ло, напри­мер, 10 000 кило­мет­ров. Как толь­ко мы най­дём путь коро­че (а мы най­дём), заме­ним его новым мини­маль­ным расстоянием.
  • Номер само­го корот­ко­го марш­ру­та. С его помо­щью мы выта­щим из мас­си­ва со все­ми марш­ру­та­ми самый корот­кий из них.

Собе­рём скрипт. Читай­те комментарии:

// таблица с расстояниями между городами
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. Если у нас будет 15 горо­дов, нам нуж­но будет делать 15 вло­жен­ных цик­лов и делать 120 про­ве­рок — это выгля­дит очень гро­мозд­ко, лег­ко оши­бить­ся в таком коде.
  2. Чем боль­ше будет горо­дов, тем мед­лен­нее будет счи­тать­ся резуль­тат. Уже на 10 горо­дах мы полу­чим 3,5 мил­ли­о­на выпол­не­ний тела цик­ла, что зай­мёт гораз­до боль­ше вре­ме­ни. На 13 горо­дах таких выпол­не­ний будет уже 6 мил­ли­ар­дов, и ком­пью­тер может их счи­тать неде­лю или даже больше. 

Попро­бу­ем испра­вить эти недо­стат­ки в сле­ду­ю­щих под­хо­дах к зада­че. Сле­ди­те за новы­ми статьями.

Текст и код:

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

Редак­ту­ра:

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

Худож­ник:

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

Кор­рек­тор:

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

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Ана­ста­сия Гаврилова