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

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

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

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

92
Реализуем алгоритмы поиска пути в графе на платформе 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/

92

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

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

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

Лучшие комментарии
1. RonX01 213 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 213 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
dmitrydemenew; pchelkatoo; headMade; +3 Ответить
Остальные комментарии
Избранное Подписка Сортировка: Древо
1. RonX01 213 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 1237 09.07.19 15:55 Сейчас в теме
И не далее как пару недель назад : https://infostart.ru/public/1081085/)))
for_sale; +1 Ответить
3. aximo 1100 09.07.19 17:26 Сейчас в теме
Замечательно! Можно взять алгоритм не «выдумывая» его)))))

А как на счет волнового алгоритма?
4. RonX01 213 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 213 12.07.19 07:30 Сейчас в теме
(5) Пока пас. Может быть позже.
7. it@contlog.ru 12.07.19 12:01 Сейчас в теме
Тогда еще спрошу. В случае если есть несколько точек Б интересно какая из них ближайшая. Какой из них предпочтительней?
8. RonX01 213 14.07.19 09:15 Сейчас в теме
(7) При поиске в ширину можно добавить несколько вершин, тогда функцию можно расширить так:
Дополнение к коду

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

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

См. также

Альтернативный способ добавления элементов и реквизитов на формы 32

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 ERP2 УТ11 Россия Абонемент ($m) Работа с интерфейсом

Предлагаю альтернативный вариант добавления динамически создаваемых элементов и реквизитов на форму.

1 стартмани

09.09.2019    3993    5    bmk74    0       

Онлайн-курс "Технология выполнения проектов ERP-класса – процессный подход". Третий поток. Курс проходит с 21 января по 18 марта 2020 года. Промо

Курс разработан Внедренческим центром «Раздолье». Курс предназначен для подготовки аналитиков, архитекторов и руководителей проектов автоматизации процессов управления с использованием комплексных ИТ-систем (1С:ERP, 1С:УХ, 1С:КА, 1С:УТ). В основе курса лежит методика применения процессного подхода.

9000 рублей

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

Инструменты и обработки Программист Архив с данными v8 1cv8.cf Абонемент ($m) Практика программирования Разработка

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

1 стартмани

13.08.2019    2649    2    RonX01    10       

С 2020 года сервис «Продление поддержки конфигурации 1С:УПП» подорожает вдвое Промо

Успейте продлить поддержку УПП до повышения цен! Фирма «1С» предупредила об изменении цен на сервис «Продление поддержки конфигурации "1С:Управление производственным предприятием"». С 1 января 2020 года сервис подорожает в два раза.

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

Инструменты и обработки Программист Конфигурация (md, cf) v8 v8::Запросы 1cv8.cf Абонемент ($m) Практика программирования Разработка

Речь не только о том, что простейший запрос с "легальным" оформлением растянется на пол-экрана, речь еще обо всем, что нужно написать "в нагрузку" к тексту запроса. Все эти "Новый Запрос", "УстановитьПараметр" и последующие пляски с обработкой результата... Пора с этим заканчивать!

1 стартмани

03.07.2019    11243    1    m-rv    79       

Программы для исполнения 488-ФЗ: Маркировка товаров Промо

1 января 2019 года вступил в силу ФЗ от 25.12.2018 № 488-ФЗ о единой информационной системе маркировки товаров с использованием контрольных (идентификационных) знаков, который позволяет проследить движение товара от производителя до конечного потребителя. Инфостарт предлагает подборку программ, связанных с применением 488-ФЗ и маркировкой товаров.

Модель объекта 10

Инструменты и обработки Программист Конфигурация (md, cf) v8 Абонемент ($m) Инструментарий разработчика

Подсистема позволяет описать модель данных объекта, где описана зависимость между реквизитами, и затем использовать эту модель в разных сценариях работы с объектом. Версия платформы: 8.3.6 и выше. С небольшими доработками будет работать на 8.2.

1 стартмани

30.06.2019    4438    1    vadim1980    0       

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

Статья Программист Нет файла v8 1cv8.cf Россия Бесплатно (free) Практика программирования Математика и алгоритмы Разработка

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

24.06.2019    8243    RonX01    63       

Подборка программ для взаимодействия с ЕГАИС Промо

ЕГАИС (Единая государственная автоматизированная информационная система) - автоматизированная система, предназначенная для государственного контроля за объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции. Инфостарт рекомендует подборку проверенных решений для взаимодействия с системой.

