Алгоритмы поиска пути в графе. Часть 2
Разработка - Практика программирования
Это продолжение публикации Алгоритмы поиска пути в графе. Добавлены следующие возможности:
- Несколько точек "Б". Теперь можно посмотреть поведение различных алгоритмов для множеств конечных точек "Б", и оценить длину путей.
- Окрестности Мура. Теперь поиск можно осуществлять не только по четырем направлениям но и по восьми, т.е. учитывать диагональные направления. В связи с этим выведены настройки стоимостей путей.
Сами алгоритмы поиска будут выглядеть следующим образом (они не сильно изменились по сравнению с предыдущей публикации):
Алгоритмы поиска на выходе предоставляют структуру ПосещенныеВершины. По ней строится путь от точки "А" до интересующей нас точки "Б". Для этого используются следующие функции:
При такой реализации на выходе получаем стек с вершинами в порядке следования. Начиная путь с точки "А" берем из стека вершину и движемся к ней, после ее достижения берем следующую, и так пока не опустошим стек.
Про то как реализовать стек можно посмотреть здесь (реализуем Стек, Очередь и Приоритетную очередь в 1С).
В алгоритмах поиска пути используется функция получения соседей поэтому приведу код для их вычислений:
Для демонстрации новых возможностей доработал обработку. Выглядит она теперь так:
Добавляйте точки "Б", перетаскивайте их, изменяйте карту, жмякайте "Старт" и наблюдайте пошагово работу выбранного алгоритма. Стрелками "Влево"(кнопка A) или "Вправо"(D) можно шагать по выполненному алгоритму.
Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент.
ПС: для любителей автоматного программирования - обработка выполнена в стиле автоматного программирования и к ней идет спецификация, состоящая из схем связей и графов перехода (диаграмм состояний). Список литературы по автоматному программированию и конечным автоматам:
[1] - http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
Специальные предложения
См. также
Альтернативный способ добавления элементов и реквизитов на формы 34
1 стартмани
09.09.2019 4103 6 bmk74 0
Подборка решений для взаимодействия со ФГИС «Меркурий» Промо
С 1 июля 2019 года все компании, участвующие в обороте товаров животного происхождения, должны перейти на электронную ветеринарную сертификацию (ЭВС) через ФГИС «Меркурий». Инфостарт предлагает подборку программ, связанных с этим изменением.
Новый раздел на Инфостарте - Electronic Software Distribution Промо
Инфостарт напоминает: на нашем сайте можно купить не только ПО, связанное с 1С. В нашем арсенале – ESD-лицензии на ПО от ведущих вендоров: Microsoft, Kaspersky, ESET, Dr.Web, Аскон и другие.
- Низкие цены, без скрытых платежей и наценок
- Оперативная отгрузка
- Возможность оплаты с личного счета (кешбек, обмен стартмани на рубли и т.п.)
- Покупки идут в накопления для получения скидочных карт лояльности Silver (5%) и Gold (10%)
Подборка программ для взаимодействия с ЕГАИС Промо
ЕГАИС (Единая государственная автоматизированная информационная система) - автоматизированная система, предназначенная для государственного контроля за объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции. Инфостарт рекомендует подборку проверенных решений для взаимодействия с системой.
Цифровая подпись Cades-BES для XML средствами 1С с помощью КриптоПро 6
1 стартмани
13.05.2019 4377 12 PythonJ 25
Базовый курс для начинающих 1С-программистов. Пятый поток. Онлайн-курс с 12 февраля по 15 апреля 2020 г. Промо
Данный онлайн-курс является начальной ступенью по изучению базовых принципов программирования в системе “1С:Предприятие” и предназначен для обучения 1С-программированию “с нуля”.
4500/9500 рублей
Готовые переносы данных из различных конфигураций 1C Промо
Рекомендуем готовые решения для переноса данных из различных конфигураций 1C. C техподдержкой от разработчиков и гарантией от Инфостарт.
1C:Предприятие для программистов: Запросы и отчеты. Второй поток. Онлайн-интенсив с 17 марта по 16 апреля 2020 г. Промо
Данный онлайн-курс предусматривает углубленное изучение языка запросов и возможностей системы компоновки данных, которые понадобятся при разработке отчетов, работающих на платформе “1С:Предприятие” в рамках различных прикладных решений. Курс предназначен для тех, кто уже имеет определенные навыки конфигурирования и программирования в системе “1С:Предприятие”, а также для опытных пользователей различных прикладных решений, которые используют в своей работе отчеты разного назначения.
6500 рублей
Расширение "Курсы валют в формулах расчета динамических цен" для УНФ 1.6 5
5 стартмани
17.01.2019 6681 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) 178
5 стартмани
09.01.2019 24890 228 informa1555 187
Перенос документов, остатков и справочников КА 1.1 => КА 2 / УТ 11. Обновлено до КА 2.4.10.х и УТ 11.4.10.х! Промо
Более 130 компаний выполнили переход на КА 2 или УТ 11 с помощью нашей разработки! Позволяет перенести не только остатки и справочники (как типовая обработка), но и документы за нужный период времени. Предоставляем техподдержку, оперативно исправляем замечания, выпускаем обновления при выходе новых релизов программ 1С. Вы можете проверить разработку до покупки: сделаем бесплатный тестовый перенос из вашей базы КА 1.1 и предоставим доступ к базе-результату через веб-клиент!
29700 руб.
С 2020 года сервис «Продление поддержки конфигурации 1С:УПП» подорожает вдвое Промо
Успейте продлить поддержку УПП до повышения цен! Фирма «1С» предупредила об изменении цен на сервис «Продление поддержки конфигурации "1С:Управление производственным предприятием"». С 1 января 2020 года сервис подорожает в два раза.
Обнуление остатков регистров бухгалтерии и накопления 42
2 стартмани
19.11.2018 11454 186 morozov.sv 30
Очный семинар по регулярному менеджменту Александра Фридмана "Вы или Хаос", 12 декабря 2019 г. , Санкт-Петербург Промо
Семинар по регулярному менеджменту от Александра Фридмана для собственников, первых лиц и топов. Технология управленческого планирования, комплексного управления временем и другими ресурсами, выполнением поручений, делами, информацией, контактами (встречи-звонки-почта).
от 11000 до 29000 рублей
Правила обмена данными из Бухгалтерии предприятия ред. 3.0 в Управление производственным предприятием ред. 1.3 2
3 стартмани
06.11.2018 5913 байт 0
Программы для исполнения 54-ФЗ Промо
С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.
Перенос документов и справочников ERP 2 / КА 2 / УТ 11 => БП 3.0 Промо
Перенос позволяет настроить собственный обмен данными между указанными программами, альтернативный предлагаемому фирмой 1С. Предоставляем техподдержку по всем вопросам данного обмена. Можем подключиться к вам удаленно для разбора ситуаций. Оперативно обновляем при выходе новых релизов 1С. Бесплатные обновления в течение полугода.
19700 руб.
Универсальный инструмент для переноса данных через табличный документ (УФ) 36
5 стартмани
15.10.2018 16968 97 json 32