Алгоритмы поиска пути в графе. Часть 2

Публикация № 1103399

Программирование - Практика программирования

Граф Дейкстры Алгоритм поиска пути автоматное программирование конечный автомат А* волновой

Новые возможности, ранее реализованных алгоритмов поиска пути в графе на платформе 1С 8.3.

Это продолжение публикации Алгоритмы поиска пути в графе. Добавлены следующие возможности:

Несколько точек "Б". Теперь можно посмотреть поведение различных алгоритмов для множеств конечных точек "Б", и оценить длину путей.
Окрестности Мура. Теперь поиск можно осуществлять не только по четырем направлениям но и по восьми, т.е. учитывать диагональные направления. В связи с этим выведены настройки стоимостей путей.

Сами алгоритмы поиска будут выглядеть следующим образом (они не сильно изменились по сравнению с предыдущей публикации):

Поиск в ширину

Функция Граф_ПоискВШирину(ТочкаА)
	
	Очередь = Очередь_Новый();
	Очередь_Добавить(Очередь, ТочкаА);
	ПосещенныеВершины = Новый Структура;
	ПосещенныеВершины.Вставить(ТочкаА, Новый Структура("Родитель, Направление", "А"));
	
	Пока Не Очередь_Пустой(Очередь) Цикл
		Вершина = Очередь_Получить(Очередь);
		
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл  // Ключ - Вершина соседа, значение - Направление соседа
			Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда
				Очередь_Добавить(Очередь, Сосед.Ключ);
				ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура("Родитель, Направление", Вершина, Сосед.Значение));
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	Возврат ПосещенныеВершины;
	
КонецФункции

Поиск в ширину с ранним выходом

Функция Граф_ПоискВШиринуСРаннимВыходом(ТочкаА, ТочкиБ)
	
	Очередь = Очередь_Новый();
	Очередь_Добавить(Очередь, ТочкаА);
	ПосещенныеВершины = Новый Структура;
	ПосещенныеВершины.Вставить(ТочкаА, Новый Структура("Родитель, Направление", "А"));
	
	Пока Не Очередь_Пустой(Очередь) Цикл
		Вершина = Очередь_Получить(Очередь);
		
		Если ДостигнутыВсеТочкиБ(ТочкиБ, Вершина) Тогда // Проверка раннего выхода
			Прервать;
		КонецЕсли;
		
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл // Ключ - Вершина соседа, значение - Направление соседа
			Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда
				Очередь_Добавить(Очередь, Сосед.Ключ);
				ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура("Родитель, Направление", Вершина, Сосед.Значение));
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	Возврат ПосещенныеВершины;
	
КонецФункции

Жадный поиск

Функция Граф_ЖадныйПоиск(ТочкаА, ТочкиБ)
	
	ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый();
	ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ТочкаА, 0);
	ПосещенныеВершины = Новый Структура;
	ПосещенныеВершины.Вставить(ТочкаА, Новый Структура("Родитель, Направление", "А"));
	
	Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл
		Вершина = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь);
		
		Если ДостигнутыВсеТочкиБ(ТочкиБ, Вершина) Тогда // Проверка раннего выхода
			Прервать;
		КонецЕсли;
		
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл // Ключ - Вершина соседа, значение - Направление соседа
			Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда
				Приоритет = Граф_ПолучитьРасстояниеДоБлижайшейТочкиБ(Граф[Сосед.Ключ], ТочкиБ);
				ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, Приоритет);
				
				ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура("Родитель, Направление", Вершина, Сосед.Значение));
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	Возврат ПосещенныеВершины;
	
КонецФункции

Алгоритм Дейкстры

Функция Граф_АлгоритмДейкстры(ТочкаА, ТочкиБ)
	Перем ПосещеннаяВершина;
	
	ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый();
	ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ТочкаА, 0);
	ПосещенныеВершины = Новый Структура(ТочкаА, Новый Структура("Родитель, Стоимость, Направление", "А", 0));
	
	Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл
		Вершина = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь);
		
		Если ДостигнутыВсеТочкиБ(ТочкиБ, Вершина) Тогда // Проверка раннего выхода
			Прервать;
		КонецЕсли;
		
		СтоимостьРодителя = ПосещенныеВершины[Вершина].Стоимость;
		
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл // Ключ - вершина соседа, значение - Направление соседа
			НоваяСтоимость = СтоимостьРодителя + Граф_ПолучитьСтоимостьВершины(Сосед.Ключ) + Граф_ПолучитьСтоимостьДуги(Сосед.Значение);
			
			Если Не ПосещенныеВершины.Свойство(Сосед.Ключ, ПосещеннаяВершина)
				Или НоваяСтоимость < ПосещеннаяВершина.Стоимость
				Тогда
				Приоритет = НоваяСтоимость;
				ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, Приоритет);
				
				ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура("Родитель, Стоимость, Направление", Вершина, НоваяСтоимость, Сосед.Значение));
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	Возврат ПосещенныеВершины;
	
