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

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

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

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

57
Новые возможности, ранее реализованных алгоритмов поиска пути в графе на платформе 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/

57

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

Наименование Файл Версия Размер
Алгоритмы поиска пути в графе v2:
.rar 208,76Kb
13.08.19
2
.rar 208,76Kb 2 Скачать

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

Лучшие комментарии
1. RonX01 213 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 213 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 286 13.08.19 13:10 Сейчас в теме
Еще и конструктор уровней :)
Поддержал стартманями.
4. RonX01 213 13.08.19 13:35 Сейчас в теме
3. herfis 286 13.08.19 13:17 Сейчас в теме
А что это за схема префиксации методов и переменных? Навскидку не соображу.
z12_1_ПоказатьНадписьВыбораНовойТочки() - что это означает?
5. RonX01 213 13.08.19 13:49 Сейчас в теме
(3) Это связано с изоморфной реализацией конечного автомата согласно спецификации.
Другими словами - сложная логика реализована в виде конечных автоматов. Они сначала проектируются - создается схема связей и граф перехода. На схеме связей как раз и происходит кодирование элементов (буква + число). Начальные буквы означают: е - событие, х - булева переменная, а z - это действие которое будет выполнено.
Кодирование помогает компактно отражать логику на графе перехода.
После окончания проектирования конечных автоматов они реализуются изморфно, т.е. по спецификации. Таким образом, z12_1_ПоказатьНадписьВыбораНовойТочки(), где z12_1 - номер действия, который можно найти в спецификации, а ПоказатьНадписьВыбораНовойТочки - текст, который расшифровывает действие.
6. herfis 286 13.08.19 15:14 Сейчас в теме
(5) А, привязка к спецификации! Ок.
Но разобраться в спецификации методом научного тыка не удалось :)
8. RonX01 213 14.08.19 06:12 Сейчас в теме
(6) Да, к сожалению приходится погрузиться хоть немного в тему, чтобы читать спецификацию.
Если интересно, то вот книга, по которотой спецификация и сделана -
http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
На мой взгляд очень легко и интересно написано.
9. RonX01 213 14.08.19 06:30 Сейчас в теме
(6) Кстати, мне кажется, что протокол тестирования должен помочь разобраться в спецификации (кнопка "Показать протокол тестирования").
Например, нажав на клетку в протокле тестирования будет трассировка автоматов, это по сути интерактивная отладка.
7. Yashazz 2910 13.08.19 19:02 Сейчас в теме
Нравится однозначно, спасибо!
10. shard 251 14.08.19 16:01 Сейчас в теме
В случае поиска путей по маршруту из нескольких точек будет иметь смысл предусмотреть величину забираемого груза в точке. Пригодится например в случае поиска оптимального маршрута кладовщика по складу: если в первой точке он зацепит 300кило, то будет тяжело потом заехать потом еще в 5 мест и забрать оттуда мелочевки по 1-2кг.
Оставьте свое сообщение

См. также

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

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

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

1 стартмани

09.09.2019    4190    6    bmk74    0       

Новогодние скидки на авторское ПО Промо

В преддверии праздника в Маркетплейсе на Инфостарт действует скидка на все платные авторские программы. Размер скидок начинается от 10%. Советуем не откладывать покупки, многие наши партнеры повышают цены на свои продукты именно в начале нового года.

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

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

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

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

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

1 стартмани

09.07.2019    8043    8    RonX01    10       

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

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

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

1 стартмани

03.07.2019    11486    1    m-rv    79       

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

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

6500 рублей

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

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

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

1 стартмани

30.06.2019    4744    1    vadim1980    0       

Цифровая подпись 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    4494    12    PythonJ    25       

Многофункциональная выгрузка из 1С: Управление торговлей (УТ11, УТ10) в Бухгалтерию предприятия (БП2, БП3) Промо

Хотите точно знать, что вы выгружаете? Хотите сворачивать товары по НДС или фильтровать товары по доп. реквизиту? Вы волшебник, которому необходимо превращать одних контрагентов в других? Хотите при выгрузке превратить группу товаров в один? Или просто нужен удобный OLE обмен между 1C Управление торговлей (ред. 11 или 10) и 1С Бухгалтерия предприятия (ред. 2 или 3). Тогда эта обработка для вас!

9500 руб.

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

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

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

1 стартмани

29.04.2019    7581    15    mkalimulin    28       

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

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

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

1 стартмани

25.03.2019    17943    8    tormozit    44       

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

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

24700 руб.

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

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

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

2 стартмани

12.03.2019    15442    86    Asenka    7       

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

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

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

1 стартмани

31.01.2019    31554    283    bonv    117       

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

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

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

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

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

2 стартмани

23.01.2019    12225    157    ROL32    28       

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

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

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

5 стартмани

17.01.2019    6801    13    Palmer1976    4       

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

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

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

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

5 стартмани

09.01.2019    25280    229    informa1555    189       

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

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

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

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

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

1 стартмани

19.12.2018    7795    4    Torin99    2       

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

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

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

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

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

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

1 стартмани

26.11.2018    5337    wtlz    0       

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

Инструменты и обработки Системный администратор Программист Внешняя обработка (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    11626    186    morozov.sv    30       

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

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

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

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

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

3 стартмани

31.10.2018    9389    72    ELAM    3       

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

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

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

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

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

3 стартмани

28.10.2018    18621    202    ROL32    47       

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

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

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

1 стартмани

27.10.2018    10666    11    tormozit    28       

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

Расширение "Интерфейс Плюс" 44

Отчеты и формы Бухгалтер Пользователь Расширение (cfe) v8 v8::ОУ Розница УТ11 Россия УУ Розничная торговля Абонемент ($m) Рабочее место

Расширение для 1С:Розница 2.2 и 1С:Управление Торговлей 11, которое позволит повысить удобство работы!

3 стартмани

22.09.2018    11944    98    RocKeR_13    82