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

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

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

См. также

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

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

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

1 стартмани

03.07.2019    19597    4    m-rv    86    

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

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

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

3 стартмани

04.09.2019    23432    22    Stepa86    45    

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

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

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

1 стартмани

09.07.2019    16841    11    RonX01    10    

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

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

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

1 стартмани

01.06.2018    29735    86    m-rv    57    

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

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

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

1 стартмани

13.09.2018    21021    13    RocKeR_13    16    

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

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

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

1 стартмани

27.08.2018    35403    54    dsdred    15    

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

Инструментарий разработчика Практика программирования v8 Абонемент ($m)

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

5 стартмани

09.08.2018    27247    26    informa1555    26    

Заполняем по шаблону (по умолчанию)

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

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

1 стартмани

08.02.2018    27452    19    mvxyz    17    

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

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

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

1 стартмани

17.07.2018    44971    17    kalyaka    16    

Полезные примеры составления схемы компоновки данных #2

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

Еще один набор примеров как решить частные задачи в СКД

1 стартмани

22.05.2018    29673    11    SITR-utyos    13    

Нечеткий поиск одним запросом Промо

Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

28.12.2015    26881    69    vasvl123    9    

Печатная форма, сделанная как расширение конфигурации для БП 3.0. Новые возможности БСП

Практика программирования Универсальные печатные формы v8 БП3.0 Абонемент ($m)

Печатные формы на внешних обработках скоро канут в лету. На смену им приходят ПФ, реализованные в виде расширений конфигурации. Не нашел на сайте примеров таких расширений. Привожу пример подобного расширения для БП 3.0.

1 стартмани

06.12.2017    26317    49    kwazi    6    

Паузы при исполнении кода (Sleep для 1С)

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

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

1 стартмани

28.11.2017    43144    12    swimdog    41    

Быстрое определение интервалов в запросе Промо

Практика программирования v8 Абонемент ($m)

В статье описывается новый метод определения интервалов между данными различных записей в запросе. В отличие от общеизвестного метода, время работы предлагаемого метода зависит от объема данных ЛИНЕЙНО. Это обеспечивает ему значительный выигрыш по быстродействию на больших объемах данных. В качестве иллюстрации возможностей метода приведен отчет, показывающий гистограмму распределения времени между продажами.

1 стартмани

01.10.2015    50508    35    ildarovich    41    

Макет в СКД - пример всех возможных типовых вариантов

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

Макет СКД: наглядное представление того, что, как и куда выводится при типовых настройках.

1 стартмани

09.11.2017    21194    76    freelancer    4    

Telegram-боты

Практика программирования v8 Абонемент ($m)

Описание теории, разбор архитектуры и пример реализации telegram-ботов. Сразу скажу, со структурированием изложения мало что могу поделать. :) редакция от 18.07.2018 Правки последней редакции выделены жирным.

1 стартмани

01.09.2017    31442    130    PLAstic    57    

Умный дом на 1С + ардуино

Практика программирования v8 Абонемент ($m)

Конфигурация для автоматизации быта программиста 1C и не только. В данной статье будет рассказано, как можно использовать 1С для задач, не входящих в стандартные рамки этой платформы. Например, управление домом. В качестве периферии для подключения будет использован микроконтроллер (МК) Ардуино, но на нём не будет никакой логической нагрузки, весь процесс будет проходить на сервере 1С. Работа с пинами ввода/вывода происходит напрямую из 1С.

1 стартмани

07.08.2017    22079    21    sasha777666    63    

Расширения конфигураций 1С: учимся перехватывать методы

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

В этой статье я на примерах разберу некоторые механизмы расширений конфигураций 1С. А именно «перехваты» методов модуля объекта и «перехваты» событий формы и элементов формы. Данная статья написана с учебными целями, чтобы показать, как при помощи расширений конфигурации можно делать такие доработки, ради которых раньше приходилось снимать конфигурацию с поддержки.

1 стартмани

30.05.2017    125429    13    signum2009    48    

Регулярные выражения – это просто. Построитель и отладчик регулярных выражений

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

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

1 стартмани

13.03.2017    30609    112    romasna    49    

