Алгоритмы поиска пути в графе. Часть 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
2
.rar 208,76Kb 2 Скачать

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

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

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

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

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

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

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

1 стартмани

07.10.2019    15126    4    HostHost    24       

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

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

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

1 стартмани

06.09.2019    8233    7    Dementor    27       

Онлайн-курс "Подготовка к экзамену 1С:Эксперт и 1С:Профессионал по технологическим вопросам" с 7 по 24 апреля 2020 г. Промо

На курсе вы получите практические навыки решения задач производительности 1С, в том числе характерных для высоконагруженных информационных систем (более 1000 пользователей). Подготовка к экзамену – только одна из составляющих курса. 70% слушателей приходят за знаниями, которые позволят расти и зарабатывать, делать сложные задачи на крупных проектах.

16450 рублей

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

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

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

3 стартмани

04.09.2019    9563    16    Stepa86    37       

Базовый курс по управлению ИТ-проектами. Курс проходит с 26 февраля по 22 апреля 2020 года. Промо

Отличительная черта курса - органичное сочетание трех вещей: 1.Теория проектного управления (PMI®+Agile Alliance+Российские ГОСТ+Методологии от 1С); 2. Опыт внедрения продуктов 1С (опыт франчайзи и успешных компаний + тренды Infostart Event и Agile Days); 3. Разбор реальных проблем и рекомендации экспертов по проектам слушателей. Мы будем фиксироваться на тех инструментах, которые реально оказываются полезными в практике руководителей проектов внедрения. Ведущая курса - Мария Темчина.

от 11000 рублей

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

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

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

1 стартмани

09.07.2019    9257    10    RonX01    10       

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

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

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

1 стартмани

03.07.2019    12655    1    m-rv    79       

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

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

9000 рублей

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

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

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

1 стартмани

21.06.2019    17862    55    Evil Beaver    116       

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

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

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

1 стартмани

12.06.2019    17840    16    Hatson    22       

Сдача регламентированной отчетности из программ 1С Промо

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

от 1500 руб.

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

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

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

1 стартмани

25.03.2019    19657    8    tormozit    44       

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

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

4500/9500 рублей

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    17732    70    Synoecium    40       

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

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

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

1 стартмани

28.12.2018    17240    63    maxx    58       

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

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

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

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

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

1 стартмани

07.12.2018    15868    12    dmitry1975    31       

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

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

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

1 стартмани

23.11.2018    16650    10    ids79    23       

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

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

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

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

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

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

1 стартмани

13.09.2018    11761    12    RocKeR_13    16       

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

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

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

1 стартмани

27.08.2018    20406    32    dsdred    13       

Управление ИТ-проектами. Модуль 2: продвинутый онлайн-курс по классическим методам управления проектами. Вебинары проходят с 12 марта по 11 июня 2020 года. Промо

Продвинутый онлайн-курс по классическому управлению ИТ-проектами позволит слушателям освоить инструменты из PMBoK® и 1С:Технологии корпоративного внедрения и научиться их применять для проектов любого масштаба. Курс включает в себя 12 вебинаров и 12 видеолекции, разбор кейсов и рекомендации экспертов по проектам слушателей. Ведущая курса - Мария Темчина.

от 13000 рублей

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

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

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

5 стартмани

09.08.2018    18518    23    informa1555    26       

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

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

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

1 стартмани

17.07.2018    26921    15    kalyaka    16       

Базовый курс по разработке мобильных 1C-приложений для Android-устройств. Третий поток. Онлайн-интенсив с 11 февраля по 05 марта 2020 г. Промо

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

7500 рублей

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

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

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

1 стартмани

15.07.2018    47997    18    dsdred    24       

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

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

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

1 стартмани

01.06.2018    21873    86    m-rv    57       

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

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

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

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

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

1 стартмани

10.05.2018    31782    30    dsdred    36       

Перенос данных УТ 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 руб.

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

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

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

2 стартмани

08.05.2018    20000    10    wowik    3       

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

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

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

1 стартмани

24.04.2018    32012    77    kalyaka    34