КонецФункции

Алгоритм А*

Функция Граф_АлгоритмА(ТочкаА, ТочкиБ)
	Перем ПосещеннаяВершина;
	
	ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый();
	ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ТочкаА, 0);
	ПосещенныеВершины = Новый Структура(ТочкаА, Новый Структура("Родитель, Стоимость, Направление", "А", 0));
	
	Пока Не ПриоритетнаяОчередь_Пустой(ПриоритетнаяОчередь) Цикл
		Вершина = ПриоритетнаяОчередь_Получить(ПриоритетнаяОчередь);
		
		Если ДостигнутыВсеТочкиБ(ТочкиБ, Вершина) Тогда // Проверка раннего выхода
			Прервать;
		КонецЕсли;
		
		СтоимостьРодителя = ПосещенныеВершины[Вершина].Стоимость;
		
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл // Ключ - вершина соседа, значение - Направление соседа
			НоваяСтоимость = СтоимостьРодителя + Граф_ПолучитьСтоимостьВершины(Сосед.Ключ) + Граф_ПолучитьСтоимостьДуги(Сосед.Значение);
			
			Если Не ПосещенныеВершины.Свойство(Сосед.Ключ, ПосещеннаяВершина)
				Или НоваяСтоимость < ПосещеннаяВершина.Стоимость
				Тогда
				Приоритет = НоваяСтоимость + Граф_ПолучитьРасстояниеДоБлижайшейТочкиБ(Граф[Сосед.Ключ], ТочкиБ);
				ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, Приоритет);
				
				ПосещенныеВершины.Вставить(Сосед.Ключ, Новый Структура("Родитель, Стоимость, Направление", Вершина, НоваяСтоимость, Сосед.Значение));
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	Возврат ПосещенныеВершины;
	
КонецФункции

Волновой алгоритм

Функция Граф_ВолновойАлгоритм_РаспространениеВолны(ТочкаА, ТочкиБ)
	
	Очередь = Очередь_Новый();
	Очередь_Добавить(Очередь, ТочкаА);
	ПосещенныеВершины = Новый Структура;
	ПосещенныеВершины.Вставить(ТочкаА, 0); // В значении храним номер волны
	
	Пока Не Очередь_Пустой(Очередь) Цикл
		Вершина = Очередь_Получить(Очередь);
		
		Если ДостигнутыВсеТочкиБ(ТочкиБ, Вершина) Тогда // Проверка раннего выхода
			Прервать;
		КонецЕсли;
		
		НомерВолны = ПосещенныеВершины[Вершина];
		
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл // Ключ - Вершина соседа, значение - Направление соседа
			Если Не ПосещенныеВершины.Свойство(Сосед.Ключ) Тогда
				Очередь_Добавить(Очередь, Сосед.Ключ);
				ПосещенныеВершины.Вставить(Сосед.Ключ, НомерВолны + Граф_ПолучитьСтоимостьДуги(Сосед.Значение));
			КонецЕсли;
		КонецЦикла;
		
	КонецЦикла;
	
	Возврат ПосещенныеВершины;
	
КонецФункции

Алгоритмы поиска на выходе предоставляют структуру ПосещенныеВершины. По ней строится путь от точки "А" до интересующей нас точки "Б". Для этого используются следующие функции:

Восстановление пути

Функция Граф_ПолучитьПуть(ПосещенныеВершины, ТочкаА, ТочкаБ)
	Перем ПосещеннаяВершина;
	Путь = Стек_Новый();
	Вершина = ТочкаБ;
	
	Пока Вершина <> ТочкаА И ПосещенныеВершины.Свойство(Вершина, ПосещеннаяВершина) Цикл
		ПосещеннаяВершина.Вставить("Вершина", Вершина);
		Стек_Положить(Путь, ПосещеннаяВершина);
		Вершина = ПосещеннаяВершина.Родитель;
	КонецЦикла;
	
	Возврат Путь;
КонецФункции

Восстановление пути волнового алгоритма