"Убер на складе": динамический расчет маршрутов с учетом реальных расстояний 66

Статья Программист Конфигурация (md, cf) v8 УУ Учет ТМЦ Абонемент ($m) Практика программирования

Представляю методику и инструмент для динамического расчета маршрутов отбора на высоконагруженных складах для максимального повышения эффективности склада, ускорения проходимости и, как следствие, экономии денег. Это методика и обработка для интеграции в WMS решения. Тестировалось на 1С 8.3.14.1565.

3 стартмани

24.06.2019    6530    5    informa1555    16       

Цифровая подпись Cades-BES для XML средствами 1С с помощью КриптоПро 6

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Россия Windows Абонемент ($m) Защита и шифрование

Обработка иллюстрирует возможность подписания XML SOAP-конверта по стандарту Cades-BES средствами 1С с помощью внешней компоненты КриптоПРО "CAdESCOM" с учетом ГОСТ 2001 и ГОСТ 2012. Стандарт используется в различных механизмах государственных сайтов России, в том числе в СМЭВ и ГИС ЖКХ. Код не привязан к прикладному решению может быть встроен куда угодно, но только на платформе Windows.

1 стартмани

13.05.2019    4311    12    PythonJ    25       

Перенос данных УПП 1.3 => ERP 2 (ЕРП) / УТ 11 / КА 2.х (обработка переноса документов, остатков и справочников из "1С:Управление производственным предприятием, ред. 1.3" в ERP / УТ 11 / КА 2). Обновлен до УПП 1.3.127.х, КА 2.4.10.х и ERP 2.4.10.х! Промо

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

29700 руб.

Быстрый запрос 42

Отчеты и формы Программист Пользователь Внешняя обработка (ert,epf) v8 v8::УФ 1cv8.cf Абонемент ($m) Универсальные обработки

Можно ли дать пользователю "удочку", а не "рыбу"? До сих пор ответ на этот вопрос был отрицательным. Всякий инструмент, который мог бы делать с базой данных все или почти все (или хотя бы многое), отвергался пользователями, как слишком сложный. Вспомните тот же SQL, который изначально разрабатывался именно как пользовательский инструмент. "Быстрый запрос" - это попытка устранить сложность, но сохранить при этом универсальность.

1 стартмани

29.04.2019    7330    15    mkalimulin    28       

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

Статья Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования

Разбираемся с опасностями использования транзакций во встроенном языке 1С. Познаем ошибку "В данной транзакции уже происходили ошибки". Учимся защищаться от них.

1 стартмани

25.03.2019    17372    8    tormozit    44       

Очный семинар по регулярному менеджменту Александра Фридмана "Вы или Хаос", 12 декабря 2019 г. , Санкт-Петербург Промо

Семинар по регулярному менеджменту от Александра Фридмана для собственников, первых лиц и топов. Технология управленческого планирования, комплексного управления временем и другими ресурсами, выполнением поручений, делами, информацией, контактами (встречи-звонки-почта).

от 11000 до 29000 рублей

Трудовой договор, Дополнительное соглашение, Лист ознакомления, Договор о материальной ответственности, Договор о коммерческой тайне, Согласие на обработку персональных данных для ЗУП 3.1 18

Отчеты и формы Бухгалтер Внешняя обработка (ert,epf) v8 v8::СПР ЗУП3.x Россия БУ Зарплата Управление персоналом (HRM) Абонемент ($m) Печатные формы документов

Комплект печатных форм для отдела кадров для документов Прием на работу и Кадровый перевод: Трудовой договор, Доп. соглашение к трудовому договору, Лист ознакомления с локальными нормативными актами, Договор о полной материальной ответственности, Договор о неразглашении коммерческой тайны, Согласие на обработку персональных данных.

2 стартмани

12.03.2019    14847    81    Asenka    5       

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

Инструменты и обработки Программист Конфигурация (md, cf) v8 1cv8.cf Абонемент ($m) Практика программирования Внешние источники данных WEB Универсальные функции Инструментарий разработчика Универсальные обработки

Коннектор - библиотека для работы с HTTP запросами. Библиотека берет на себя всю рутину работы с HTTP запросами. Буквально в одну строку можно получать данные, отправлять, не заботясь о необходимости конструирования URL, кодирования данных и т.п.

1 стартмани

