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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавляйте точки "Б", перетаскивайте их, изменяйте карту, жмякайте "Старт" и наблюдайте пошагово работу выбранного алгоритма. Стрелками "Влево"(кнопка 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
5
.rar 208,76Kb 5 Скачать

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

Лучшие комментарии
1. RonX01 230 13.08.19 11:42 Сейчас в теме
Если уж сильно хочется посмотреть то пожалуйста. :)
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе_v2.epf
Спецификация.pdf
Cirdan; MSK_Step; Merkalov; qazaas; chng; devilpc; shard; gaglo; maxdmt; товарищ Ын; Niang; AlX0id; Angealtor; khomkolov; Vanch90; vovaikilko; Ziggurat; botokash; Jeka44; izidakg; litonchik; vipchep; +22 Ответить
Остальные комментарии
Избранное Подписка Сортировка: Древо
1. RonX01 230 13.08.19 11:42 Сейчас в теме
Если уж сильно хочется посмотреть то пожалуйста. :)
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе_v2.epf
Спецификация.pdf
Cirdan; MSK_Step; Merkalov; qazaas; chng; devilpc; shard; gaglo; maxdmt; товарищ Ын; Niang; AlX0id; Angealtor; khomkolov; Vanch90; vovaikilko; Ziggurat; botokash; Jeka44; izidakg; litonchik; vipchep; +22 Ответить
2. herfis 312 13.08.19 13:10 Сейчас в теме
Еще и конструктор уровней :)
Поддержал стартманями.
4. RonX01 230 13.08.19 13:35 Сейчас в теме
3. herfis 312 13.08.19 13:17 Сейчас в теме
А что это за схема префиксации методов и переменных? Навскидку не соображу.
z12_1_ПоказатьНадписьВыбораНовойТочки() - что это означает?
5. RonX01 230 13.08.19 13:49 Сейчас в теме
(3) Это связано с изоморфной реализацией конечного автомата согласно спецификации.
Другими словами - сложная логика реализована в виде конечных автоматов. Они сначала проектируются - создается схема связей и граф перехода. На схеме связей как раз и происходит кодирование элементов (буква + число). Начальные буквы означают: е - событие, х - булева переменная, а z - это действие которое будет выполнено.
Кодирование помогает компактно отражать логику на графе перехода.
После окончания проектирования конечных автоматов они реализуются изморфно, т.е. по спецификации. Таким образом, z12_1_ПоказатьНадписьВыбораНовойТочки(), где z12_1 - номер действия, который можно найти в спецификации, а ПоказатьНадписьВыбораНовойТочки - текст, который расшифровывает действие.
6. herfis 312 13.08.19 15:14 Сейчас в теме
(5) А, привязка к спецификации! Ок.
Но разобраться в спецификации методом научного тыка не удалось :)
8. RonX01 230 14.08.19 06:12 Сейчас в теме
(6) Да, к сожалению приходится погрузиться хоть немного в тему, чтобы читать спецификацию.
Если интересно, то вот книга, по которотой спецификация и сделана -
http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
На мой взгляд очень легко и интересно написано.
9. RonX01 230 14.08.19 06:30 Сейчас в теме
(6) Кстати, мне кажется, что протокол тестирования должен помочь разобраться в спецификации (кнопка "Показать протокол тестирования").
Например, нажав на клетку в протокле тестирования будет трассировка автоматов, это по сути интерактивная отладка.
7. Yashazz 2950 13.08.19 19:02 Сейчас в теме
Нравится однозначно, спасибо!
10. shard 251 14.08.19 16:01 Сейчас в теме
В случае поиска путей по маршруту из нескольких точек будет иметь смысл предусмотреть величину забираемого груза в точке. Пригодится например в случае поиска оптимального маршрута кладовщика по складу: если в первой точке он зацепит 300кило, то будет тяжело потом заехать потом еще в 5 мест и забрать оттуда мелочевки по 1-2кг.
Оставьте свое сообщение

