Поиск кратчайшего пути между городами методом обратного отслеживания (поиском с возвратом)

Всем привет!

Представляю алгоритм на 1с - поиска кратчайшего пути между городами. Алгоритм использует полный перебор городов (вершин графа). Поэтому постановка исходной задачи предполагает наложение ограничений таких как, например, что между некоторыми городами нет проезда (нет дорог).

На обдумывание, создание, написание и отладку такого алгоритма меня сподвигнуло обсуждение со своим сыном задач 4  по ОГЭ по Информатики (для 9 классов). Задачи 9 по ОГЭ по Информатики решаются аналогичным алгоритмом (о них будет сказано ниже и отдельно). 

Среди задач по ОГЭ по Информатике (для 9 классов) встречаются задачи (№4) такого содержания. В таблице 5х5 указаны расстояния между городами. Необходимо определить кратчайший путь от одного города (например, А) до другого (В или Е), посетив каждый город только один раз. Иногда накладывается условие, что обязательно нужно посетить какой-то определенный город (например, С). Если между городами нет дороги, значит в соответствующей ячейке таблицы будет пусто (или ноль).

Скажем, исторически так сложилось, что мой сын сдал ОГЭ, и мы с ним обсуждали подобные задачи. Я написал алгоритм решения подобных задач.

Для учеников написание подобных алгоритмов не требуется, так как для этого необходимы минимальные знания методов динамического программирования, применения рекурсивных функций (процедур), знания и понимания синтаксиса языка программирования. На создание и отладку подобного алгоритма может уйти много времени. 

Представлена внешняя обработка на обычных формах, разработанная на платформе 1С:Предприятие 8.3 (8.3.27.1936). От конфигурации не зависит. В окне обработки в левом поле нужно указать данные из таблицы по задаче в виде матрицы 5х5: между числами должны быть пробелы, между строками можно оставлять пустые строки, можно и не оставлять - как вам удобно.

Практическое применение подобных задач - когда вам нужно отвезти товар по разным точкам, и вам необходимо при этом выбрать кратчайший путь. Сам алгоритм легко масштабировать до любых размеров 8х8, 14х14, 20х20 и т.д. - см. Листинг.

Перем МассивГородов; 
Перем МассивДлинПутей;
Перем МассивПутей; 
Перем СоответствиеГородов;
Перем СоответствиеИндексовГородам;  
Перем ИндексГородаФиниш;
Перем а; //матрица 5х5 - наша исходная таблица по задаче

Процедура НачатьРасчет()  
	
	МассивГородов = Новый Массив;
	МассивДлинПутей = Новый Массив;
	МассивПутей = Новый Массив;
	
	//стартуем с вершины А
	//А - 0, В - 1, С - 2, Д - 3, Е - 4 
	СоответствиеГородов = Новый Соответствие;
	СоответствиеГородов.Вставить(0,"А");
	СоответствиеГородов.Вставить(1,"В");  
	СоответствиеГородов.Вставить(2,"С");
	СоответствиеГородов.Вставить(3,"Д");
	СоответствиеГородов.Вставить(4,"Е");
	
	СоответствиеИндексовГородам = Новый Соответствие;
	СоответствиеИндексовГородам.Вставить("А", 0);
	СоответствиеИндексовГородам.Вставить("В", 1);
	СоответствиеИндексовГородам.Вставить("С", 2);
	СоответствиеИндексовГородам.Вставить("Д", 3);
	СоответствиеИндексовГородам.Вставить("Е", 4);

	ИндексГородаСтарт = СоответствиеИндексовГородам.Получить(Старт);
	ИндексГородаФиниш = СоответствиеИндексовГородам.Получить(Финиш);
	
	МассивГородов.Добавить(ИндексГородаСтарт); ДлинаПути = 0; ПредыдущийИндекс = ИндексГородаСтарт;
	РассчитатьПуть(ИндексГородаСтарт, МассивГородов, ДлинаПути, ПредыдущийИндекс);
	
КонецПроцедуры