31.01.2019    30826    274    bonv    116       

1С:Предприятие через Интернет. 1С:Fresh Промо

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

Редактор объектов информационной базы 8.3 42

Инструменты и обработки Программист Пользователь Внешняя обработка (ert,epf) v8 v8::УФ 1cv8.cf Россия Windows Абонемент ($m) Инструментарий разработчика Универсальные обработки

Универсальная внешняя обработка (СДРОбъектУпр) для редактирования реквизитов и табличных частей объектов информационной базы, редактирование движений документов. Доступ ко всем реквизитам объектов, есть возможность выгрузки и загрузки данных (объекты и движения документов) через XML. Платформа 8.3, управляемые формы. Версия 1.1.0.35 от 25.11.2019

2 стартмани

23.01.2019    11831    153    ROL32    28       

Расширение "Курсы валют в формулах расчета динамических цен" для УНФ 1.6 5

Инструменты и обработки Программист Пользователь Архив с данными v8 УНФ УУ Ценообразование, анализ цен Абонемент ($m) Ценообразование, прайсы

Расширение "Курсы валют в формулах расчета динамических цен" с автоматическим пересчетом цен при изменении курсов валют для конфигурации "Управление нашей фирмой, редакция 1.6"

5 стартмани

17.01.2019    6584    13    Palmer1976    4       

Готовые переносы данных из различных конфигураций 1C Промо

Рекомендуем готовые решения для переноса данных из различных конфигураций 1C. C техподдержкой от разработчиков и гарантией от Инфостарт.

Конструктор мобильного клиента Simple WMS Client: способ создать полноценный ТСД без мобильной разработки. Теперь новая версия - Simple UI (обновлено 14.11.2019) 178

Инструменты и обработки Программист Архив с данными v8 v8::Mobile БУ УУ Android Оптовая торговля Производство готовой продукции (работ, услуг) Розничная торговля Учет ОС и НМА Учет ТМЦ Абонемент ($m) Инструментарий разработчика Сканер штрих-кода Терминал сбора данных Мобильная разработка

Simple WMS Client – это визуальный конструктор мобильного клиента для терминала сбора данных(ТСД) или обычного телефона на Android. Приложение работает в онлайн режиме через интернет или WI-FI, постоянно общаясь с базой посредством http-запросов (вариант для 1С-клиента общается с 1С напрямую как обычный клиент). Можно создавать любые конфигурации мобильного клиента с помощью конструктора и обработчиков на языке 1С (НЕ мобильная платформа). Вся логика приложения и интеграции содержится в обработчиках на стороне 1С. Это очень простой способ создать и развернуть клиентскую часть для WMS системы или для любой другой конфигурации 1С (УТ, УПП, ERP, самописной) с минимумом программирования. Например, можно добавить в учетную систему адресное хранение, учет оборудования и любые другие задачи. Приложение умеет работать не только со штрих-кодами, но и с распознаванием голоса от Google. Это бесплатная и открытая система, не требующая обучения, с возможностью быстро получить результат.

5 стартмани

09.01.2019    24641    225    informa1555    174       

Новый раздел на Инфостарте - Electronic Software Distribution Промо

Инфостарт напоминает: на нашем сайте можно купить не только ПО, связанное с 1С. В нашем арсенале – ESD-лицензии на ПО от ведущих вендоров: Microsoft, Kaspersky, ESET, Dr.Web, Аскон и другие.

  • Низкие цены, без скрытых платежей и наценок
  • Оперативная отгрузка
  • Возможность оплаты с личного счета (кешбек, обмен стартмани на рубли и т.п.)
  • Покупки идут в накопления для получения скидочных карт лояльности Silver (5%) и Gold (10%)

Сравнение pdf-файлов актов сверки 1

Инструменты и обработки Бухгалтер Внешняя обработка (ert,epf) v8 v8::БУ БП2.0 Россия БУ Дебиторская и кредиторская задолженность Абонемент ($m) Универсальные обработки

Обработка сравнивает два pdf-файла, в которых находятся стандартные печатные формы актов сверки, и показывает на экране совпадающие и/или отличающиеся по суммам документы взаиморасчетов.

1 стартмани

19.12.2018    7583    4    Torin99    2       

Вакансия Автор новостных обзоров на тему 1С и бухучета, По совместительству Промо