Функция Граф_ВолновойАлгоритм_ВосстановлениеПути(ПосещенныеВершины, ТочкаБ)
	Перем НомерВолны;
	Путь = Стек_Новый();
	Вершина = ТочкаБ;
	
	Пока ПосещенныеВершины.Свойство(Вершина, НомерВолны) И НомерВолны <> 0 Цикл // Если НомерВолны=0, то это точка А, т.е. достигли цели
		Стек_Положить(Путь, Вершина);
		
		// Выбираем соседа с наименьшим номером волны
		ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый();
		Для каждого Сосед Из Граф_ПолучитьСоседейВершины(Вершина) Цикл
			Если ПосещенныеВершины.Свойство(Сосед.Ключ, НомерВолны) Тогда
				ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, Сосед.Ключ, НомерВолны);
			КонецЕсли;
		КонецЦикла;
		
		Вершина = ПриоритетнаяОчередь_ПолучитьБезУдаления(ПриоритетнаяОчередь);
	КонецЦикла;
	
	Возврат Путь;
КонецФункции

При такой реализации на выходе получаем стек с вершинами в порядке следования. Начиная путь с точки "А" берем из стека вершину и движемся к ней, после ее достижения берем следующую, и так пока не опустошим стек.

Про то как реализовать стек можно посмотреть здесь (реализуем Стек, Очередь и Приоритетную очередь в 1С).

В алгоритмах поиска пути используется функция получения соседей поэтому приведу код для их вычислений:

Получение соседей

Функция Граф_ПолучитьСоседейВершины(Вершина)
	
	СвойстваВершины = Граф[Вершина];
	Колонка = СвойстваВершины.Колонка;
	Строка = СвойстваВершины.Строка;
	
	Соседи = Новый Структура;
	Соседи.Вставить(Карта_ПолучитьИмяВершины(Колонка + 1, Строка), "Право");
	Соседи.Вставить(Карта_ПолучитьИмяВершины(Колонка - 1, Строка), "Лево");
	Соседи.Вставить(Карта_ПолучитьИмяВершины(Колонка, Строка + 1), "Низ");
	Соседи.Вставить(Карта_ПолучитьИмяВершины(Колонка, Строка - 1), "Верх");
	
	Если Окрестности = "Неймана" Тогда // только 4 точки
		
		// Отсеиваем стены, т.е. соседи, это врешины, куда можно пройти
		Для каждого Сосед Из Соседи Цикл
			Если Граф[Сосед.Ключ].Состояние_у2 = у2_0_СТЕНА Тогда
				Соседи.Удалить(Сосед.Ключ);
			КонецЕсли;
		КонецЦикла;
		
	Иначе // Учитывать диагонали
		МакетДиагоналей = Новый Структура;
		МакетДиагоналей.Вставить("ВЛ", Новый Структура("Колонка, Строка", -1, -1));
		МакетДиагоналей.Вставить("ВП", Новый Структура("Колонка, Строка", +1, -1));
		МакетДиагоналей.Вставить("НП", Новый Структура("Колонка, Строка", +1, +1));
		МакетДиагоналей.Вставить("НЛ", Новый Структура("Колонка, Строка", -1, +1));
		
		// Отсеиваем стены, т.е. соседи, это врешины, куда можно пройти, а также диагонали
		Для каждого Сосед Из Соседи Цикл
			Если Граф[Сосед.Ключ].Состояние_у2 = у2_0_СТЕНА Тогда
				МакетДиагоналей.Удалить(Карта_ПолучитьД1(Сосед.Значение));
				МакетДиагоналей.Удалить(Карта_ПолучитьД2(Сосед.Значение));
				Соседи.Удалить(Сосед.Ключ);
			КонецЕсли;
		КонецЦикла;
		
		// Добавляем проходимые диагонали
		Для каждого Диагональ Из МакетДиагоналей Цикл
			Смещение = Диагональ.Значение;
			ДиагональнаяВершина = Карта_ПолучитьИмяВершины(Колонка + Смещение.Колонка, Строка + Смещение.Строка);
			Если Граф[ДиагональнаяВершина].Состояние_у2 <> у2_0_СТЕНА Тогда
				Соседи.Вставить(ДиагональнаяВершина, Диагональ.Ключ);
			КонецЕсли;
		КонецЦикла;
		
	КонецЕсли;
	
	Возврат Соседи;
	
КонецФункции

Для демонстрации новых возможностей доработал обработку. Выглядит она теперь так:

Добавляйте точки "Б", перетаскивайте их, изменяйте карту, жмякайте "Старт" и наблюдайте пошагово работу выбранного алгоритма. Стрелками "Влево"(кнопка A) или "Вправо"(D) можно шагать по выполненному алгоритму.

Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент.

ПС: для любителей автоматного программирования - обработка выполнена в стиле автоматного программирования и к ней идет спецификация, состоящая из схем связей и графов перехода (диаграмм состояний). Список литературы по автоматному программированию и конечным автоматам:

[1] - http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.

[2] - http://is.ifmo.ru/automata/

[3] - http://softcraft.ru/auto/

