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

13.08.19

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование		По подписке [?]	Купить один файл
Алгоритмы поиска пути в графе v2: .rar 208,76Kb 11	11	Скачать (1 SM)	Купить за 1 850 руб.

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

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

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

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

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

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

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

Жадный поиск

Функция Граф_ЖадныйПоиск(ТочкаА, ТочкиБ)
	
	ПриоритетнаяОчередь = ПриоритетнаяОчередь_Новый();
	ПриоритетнаяОчередь_Добавить(ПриоритетнаяОчередь, ТочкаА, 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/

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

+98 –

См. также

Метод Дугласа-Пойкера

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024 4590 stopa85 12

Алгоритм симплекс-метода

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023 9483 user1959478 52

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

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023 4463 maksa2005 8

Регулярки на 1С

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023 12072 8 SpaceOfMyHead 19

Мини-обзор разных решений задач

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023 5691 RustIG 9

Тестирование средств 1С для решения СЛАУ

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022 4820 gzharkoj 14

Модель распределения суммы по базе

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

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

1 стартмани

21.03.2022 9286 7 kalyaka 11

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Программист Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021 6996 fishca 12

Отзывы

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

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

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

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

Ответить

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

Подписаться на ответы Инфостарт бот

Свернуть все

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

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

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

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

Ответить

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

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

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

(2) Спасибо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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