См. также

Краткое руководство по внесению изменений в конфигурацию

Статья Программист Нет файла v8 1cv8.cf Абонемент ($m) Практика программирования

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

1 стартмани

13.01.2020    5327    12    sapervodichka    34       

PgConf.Russia 2020. 3-5 февраля 2020 г. Москва. Промо

PGConf.Russia – международная техническая конференция по открытой СУБД PostgreSQL, ежегодно собирающая более 700 разработчиков, администраторов баз данных и IT-менеджеров для обмена опытом и профессионального общения. Для участников сообщества infostart.ru скидка 5% на участие в конференции.

от 12350 рублей

Полезные процедуры и функции для программиста

Статья Программист Нет файла v8 1cv8.cf Россия Абонемент ($m) Практика программирования Универсальные функции

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

1 стартмани

07.10.2019    15286    4    HostHost    24       

Описание формата внутреннего представления данных 1С в контексте обмена данными

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

Фирма 1С не рекомендует использовать внутреннее представление данных для любых целей, которые отличны от обмена с 1С:Предприятием 7.7. Но сама возможность заглянуть на "внутреннюю кухню" платформы с помощью функций ЗначениеВСтрокуВнутр(), ЗначениеВФайл(), ЗначениеИзСтрокиВнутр() и ЗначениеИзФайла(), дала возможность сообществу программистов 1С разработать новые приемы разработки и анализа. Так, именно на использовании внутреннего представления был построен алгоритм "быстрого массива", который позволяет практически мгновенно создать массив в памяти на основании строки с разделителями. С помощью разбора внутреннего представления можно "на лету" программным кодом выполнить анализ обычной формы и даже сделать редактор графической схемы. Во внутреннем формате сохраняют свои данные между сеансами различные популярные внешние обработки. А еще это возможность сделать быстрый обмен с внешними системами.

1 стартмани

06.09.2019    8362    7    Dementor    27       

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

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

Конвейер проверки качества кода

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

Jenkinsfile для выполнения проверки качества кода. Собирает информацию с АПК, EDT и BSL-LS. Сопоставляет ошибки с гит-репозиторием, выгруженным ГитКонвертором. Отправляет в Сонар.

3 стартмани

04.09.2019    9744    16    Stepa86    37       

Перенос документов, остатков и справочников КА 1.1 => КА 2 / УТ 11. Обновлено до КА 2.4.12.х и УТ 11.4.11.х! Промо

Более 130 компаний выполнили переход на КА 2 или УТ 11 с помощью нашей разработки! Позволяет перенести не только остатки и справочники (как типовая обработка), но и документы за нужный период времени. Предоставляем техподдержку, оперативно исправляем замечания, выпускаем обновления при выходе новых релизов программ 1С. Вы можете проверить разработку до покупки: сделаем бесплатный тестовый перенос из вашей базы КА 1.1 и предоставим доступ к базе-результату через веб-клиент!

29700 руб.

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

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

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

1 стартмани

09.07.2019    9345    11    RonX01    10       

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

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

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

1 стартмани

03.07.2019    12727    1    m-rv    79       

1C:Предприятие для программистов: Запросы и отчеты. Второй поток. Онлайн-интенсив с 17 марта по 16 апреля 2020 г. Промо

Данный онлайн-курс предусматривает углубленное изучение языка запросов и возможностей системы компоновки данных, которые понадобятся при разработке отчетов, работающих на платформе “1С:Предприятие” в рамках различных прикладных решений. Курс предназначен для тех, кто уже имеет определенные навыки конфигурирования и программирования в системе “1С:Предприятие”, а также для опытных пользователей различных прикладных решений, которые используют в своей работе отчеты разного назначения.

6500 рублей

1С:Ассемблер. Немного летнего веселья!

Статья Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования Разработка

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

1 стартмани

21.06.2019    18009    55    Evil Beaver    116       