Процедура РассчитатьПуть(i, МассивГородов, ДлинаПути, ПредыдущийИндекс) 
	
	Если МассивГородов.Получить(МассивГородов.Количество()-1) = ИндексГородаФиниш Тогда
		//Если достигли города Финиш 
		МассивДлинПутей.Добавить(ДлинаПути);  	
		Путь = "";
		Для Каждого Эл Из МассивГородов Цикл
			Путь = Путь + СоответствиеГородов.Получить(Эл);
		КонецЦикла;		
		МассивПутей.Добавить(Путь);       	
		
		Результат = Результат + Символы.ПС + Путь + " = " + ДлинаПути;
		         	
		МассивГородов.Удалить(МассивГородов.Количество()-1); 
		ДлинаПути = ДлинаПути - а[ПредыдущийИндекс][i];
	Иначе
		Для j = 0 По 4 Цикл      		
			Если МассивГородов.Найти(j) = Неопределено Тогда 			
				Если а[i][j]>0 Тогда
					МассивГородов.Добавить(j);
					ДлинаПути = ДлинаПути + а[i][j];
					РассчитатьПуть(j,МассивГородов,ДлинаПути, i);
				КонецЕсли;                   			
			КонецЕсли;    		
		КонецЦикла;
		Если МассивГородов.Получить(МассивГородов.Количество()-1) <> ИндексГородаФиниш Тогда  
			//Если прошли цикл по городам, и достигли "тупикового" города, который "не Финиш" 
			МассивГородов.Удалить(МассивГородов.Количество()-1); 
			ДлинаПути = ДлинаПути - а[ПредыдущийИндекс][i];
		КонецЕсли;             
	КонецЕсли;      	

КонецПроцедуры

Индексация массивов начинается с 0, названия городов: А, В, С, Д, Е - кириллицей для упрощения набора букв. Индекс i - отвечает за строки матрицы. Индекс j - отвечает за столбцы матрицы.   

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

Дополнительно, как задавать матрицы и умножать их между собой - описано здесь Матрицы и матричное программирование.

В задачах по ОГЭ Информатика встречается также задача 9 - по которой для представленной схемы связанных городов нужно найти все различные пути от города А в город К. Двигаться от города к городу можно только в одном направлении. Для такой задачи можно составить такую же матрицу, что и для задачи 4. Только матрица не будет симметричной, заполнена 1 если дорога от города к городу имеется и заполнена нулем (или пусто), если дороги между городами нет. Для такой матрицы алгоритм решения такой же, что и для задачи 4. 

Целью написания алгоритма с помощью рекурсивной модели не было создание полноценного коммерческого приложения. 

Целью написания алгоритма именно полного перебора было понимание, правильно ли ученик перебрал все варианты проезда, не упустил ли что-нибудь. При написании алгоритма можно было бы отсекать заведомо длинные пути, сравнивая с первым найденным коротким путем. Но снова мы вспоминаем цель написания алгоритма полного перебора - это самопроверка - нам нужно на выходе видеть все возможные пути и расстояния!

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

К примеру, во всех публикациях интернета  вас будут отговаривать использовать полный перебор, будут предложены другие алгоритмы обхода, например, алгоритм Дейкстры https://thecode.media/shortest-path/.

Если вы самостоятельно напишите алгоритм Дейкстры, как вы сможете проверить его правильность?

Один из вариантов сравнить с результатами поиска с алгоритмом полного перебора! Поэтому иметь алгоритм полного перебора необходимо, как стартовый алгоритм для сравнения всех последующих алгоритмов (а их очень много). Понятно, что вы будете ограничены количеством узлов для самопроверки.

Задумавшись над контекстом проблемы и задачи поиска наилучшего пути по точкам (магазинам) - к примеру, нужно отвезти товары со склада по магазинам - я пришел к тому, о чем в классической задаче коммивояжера не говорится.

А именно, что нам не всегда нужно искать кратчайший путь (в километрах). Сегодня организациям нужно искать наилучший путь - в терминах математики, это оптимальный путь с учетом стоимости заказов, тоннажа, габаритов груза, времени пути, сроков доставки. Мои мысли подтверждает статья https://blogs.epsilonmetrics.ru/route-optimization.

Дополнительно, я считаю, что в первом приближении, в реальных задачах для малых компаний, которые работают в УТ, можно объединять точки доставки (магазины) по "районам" (квадрантам, областям, зонам, улицам) - тем самым сокращая количество узлов - то есть, допускаем. что точки доставки одного "района" представляют собой один узел. Это будет решение первого приближения.

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

У решения, представленного в данной статье - есть свое название. Подобное использование рекурсии относится к алгоритмам Поиска с возвратом или Метода обратного отслеживания (Backtracking).

На этом все. Всем добра!