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

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

Разработка - Практика программирования

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

Реализуем алгоритмы поиска пути в графе на платформе 1С 8.3, такие как алгоритм А*, поиск в ширину, жадный поиск, алгоритм Дейкстры и вконце волновой.

Продолжение публикации здесь (Алгоритмы поиска пути в графе. Часть 2)

Алгоритмы поиска пути чаще всего используют в играх, но бывает и такое infostart.ru/public/1081085, где автор применяет алгоритм поиска А* для нахождения коротких путей на складе.

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

 
 Поиск в ширину
 
 Поиск в ширину с ранним выходом
 
 Жадный поиск
 
 Алгоритм Дейкстры
 
 Алгоритм А*

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

Выше описанная реализация возвращает направленные дуги в виде структуры, ключи которой будут вершины, а в значениях хранится направление следующей вершины. Таким образом, чтобы найти путь мы должны знать в какой вершине сейчас находимся и обратившись к полученной структуре находим вершину куда переместиться дальше. И так до тех пор пока есть куда перемещаться :).

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

Поиск в ширину говорит нам как посетить все вершины, поэтому его применение гораздо шире, чем поиск пути.

Жадный поиск использует расстояние до цели как критерий выбора следующей вершины.

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

Алгоритм А* использует такие понятия как стоимость перемещения и расстояние до цели (на самом деле эвристика может быть другой). Т.е. это жадный поиск и алгоритм дейкстры в одном.

Для наглядности сделал обработку, которая выглядит так:

Пример работы алгоритма А*:

 

Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент. Карта, на которой отображается путь интерактивна т.е. можно мышкой переносить точки А и Б, ставить(убирать) стену, лес. Для алгоритмов А* и Дейкстры стоимость пути по лесу равна 3 единицам, по пустой ячейке 1.

Еще есть сайт где наглядно можно посмотреть и другие алгоритмы поиска пути.

 

UPD: Добавил волновой алгоритм

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

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

 

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

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

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

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

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

Наименование Файл Версия Размер
Алгоритмы поиска пути в графе
.rar 120,68Kb
10.07.19
11
.rar 120,68Kb 11 Скачать

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

Лучшие комментарии
1. RonX01 274 09.07.19 12:08 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
Спецификация.pdf
Alex17; wolfsoft; suepifanov; headMade; NeviD; login1020; tsukanov; Jeka44; Boo; sam441; kuzyara; pm74; khomkolov; litonchik; wowik; товарищ Ын; user764477; +17 Ответить
4. RonX01 274 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
dmitrydemenew; pchelkatoo; headMade; +3 Ответить
Остальные комментарии
Избранное Подписка Сортировка: Древо развёрнутое
Свернуть все
1. RonX01 274 09.07.19 12:08 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
Спецификация.pdf
Alex17; wolfsoft; suepifanov; headMade; NeviD; login1020; tsukanov; Jeka44; Boo; sam441; kuzyara; pm74; khomkolov; litonchik; wowik; товарищ Ын; user764477; +17 Ответить
2. informa1555 1470 09.07.19 15:55 Сейчас в теме
И не далее как пару недель назад : https://infostart.ru/public/1081085/)))
for_sale; +1 Ответить
3. aximo 1633 09.07.19 17:26 Сейчас в теме
Замечательно! Можно взять алгоритм не «выдумывая» его)))))

А как на счет волнового алгоритма?
4. RonX01 274 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
dmitrydemenew; pchelkatoo; headMade; +3 Ответить
5. it@contlog.ru 12.07.19 06:42 Сейчас в теме
хорошо, будет ли пример jump point search?
6. RonX01 274 12.07.19 07:30 Сейчас в теме
(5) Пока пас. Может быть позже.
7. it@contlog.ru 12.07.19 12:01 Сейчас в теме
Тогда еще спрошу. В случае если есть несколько точек Б интересно какая из них ближайшая. Какой из них предпочтительней?
8. RonX01 274 14.07.19 09:15 Сейчас в теме
(7) При поиске в ширину можно добавить несколько вершин, тогда функцию можно расширить так:
Дополнение к коду

В результате мы получим карту с потоками до вершин. Т.е. зная вершину где мы находимся, используя такую карту мы сразу движемся в ближнюю точку (карта прикреплена ниже).
Если же необходимо предварительно знать размеры пути, то это будет похоже на волновой алгоритм, только волны будут расходиться от точки А, и поскольку там хранятся номера волн, то в каждой точке Б будет номер волны, и чем меньше номер, тем путь до точки Б ближе.
Но это не подойдет для жадного поиска и алгоритма А*.

