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

13.08.19

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

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

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

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

Продолжение публикации здесь (Алгоритмы поиска пути в графе. Часть 2)

Алгоритмы поиска пути чаще всего используют в играх, но бывает и такое infostart.ru/public/1081085, где автор применяет алгоритм поиска А* для нахождения коротких путей на складе.

Вот статья на тему реализации некоторых алгоритмов поиска, в частности А* (Перевод здесь). На платформе 1С 8.3 (далее просто 1С) реализация таких алгоритмов будет следующей:

 
 Поиск в ширину
 
 Поиск в ширину с ранним выходом
 
 Жадный поиск
 
 Алгоритм Дейкстры
 
 Алгоритм А*

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

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

Теоретические описания алгоритмов приводить не буду. Выделю главные, на мой взгляд, моменты:

Поиск в ширину говорит нам как посетить все вершины, поэтому его применение гораздо шире, чем поиск пути.

Жадный поиск использует расстояние до цели как критерий выбора следующей вершины.

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

Алгоритм А* использует такие понятия как стоимость перемещения и расстояние до цели (на самом деле эвристика может быть другой). Т.е. это жадный поиск и алгоритм дейкстры в одном.

Для наглядности сделал обработку, которая выглядит так:

Пример работы алгоритма А*:

 

Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент. Карта, на которой отображается путь интерактивна т.е. можно мышкой переносить точки А и Б, ставить(убирать) стену, лес. Для алгоритмов А* и Дейкстры стоимость пути по лесу равна 3 единицам, по пустой ячейке 1.

Еще есть сайт где наглядно можно посмотреть и другие алгоритмы поиска пути.

 

UPD: Добавил волновой алгоритм

Волновой алгоритм визуально будет выглядеть как поиск в ширину с ранним выходом, только вместо стрелок будут указаны номера итерации (номера волн). А вот реализация будет отличаться, потому как на выходе получаем карту с волнами и по ней строим путь, выбирая соседа с наименьшим номером волны. Пока не дойдем до 0.

 
 Волновой алгоритм - распространение волны
 
 Волновой алгорити - восстановление пути

 

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

[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    7852    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 09.07.19 12:08 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
Спецификация.pdf
Vasvas05; cleaner_it; rom-x; Plotks2017; Aleskey_K; Alex17; wolfsoft; suepifanov; headMade; NeviD; login1020; tsukanov; Jeka44; Boo; sam441; kuzyara; pm74; khomkolov; litonchik; wowik; товарищ Ын; user764477; +22 Ответить
4. RonX01 321 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
cleaner_it; rom-x; Aleskey_K; dmitrydemenew; pchelkatoo; headMade; +6 Ответить
Остальные комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. RonX01 321 09.07.19 12:08 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
Спецификация.pdf
Vasvas05; cleaner_it; rom-x; Plotks2017; Aleskey_K; Alex17; wolfsoft; suepifanov; headMade; NeviD; login1020; tsukanov; Jeka44; Boo; sam441; kuzyara; pm74; khomkolov; litonchik; wowik; товарищ Ын; user764477; +22 Ответить
2. informa1555 2646 09.07.19 15:55 Сейчас в теме
И не далее как пару недель назад : https://infostart.ru/public/1081085/)))
for_sale; +1 Ответить
3. aximo 2027 09.07.19 17:26 Сейчас в теме
Замечательно! Можно взять алгоритм не «выдумывая» его)))))

А как на счет волнового алгоритма?
4. RonX01 321 10.07.19 11:14 Сейчас в теме
(3) Добавил волновой алгоритм. Спецификация обработки осталась прежней
Прикрепленные файлы:
АлгоритмыПоискаПутиВГрафе.epf
cleaner_it; rom-x; Aleskey_K; dmitrydemenew; pchelkatoo; headMade; +6 Ответить
5. it@contlog.ru 12.07.19 06:42 Сейчас в теме
хорошо, будет ли пример jump point search?
6. RonX01 321 12.07.19 07:30 Сейчас в теме
(5) Пока пас. Может быть позже.
7. it@contlog.ru 12.07.19 12:01 Сейчас в теме
Тогда еще спрошу. В случае если есть несколько точек Б интересно какая из них ближайшая. Какой из них предпочтительней?
8. RonX01 321 14.07.19 09:15 Сейчас в теме
(7) При поиске в ширину можно добавить несколько вершин, тогда функцию можно расширить так:
Дополнение к коду

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

ПС: Похоже надо делать продожение, где реализовать алгоритмом jump point search и возможность указывать множество точек Б.
Прикрепленные файлы:
10. it@contlog.ru 18.07.19 05:13 Сейчас в теме
(8) Точно!!! Про продолжение согласен.
9. wolfsoft 2421 15.07.19 08:04 Сейчас в теме
Дельная вещь, однозначно в копилку, и плюс от меня.
11. пользователь 11.05.21 20:09
Сообщение было скрыто модератором.
...
12. RustIG 1351 31.01.22 13:28 Сейчас в теме
Пробовал разобраться по книгам что такое конечный автомат или автомат Маркова - ничего не вышло. Если нет вводных базовых простым языком, то подступиться будет неподготовленному слушателю сложно.
На днях нашел в ютубе ролик, облегчающий вход в эту дисциплину математики и программирования: яндекс-практикум по конечным автоматам https://www.youtube.com/watch?v=LWA43vTeFGQ
Оставьте свое сообщение