X01 Ron

322
Рейтинг

RonX01



  •   Регистрация: 21.04.2019 (5 лет назад)

  •   Был(а) на сайте: вчера в 07:29

Друзья
  • Петр Малыгин
  • Дмитрий Малышев
  • R G
  • Евгений Комиссаров
Подписчики 19
Группы

Профессиональный разработчик

Рейтинг 322

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

Инструменты и обработки Программист Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m) Архив с данными Математика и алгоритмы

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

1 стартмани

13.08.2019    14857    11    RonX01    10       

97

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

Инструменты и обработки Программист Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m) Архив с данными Математика и алгоритмы

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

1 стартмани

09.07.2019    31243    14    RonX01    11       

118

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

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

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

24.06.2019    22302    RonX01    70       

92

Игра Змейка с автопилотом
+15 –

Отчеты и формы Для всех Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m) Архив с данными Игры

Игра Змейка с автопилотом реализована в парадигме автоматного программирования.

1 стартмани

23.04.2019    13490    2    RonX01    17       

15
Смотреть все

Комментарии

О жизни › Игра Змейка с автопилотом › #17 22.08.19 5:24
(15) Спасибо.
О жизни › Игра Змейка с автопилотом › #16 22.08.19 5:19
(14) :) и чтобы окончательно "убить" бухгалтера по кнопке "Подробнее" будет открываться схема связей.
Dev › Алгоритмы поиска пути в графе. Часть 2 › #9 14.08.19 6:30
(6) Кстати, мне кажется, что протокол тестирования должен помочь разобраться в спецификации (кнопка "Показать протокол тестирования").
Например, нажав на клетку в протокле тестирования будет трассировка автоматов, это по сути интерактивная отладка.
Dev › Алгоритмы поиска пути в графе. Часть 2 › #8 14.08.19 6:12
(6) Да, к сожалению приходится погрузиться хоть немного в тему, чтобы читать спецификацию.
Если интересно, то вот книга, по которотой спецификация и сделана -
http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
На мой взгляд очень легко и интересно написано.
Dev › Алгоритмы поиска пути в графе. Часть 2 › #5 13.08.19 13:49
(3) Это связано с изоморфной реализацией конечного автомата согласно спецификации.
Другими словами - сложная логика реализована в виде конечных автоматов. Они сначала проектируются - создается схема связей и граф перехода. На схеме связей как раз и происходит кодирование элементов (буква + число). Начальные буквы означают: е - событие, х - булева переменная, а z - это действие которое будет выполнено.
Кодирование помогает компактно отражать логику на графе перехода.
После окончания проектирования конечных автоматов они реализуются изморфно, т.е. по спецификации. Таким образом, z12_1_ПоказатьНадписьВыбораНовойТочки(), где z12_1 - номер действия, который можно найти в спецификации, а ПоказатьНадписьВыбораНовойТочки - текст, который расшифровывает действие.
Dev › Алгоритмы поиска пути в графе. Часть 2 › #4 13.08.19 13:35
(2) Спасибо.
Dev › Алгоритмы поиска пути в графе. Часть 2 › #0 13.08.19 12:40
Новые возможности, ранее реализованных алгоритмов поиска пути в графе на платформе 1С 8.3.
Dev › Алгоритмы поиска пути в графе. Часть 2 › #1 13.08.19 11:42
Если уж сильно хочется посмотреть то пожалуйста. :)

Прикрепленные файлы:

АлгоритмыПоискаПутиВГрафе_v2.epf
Спецификация.pdf
О жизни › Игра Змейка с автопилотом › #13 14.07.19 9:25
(11) Вложил свои 5 копеек коментарием в вашей публикации Сборка автомата (с примерами) :)
Dev › Алгоритмы поиска пути в графе › #8 14.07.19 9:15
(7) При поиске в ширину можно добавить несколько вершин, тогда функцию можно расширить так:
Дополнение к коду

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

ПС: Похоже надо делать продожение, где реализовать алгоритмом jump point search и возможность указывать множество точек Б.

Прикрепленные файлы:

2019-07-14_130248.png