Простые примеры сложных отчетов на СКД

Статья Программист Архив с данными v8 v8::СКД 1cv8.cf Абонемент ($m) Практика программирования

Подписи в отчете. Особенности соединения наборов: как соединить несоединяемое. Остатки на дату и обороты по месяцам в одном отчете. Курс валюты на каждую дату без группировок и соединений в запросе. Отчет с произвольными колонками и с произвольной последовательностью. "Неадекватный отчет".

1 стартмани

12.06.2019    17985    16    Hatson    22       

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

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

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

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

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

1 стартмани

25.03.2019    19811    8    tormozit    44       

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

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

HTML в новой версии 8.3.14 на примере 3-х JavaScript библиотек: AmCharts, HighCharts, DHTMLX

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

Тестируем возможности HTML в новой версии 8.3.14 платформы на примере 3-х JavaScript библиотек: AmCharts, HighCharts, DHTMLX.

1 стартмани

29.01.2019    17898    74    Synoecium    40       

Отладка сложных отчетов на СКД

Отчеты и формы Программист Расширение (cfe) v8 v8::СКД 1cv8.cf Россия Абонемент ($m) Практика программирования

Расширение для отладки сложных отчетов на СКД (в т.ч. для собираемых программно "на лету") и быстрого перехода к отладке таких отчетов в консоли запросов и отчетов на СКД.

1 стартмани

28.12.2018    17376    63    maxx    58       

INFOSTART MEETUP Krasnodar. 14 февраля 2020 г. Промо

Краснодар станет первым в 2020 году местом, где пройдет региональная встреча IT-специалистов сообщества Инфостарт. Тема мероприятия - управление и технологии автоматизации учета на платформе "1С: Предприятие". Стоимость участия - 5000 рублей. Цена действительна до 26.12.2019.

Реализация простого http-сервиса "Просмотр карточки номенклатуры(товара) в браузере"

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

Практический пример реализации простого http-сервиса средствами 1С Предприятие 8.3. Обеспечивает просмотр списка товаров и просмотр данных товара в браузере.

1 стартмани

07.12.2018    15944    12    dmitry1975    31       

Использование подсистемы БСП "Заполнение объектов"

Статья Программист Расширение (cfe) v8 v8::УФ 1cv8.cf Россия Абонемент ($m) Практика программирования Универсальные функции БСП (Библиотека стандартных подсистем)

Применение механизмов БСП для добавления новых команд заполнения к формам различных объектов. Использование расширений конфигурации для доработки. Шаблоны для реализации собственных команд заполнения.

1 стартмани

23.11.2018    16813    10    ids79    23       

Перенос данных КА 1.1 / УПП 1.3 => БП 3.0 (перенос остатков, документов и справочников из "1С:Комплексная автоматизация 1.1" / УПП 1.3 в "1С:Бухгалтерия 3.0"). Обновлен до версий КА 1.1.115.х, УПП 1.3.130.х! Промо

Разработка позволяет перенести остатки по всем счетам бух.учета в программу "1С:Бухгалтерия предприятия 8", ред. 3.0 на выбранную дату начала ведения учета. Также переносятся документы за период и вся необходимая справочная информация. Правила оперативно обновляю при выходе новых релизов. Рассылка обновлений правил бесплатно в течение 12 месяцев. Есть видеодемонстрация проведения переноса данных. Конфигурации при использовании обмена остаются полностью типовыми. Перенос данных возможен в Бухгалтерию 3.0 версии ПРОФ, КОРП или базовую.

24700 руб.

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

Инструменты и обработки Программист Архив с данными v8 УУ Абонемент ($m) Практика программирования О сообществе WEB

Работа с рублевыми публикациями на сайте "Инфостарт": ведение клиентов, заказов, обновление файлов публикации, рассылка обновлений.

1 стартмани

13.09.2018    11832    12    RocKeR_13    16       