Редакция Infostart.ru будет рада сотрудничеству с 1С-специалистом, умеющим и любящим излагать свои мысли в письменной форме. Если вы работали в IT-изданиях или имеете опыт ведения технологического блога/канала/группы, если сможете сделать обзор обработок из каталога infostart.ru/public/all/, то у вас большое преимущество.

Проверка VAT номеров 2

Инструменты и обработки Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) WEB

Обработка для вызова сервиса проверка VAT номера.

1 стартмани

26.11.2018    5123    wtlz    0       

Обнуление остатков регистров бухгалтерии и накопления 41

Инструменты и обработки Системный администратор Программист Внешняя обработка (ert,epf) v8 v8::БУ v8::ОУ v8::УФ КА1 БП2.0 ЗУП2.5 УТ10 УПП1 УНФ БГУ ERP2 БП3.0 УТ11 УХ КА2 ЗУП3.x Россия Абонемент ($m) Универсальные обработки Чистка базы

Обработка позволяет обнулить остатки по регистру накопления или бухгалтерии на определенную дату. Поддерживается большинство типовых конфигураций (БП 3, БП 2, УТ 11, УТ 10, ЗУП 3, ЗУП 2, БГУ 2, БГУ 1, ERP, УПП, КА 2, КА 1, УХ 3, УХ 1, УНФ). Гибкая настройка (отборы, заполнение реквизитов и любых полей корр. счета, возможность обнулять ресурсы выборочно). Несколько режимов работы. Два интерфейса: простой и с расширенным набором настроек.

2 стартмани

19.11.2018    11285    181    morozov.sv    30       

Подборка решений для взаимодействия со ФГИС «Меркурий» Промо

С 1 июля 2019 года все компании, участвующие в обороте товаров животного происхождения, должны перейти на электронную ветеринарную сертификацию (ЭВС) через ФГИС «Меркурий». Инфостарт предлагает подборку программ, связанных с этим изменением.

Шпаргалка разработчика для работы с формами 23

Отчеты и формы Программист Архив с данными v8 Россия Абонемент ($m) Работа с интерфейсом

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

3 стартмани

31.10.2018    9231    68    ELAM    3       

Перенос данных УТ 10.3 => УТ 11 / КА 2 / ERP 2 (ЕРП 2) (документы, остатки и справочная информация из "1С:Управление торговлей, ред. 10.3" в УТ 11 / КА 2 / ERP 2). Обновлен до УТ 10.3.56.х, УТ 11.4.10.х, КА 2.4.10.х и ERP 2.4.10.х! Промо

Уже более 100 компаний приобрели перенос и выполнили переход на УТ 11 / КА 2 / ERP 2 с помощью нашей разработки! Обработка перехода с УТ 10.3 на УТ 11 / КА 2 / ERP 2 позволяет перенести не только остатки на указанную дату (как типовой перенос), но и все возможные документы за выбранный период. При выходе новых релизов этих программ оперативно выпускаем обновление обработки. Предоставляем техническую поддержку. Можем сделать бесплатный тестовый перенос!

29700 руб.

Навигатор по конфигурации базы 1С 8.3 107

Инструменты и обработки Программист Пользователь Внешняя обработка (ert,epf) v8 v8::УФ 1cv8.cf Россия Windows Абонемент ($m) Инструментарий разработчика Универсальные обработки

Универсальная внешняя обработка (СДРНавигаторУпр) для просмотра метаданных конфигураций баз 1С 8.3. Отображает свойства и реквизиты объектов конфигурации, их количество, основные права доступа и т.д. Отображаемые характеристики объектов: свойства, реквизиты, стандартные рекизиты, реквизиты табличных частей, предопределенные данные, регистраторы для регистров, движения для документов, команды, чужие команды, подписки на события, подсистемы. Отображает структуру хранения объектов базы данных, для регистров доступен сервис "Управление итогами". Небольшой набор сервисных функций для повседневной работы. Для программистов и пользователей. Платформа 8.3, управляемые формы. Версия 1.1.0.47 от 25.11.2019

3 стартмани

28.10.2018    18287    200    ROL32    47       

Открывашка ячеек таблиц 85

Инструменты и обработки Программист Расширение (cfe) v8 1cv8.cf Абонемент ($m) Работа с интерфейсом

Глобальное сочетание клавиш для открытия объекта по ссылке из текущей ячейки любой таблицы в большинстве управляемых форм

1 стартмани

27.10.2018    10533    11    tormozit    28