ПС: Похоже надо делать продожение, где реализовать алгоритмом jump point search и возможность указывать множество точек Б.
Прикрепленные файлы:
10. it@contlog.ru 18.07.19 05:13 Сейчас в теме
(8) Точно!!! Про продолжение согласен.
9. wolfsoft 2421 15.07.19 08:04 Сейчас в теме
Дельная вещь, однозначно в копилку, и плюс от меня.
Оставьте свое сообщение

См. также

daСклонение: склонение ФИО, должностей, чисел, прилагательных, существительных на языке 1С + ТестЦентр Промо

Универсальные функции v8 1cv8.cf Абонемент ($m)

Функция предназначена для склонения выражений, которые часто требуется при формировании печатных форм договоров и прочих печатных форм. Функция склоняет по падежам ФИО, должности, числительные, валюты, единицы измерения, предметы. Также функция склоняет глаголы и прилагательные по числам и родам и существительные по числам. Имеется режим определения рода переданного выражения. Поддержка форматной строки для вывода результата. Функция не использует внешние библиотеки и веб-сервисы, написана на чистом языке 1С, и поэтому легко встраивается в любую конфигурацию или внешнюю обработку. Правила склонения оформлены в виде таблицы и могут быть легко изменены при необходимости.

1 стартмани

14.02.2015    99090    96    daMaster    88    

Сравнение реального дохода со средним доходом из API.HH.RU

Зарплата Управленческие v8 v8::СПР ЗУП3.x УУ Абонемент ($m)

Внешняя обработка на управляемой форме для 1С:Предприятие 8.3 по интеграции с HH.RU используя HH REST API. Ключевые функции: получение списка вакансий по должностям (Ключ для работы не нужен); расчет среднего дохода; Тестирование проводилось на платформе 1С:Предприятие 8.3 (8.3.13.1513) Зарплата и управление персоналом, редакция 3.1 (3.1.11.68) совместно с API.HH.RU.

1 стартмани

11.11.2019    3647    4    solaru    2    

Конфигурация для рекламного агентства

Управление услугами и сервисом Управление взаимоотношениями с клиентами (СRM) Производство готовой продукции (работ, услуг) Управление взаимоотношениями с клиентами (СRM) Производство готовой продукции (работ, услуг) v8 Реклама, PR и маркетинг УУ Абонемент ($m)

Данная конфигурация выполнена для решения тестового задания: Цель задания: 1) Понять, на каком из клиентов сколько мы заработали;  2) Понять, по какому виду СМИ сколько мы заработали;  3) Проследить по каждой услуге: у кого за сколько купили и кому за сколько продали, с возможностью перейти в соответствующий документ. Реализовано с помощью: 1. Справочники - контрагенты, номенклатура 2. Документы - Поступление услуг, реализация услуг 3. Отчеты - отчет по контрагентам, номенклатуре и движений.

1 стартмани

21.05.2019    3927    0    solaru    0    

Загрузка номенклатуры в УТ 10.3 из Excel файла с генерацией штрихкодов

Загрузка и выгрузка в Excel Обработка справочников Оптовая торговля Розничная торговля Учет ТМЦ Оптовая торговля Розничная торговля Учет ТМЦ v8 УТ10 Россия Абонемент ($m)

Обработка позволяет генерировать новые номенклатурные позиции на основе данных из файла Excel с последующей генерацией штрихкодов (ШК). Может быть полезна при больших поступлениях товаров на склад, где ручное создание и присваивание штрихкода  (ШК) может занимать много времени.

1 стартмани

24.03.2017    7529    6    solaru    0    

Под капотом управляемых форм

Практика программирования v8 1cv8.cf Бесплатно (free)

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

26.08.2013    260516    0    Evil Beaver    266    

[NotaBene] Универсальный отчет по таблице значений

Практика программирования v77::ОУ v77::БУ v77::Расчет 1cv7.md Россия Абонемент ($m)

1C v.7.7 Готовое решение. Не требует настройки. Не требует допрограммирования. Данная обработка решает часто встречающуюся задачу вывода в "красивом" виде таблицы значений (полученной, например, из запроса). Поддерживается произвольное группирование данных, отключение/включение группировок, в т.ч и создание "шахматок" (типа "продажи понедельно"). Обработка может использоваться как и в отладочных целях (для нормального просмотра ТЗ), так и в составе вполне рабочих отчетов. По крайней мере, я неоднократно клиентам данную обработку ставил вместо того, чтобы каждый раз писать замороченные выводы данных. И клиенты довольны, и мне - проще...

2 стартмани

07.05.2007    27919    1    CheBurator    61