HTTP Сервисы: Путь к своему сервису. Часть 3

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

Продолжение статьи «HTTP Сервисы: Путь к своему сервису. Часть 2». В предыдущих частях мы использовали только Get, в этой части поговорим о других методах и длительных операциях.

1 стартмани

27.08.2018    20544    32    dsdred    13       

Базовый курс для начинающих 1С-программистов. Пятый поток. Онлайн-курс с 12 февраля по 15 апреля 2020 г. Промо

Данный онлайн-курс является начальной ступенью по изучению базовых принципов программирования в системе “1С:Предприятие” и предназначен для обучения 1С-программированию “с нуля”.

4500/9500 рублей

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

Инструменты и обработки Программист Бизнес-аналитик Приложение (apk) v8 Windows Абонемент ($m) Инструментарий разработчика Практика программирования

Данная публикация содержит в себе редактор и интерактивную карту склада или иного помещения, на которой в реальном времени отображается позиция устройства, координаты которого вычисляются по уровням сигнала нескольких роутеров Wi-Fi. В статье и приложенным к ней разработкам предлагаются инструменты и методика для реализации вычисления точной геопозиции внутри помещений с помощью нейронной сети. Конфигурация написана на релизе 1С:Предприятие 8.3.12.1412, клиентское приложение имеет минимальный уровень совместимости SDK -16.

5 стартмани

09.08.2018    18589    23    informa1555    26       

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

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

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

1 стартмани

17.07.2018    27203    16    kalyaka    16       

Открыто голосование за доклады на INFOSTART MEETUP Krasnodar Промо

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

HTTP Сервисы: Путь к своему сервису. Часть 1

Статья Системный администратор Программист Расширение (cfe) v8 1cv8.cf Абонемент ($m) Практика программирования WEB

Уже много было написано про http-сервисы, но то и дело всплывают «Новые» статьи по обмену между базами V8 по COM, что «Немножко» удивляет. Решил внести свои 5 копеек, поработаем с http-сервисом.

1 стартмани

15.07.2018    48447    19    dsdred    24       

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

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

Вас не обманывают ваши глаза, это запрос на изменение данных! И это работает без прямого доступа к БД, регистрации и смс.

1 стартмани

01.06.2018    21947    86    m-rv    57       

Программы для исполнения 54-ФЗ Промо

С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.

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

Статья Программист Внешняя обработка (ert,epf) v8 1cv8.cf Абонемент ($m) Практика программирования БСП (Библиотека стандартных подсистем)

Очень много попадается странных решений, которые можно решить через БСП:Дополнительные отчеты и обработки. Я бы вообще БСП из-за этой подсистемы переименовал в «Большое Спасибо Программистам». Поработаем с подсистемой в части написания регламентных заданий.

1 стартмани

10.05.2018    31986    30    dsdred    36       

Онлайн-курс «Практические аспекты внедрения регламентированного учета и расчета себестоимости в 1С:ERP на крупных промышленных предприятиях» с 17 февраля по 13 марта 2020 года. Промо

Курс рассчитан для подготовки экспертов по регламентированному учету и учету затрат для внедрения на крупных промышленных предприятиях с «исторически сложившимся» учетом

9000 рублей

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

Статья Программист Архив с данными v8 УПП1 Россия Windows Абонемент ($m) Практика программирования

Для чего это нужно. Например, нужно в одной базе получить какой-либо показатель из другой базы. Этот показатель вычисляется в каком-либо сложном отчете, который написан на СКД. Можно, конечно, "скопипастить" текст запроса из другой базы, немного подправить его и выполнять в том же COM подключении. Но с этим теряется гибкость: если отчет изменился, то нужно помнить о том, что где-то есть его "немного модифицированная" копия. В статье будет рассмотрен пример получения данных из базы ЗУП.

2 стартмани

08.05.2018    20069    10    wowik    3       

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

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

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

1 стартмани

24.04.2018    32134    77    kalyaka    34