Скачать файлы

	Наименование	Файл	Версия	Размер
	Алгоритмы поиска пути в графе v2: .rar 208,76Kb 13.08.19 2	.rar		208,76Kb	2	Скачать

См. также

Алгоритмы поиска пути в графе

Реализуем Стек, Очередь и Приоритетную очередь в 1С

Безопасная работа с транзакциями во встроенном языке

Вам нравятся запросы в 1С?

ВСТАВИТЬ В Справочник.Номенклатура (Код, Наименование) ЗНАЧЕНИЯ ("001", "Новый товар")

Коннектор: удобный HTTP-клиент для 1С:Предприятие 8

Заполняем по шаблону (по умолчанию)

Нечеткий поиск одним запросом

Работа с публикациями "Инфостарт"

Как выполнить отчет на СКД через COM и получить данные отчета?

Позиционирование в помещении с помощью нейросети по сигналу Wi-Fi. Интерактивная карта склада в 1С с показом позиции

1С: Предприятие + корпоративный чат, как наладить оперативные уведомления за 10 минут

Как нарисовать граф на 1С

Работа с данными выбора

Быстрое определение интервалов в запросе

Простой способ индексирования интервалов

Бесплатная проверка контрагентов в ФНС (общий модуль с алгоритмом). На примере выводим статус в список справочника контрагентов

Хранение файлов в томах на диске (для УПП 1.3)

БСП: Дополнительная обработка (Регламенты), примеры от простого к сложному

Некоторая работа с данными через COM

Работа со схемой запроса

Специальные предложения

Лучшие комментарии

1. RonX01 189 13.08.19 11:42 Сейчас в теме

Если уж сильно хочется посмотреть то пожалуйста. :)

Прикрепленные файлы:

АлгоритмыПоискаПутиВГрафе_v2.epf
Спецификация.pdf

Ответить

Остальные комментарии

Избранное Подписка

1. RonX01 189 13.08.19 11:42 Сейчас в теме

Если уж сильно хочется посмотреть то пожалуйста. :)

Прикрепленные файлы:

АлгоритмыПоискаПутиВГрафе_v2.epf
Спецификация.pdf

Ответить

2. herfis 280 13.08.19 13:10 Сейчас в теме

Еще и конструктор уровней :)
Поддержал стартманями.

4. RonX01 189 13.08.19 13:35 Сейчас в теме

(2) Спасибо.

3. herfis 280 13.08.19 13:17 Сейчас в теме

А что это за схема префиксации методов и переменных? Навскидку не соображу.
z12_1_ПоказатьНадписьВыбораНовойТочки() - что это означает?

5. RonX01 189 13.08.19 13:49 Сейчас в теме

(3) Это связано с изоморфной реализацией конечного автомата согласно спецификации.
Другими словами - сложная логика реализована в виде конечных автоматов. Они сначала проектируются - создается схема связей и граф перехода. На схеме связей как раз и происходит кодирование элементов (буква + число). Начальные буквы означают: е - событие, х - булева переменная, а z - это действие которое будет выполнено.
Кодирование помогает компактно отражать логику на графе перехода.
После окончания проектирования конечных автоматов они реализуются изморфно, т.е. по спецификации. Таким образом, z12_1_ПоказатьНадписьВыбораНовойТочки(), где z12_1 - номер действия, который можно найти в спецификации, а ПоказатьНадписьВыбораНовойТочки - текст, который расшифровывает действие.

6. herfis 280 13.08.19 15:14 Сейчас в теме

(5) А, привязка к спецификации! Ок.
Но разобраться в спецификации методом научного тыка не удалось :)

8. RonX01 189 14.08.19 06:12 Сейчас в теме

(6) Да, к сожалению приходится погрузиться хоть немного в тему, чтобы читать спецификацию.
Если интересно, то вот книга, по которотой спецификация и сделана -
http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
На мой взгляд очень легко и интересно написано.

9. RonX01 189 14.08.19 06:30 Сейчас в теме

(6) Кстати, мне кажется, что протокол тестирования должен помочь разобраться в спецификации (кнопка "Показать протокол тестирования").
Например, нажав на клетку в протокле тестирования будет трассировка автоматов, это по сути интерактивная отладка.

7. Yashazz 2502 13.08.19 19:02 Сейчас в теме

Нравится однозначно, спасибо!

10. shard 251 14.08.19 16:01 Сейчас в теме

В случае поиска путей по маршруту из нескольких точек будет иметь смысл предусмотреть величину забираемого груза в точке. Пригодится например в случае поиска оптимального маршрута кладовщика по складу: если в первой точке он зацепит 300кило, то будет тяжело потом заехать потом еще в 5 мест и забрать оттуда мелочевки по 1-2кг.