Это продолжение публикации Алгоритмы поиска пути в графе. Добавлены следующие возможности:
- Несколько точек "Б". Теперь можно посмотреть поведение различных алгоритмов для множеств конечных точек "Б", и оценить длину путей.
- Окрестности Мура. Теперь поиск можно осуществлять не только по четырем направлениям но и по восьми, т.е. учитывать диагональные направления. В связи с этим выведены настройки стоимостей путей.
Сами алгоритмы поиска будут выглядеть следующим образом (они не сильно изменились по сравнению с предыдущей публикации):
Поиск в ширину
Поиск в ширину с ранним выходом
Жадный поиск
Алгоритм Дейкстры
Алгоритм А*
Волновой алгоритм
Алгоритмы поиска на выходе предоставляют структуру ПосещенныеВершины. По ней строится путь от точки "А" до интересующей нас точки "Б". Для этого используются следующие функции:
Восстановление пути
Восстановление пути волнового алгоритма
При такой реализации на выходе получаем стек с вершинами в порядке следования. Начиная путь с точки "А" берем из стека вершину и движемся к ней, после ее достижения берем следующую, и так пока не опустошим стек.
Про то как реализовать стек можно посмотреть здесь (реализуем Стек, Очередь и Приоритетную очередь в 1С).
В алгоритмах поиска пути используется функция получения соседей поэтому приведу код для их вычислений:
Получение соседей
Для демонстрации новых возможностей доработал обработку. Выглядит она теперь так:
Добавляйте точки "Б", перетаскивайте их, изменяйте карту, жмякайте "Старт" и наблюдайте пошагово работу выбранного алгоритма. Стрелками "Влево"(кнопка A) или "Вправо"(D) можно шагать по выполненному алгоритму.
Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент.
ПС: для любителей автоматного программирования — обработка выполнена в стиле автоматного программирования и к ней идет спецификация, состоящая из схем связей и графов перехода (диаграмм состояний). Список литературы по автоматному программированию и конечным автоматам:
[1] — http://is.ifmo.ru/books/_book.pdf — Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Еще и конструктор уровней 🙂
Поддержал стартманями.
А что это за схема префиксации методов и переменных? Навскидку не соображу.
z12_1_ПоказатьНадписьВыбораНовойТочки() — что это означает?
(2) Спасибо.
(3) Это связано с изоморфной реализацией конечного автомата согласно спецификации.
Другими словами — сложная логика реализована в виде конечных автоматов. Они сначала проектируются — создается схема связей и граф перехода. На схеме связей как раз и происходит кодирование элементов (буква + число). Начальные буквы означают: е — событие, х — булева переменная, а z — это действие которое будет выполнено.
Кодирование помогает компактно отражать логику на графе перехода.
После окончания проектирования конечных автоматов они реализуются изморфно, т.е. по спецификации. Таким образом, z12_1_ПоказатьНадписьВыбораНовойТочки(), где z12_1 — номер действия, который можно найти в спецификации, а ПоказатьНадписьВыбораНовойТочки — текст, который расшифровывает действие.
(5) А, привязка к спецификации! Ок.
Но разобраться в спецификации методом научного тыка не удалось 🙂
Нравится однозначно, спасибо!
(6) Да, к сожалению приходится погрузиться хоть немного в тему, чтобы читать спецификацию.
Если интересно, то вот книга, по которотой спецификация и сделана —
На мой взгляд очень легко и интересно написано.
(6) Кстати, мне кажется, что протокол тестирования должен помочь разобраться в спецификации (кнопка «Показать протокол тестирования»).
Например, нажав на клетку в протокле тестирования будет трассировка автоматов, это по сути интерактивная отладка.
В случае поиска путей по маршруту из нескольких точек будет иметь смысл предусмотреть величину забираемого груза в точке. Пригодится например в случае поиска оптимального маршрута кладовщика по складу: если в первой точке он зацепит 300кило, то будет тяжело потом заехать потом еще в 5 мест и забрать оттуда мелочевки по 1-2кг.