Распознавание текста с помощью нейросетей Google Cloud Vision и 1С

Практика программирования v8 1cv8.cf Абонемент ($m)

Возможности Google Cloud Vision в распознавании текста.

1 стартмани

08.02.2017    27821    123    kiv1c    18    

Графическая схема. Управление при помощи XDTO.

Практика программирования v8 Абонемент ($m)

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

2 стартмани

16.01.2017    21312    103    Alxby    23    

Простой редактор плана помещения JavaScript

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

На ресурсе сейчас очень много решений, которые позволяют редактировать карты, используя географические схемы. Так же много решений, которые позволяют редактировать объекты онлайн веб-карт. Мне же нужно было простое решение, для того чтобы расставить квадратные объекты на плане, показать их пользователю. Ну и распечатать, опять же. Я решил написать простенький редактор на JavaScript с использованием библиотеки Raphael.

1 стартмани

23.11.2016    20351    93    igel9780    22    

Работа с двоичными данными на примере чтения файлов изображений. Новые возможности 8.3.9

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

В статье приводятся новые функции по работе с двоичными данными, появившимися в версии платформы 8.3.9 , на примере анализа формата и размера изображений. А также пример отправки изображения через API ВКонтакте с помощью новых объектов (без использования ОбъединитьФайлы())

1 стартмани

14.11.2016    24708    16    Anton64    22    

Загрузка файлов на сервер с прогрессом и докачкой

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

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

1 стартмани

04.10.2016    12770    53    mrstomak    21    

Несколько шаблонов для доработки типовых конфигураций

Практика программирования Инструментарий разработчика v8 v8::УФ Абонемент ($m)

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

1 стартмани

03.10.2016    35894    95    json    25    

HTTP-сервис: отчеты [Расширение]

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

Это HTTP-сервис, который возвращает почти любой отчет в HTML, XLSX или в JSON. Сохраните вариант отчета, получите на него ссылку и можно получить данные без захода в 1С. Работает в конфигурациях на основе БСП 2.3.3+, для отчетов на СКД и в 1С 8.3.8+

2 стартмани

30.08.2016    25912    134    Stepa86    15    

1С: Предприятие + корпоративный чат, как наладить оперативные уведомления за 10 минут

Практика программирования v8 Абонемент ($m)

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

1 стартмани

14.08.2016    47327    36    Demanoidos    60    

Недокументированное использование стандартных форм Upd.

Практика программирования v8 v8::УФ 1cv8.cf Абонемент ($m)

Вам не хватает возможностей в платформе 1С или у Вас нет времени на углубленное изучение платформы 1С? Рассмотрены возможности использования стандартных форм, вызываемых из платформы.

1 стартмани

26.07.2016    27363    76    ZhokhovM    60    

Хранение файлов в томах на диске (для УПП 1.3)

Практика программирования v8 УПП1 Абонемент ($m)

Доработка типовой УПП 1.3 в плане хранения присоединенных файлов вне базы данных

2 стартмани

05.06.2016    55945    8    wowik    32    

БСП 2.3 и БСП 3.0: Просто про выполнение внешней обработки в фоне (c индикацией прогресса выполнения)

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

Простое пояснение о том, как сделать внешнюю обработку с фоновым выполнением и индикацией процесса для любой конфигурации на основе БСП 2.3.2. UPDATE 20/09/19: добавлен вариант обработки с индикацией процента выполнения и статусом выполнения для БСП 3.0.

1 стартмани

18.05.2016    59719    175    rozer    64    

Остатки на каждый день в запросе

Практика программирования Учет ТМЦ Учет ТМЦ v8 1cv8.cf УУ Абонемент ($m)

Запрос формирует остатки товаров на каждый день в пределах выбранного периода.

1 стартмани

26.04.2016    56411    19    arakelyan    18    

Еще один способ расчета остатков на каждый день в запросе

Математика и алгоритмы Практика программирования v8 Абонемент ($m)

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

1 стартмани

24.04.2016    33732    48    ildarovich    23    

Вывод печатных форм с запросом данных в форму "Печать документов" из подсистемы БСП "Печать".

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

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

1 стартмани

29.03.2016    86799    172    lopatin    14