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

13.08.19

Разработка - Математика и алгоритмы

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

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

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

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

  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/

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

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

1 стартмани

09.06.2023    7454    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8832    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

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

31.08.2021    7797    dusha0020    8    

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