Алгоритмы поиска пути в графе. Часть 2
Разработка - Практика программирования
Это продолжение публикации Алгоритмы поиска пути в графе. Добавлены следующие возможности:
- Несколько точек "Б". Теперь можно посмотреть поведение различных алгоритмов для множеств конечных точек "Б", и оценить длину путей.
- Окрестности Мура. Теперь поиск можно осуществлять не только по четырем направлениям но и по восьми, т.е. учитывать диагональные направления. В связи с этим выведены настройки стоимостей путей.
Сами алгоритмы поиска будут выглядеть следующим образом (они не сильно изменились по сравнению с предыдущей публикации):
Алгоритмы поиска на выходе предоставляют структуру ПосещенныеВершины. По ней строится путь от точки "А" до интересующей нас точки "Б". Для этого используются следующие функции:
При такой реализации на выходе получаем стек с вершинами в порядке следования. Начиная путь с точки "А" берем из стека вершину и движемся к ней, после ее достижения берем следующую, и так пока не опустошим стек.
Про то как реализовать стек можно посмотреть здесь (реализуем Стек, Очередь и Приоритетную очередь в 1С).
В алгоритмах поиска пути используется функция получения соседей поэтому приведу код для их вычислений:
Для демонстрации новых возможностей доработал обработку. Выглядит она теперь так:
Добавляйте точки "Б", перетаскивайте их, изменяйте карту, жмякайте "Старт" и наблюдайте пошагово работу выбранного алгоритма. Стрелками "Влево"(кнопка A) или "Вправо"(D) можно шагать по выполненному алгоритму.
Обработка сделана средствами платформы 1С 8.3.10 без использования внешних компонент.
ПС: для любителей автоматного программирования - обработка выполнена в стиле автоматного программирования и к ней идет спецификация, состоящая из схем связей и графов перехода (диаграмм состояний). Список литературы по автоматному программированию и конечным автоматам:
[1] - http://is.ifmo.ru/books/_book.pdf - Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб 2008.
Специальные предложения
См. также
Альтернативный способ добавления элементов и реквизитов на формы 32
1 стартмани
09.09.2019 3843 5 bmk74 0
Онлайн-интенсив "Бизнес-процессы для подготовки к экзамену 1С:Специалист по платформе" 12 декабря 2019 г. Промо
На интенсиве будут рассмотрены все теоретические вопросы, связанные с устройством механизма бизнес-процессов – это необходимо для успешной сдачи экзамена 1С:Специалист по платформе. Также, в качестве практического примера, будет решена задача, аналогичная экзаменационной.
777 рублей
Перенос документов, остатков и справочников КА 1.1 => КА 2 / УТ 11. Обновлено до КА 2.4.10.х и УТ 11.4.10.х! Промо
Более 130 компаний выполнили переход на КА 2 или УТ 11 с помощью нашей разработки! Позволяет перенести не только остатки и справочники (как типовая обработка), но и документы за нужный период времени. Предоставляем техподдержку, оперативно исправляем замечания, выпускаем обновления при выходе новых релизов программ 1С. Вы можете проверить разработку до покупки: сделаем бесплатный тестовый перенос из вашей базы КА 1.1 и предоставим доступ к базе-результату через веб-клиент!
29700 руб.
Cashback 35% при покупке 1С лицензий на счет INFOSTART.RU с 27.11 по 04.12 Промо
Оформляете заказ на 1С лицензии или конфигурации. Получаете 35% от стоимости на счет в профиле INFOSTART.RU. Выбираете сервисы и продукты на сумму кэшбэка.
Цифровая подпись Cades-BES для XML средствами 1С с помощью КриптоПро 6
1 стартмани
13.05.2019 4238 12 PythonJ 25
Перенос данных УТ 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 руб.
Программы для исполнения 54-ФЗ Промо
С 01.02.2017 контрольно-кассовая техника должна отправлять электронные версии чеков оператору фискальных данных - правила установлены в 54-ФЗ ст.2 п.2. Инфостарт предлагает подборку программ, связанных с применением 54-ФЗ, ККТ и электронных чеков.
Перенос документов и справочников ERP 2 / КА 2 / УТ 11 => БП 3.0 Промо
Перенос позволяет настроить собственный обмен данными между указанными программами, альтернативный предлагаемому фирмой 1С. Предоставляем техподдержку по всем вопросам данного обмена. Можем подключиться к вам удаленно для разбора ситуаций. Оперативно обновляем при выходе новых релизов 1С. Бесплатные обновления в течение полугода.
19700 руб.
Расширение "Курсы валют в формулах расчета динамических цен" для УНФ 1.6 5
5 стартмани
17.01.2019 6400 13 Palmer1976 4
Программы для исполнения 488-ФЗ: Маркировка товаров Промо
1 января 2019 года вступил в силу ФЗ от 25.12.2018 № 488-ФЗ о единой информационной системе маркировки товаров с использованием контрольных (идентификационных) знаков, который позволяет проследить движение товара от производителя до конечного потребителя. Инфостарт предлагает подборку программ, связанных с применением 488-ФЗ и маркировкой товаров.
Конструктор мобильного клиента Simple WMS Client: способ создать полноценный ТСД без мобильной разработки. Теперь новая версия - Simple UI (обновлено 14.11.2019) 178
5 стартмани
09.01.2019 24440 225 informa1555 174
Вакансия Автор новостных обзоров на тему 1С и бухучета, По совместительству Промо
Редакция Infostart.ru будет рада сотрудничеству с 1С-специалистом, умеющим и любящим излагать свои мысли в письменной форме. Если вы работали в IT-изданиях или имеете опыт ведения технологического блога/канала/группы, если сможете сделать обзор обработок из каталога infostart.ru/public/all/, то у вас большое преимущество.
Перенос данных БП 2.0 => УТ 11 / КА 2 / ERP 2 (перенос остатков, документов и справочников из "1С:Бухгалтерия предприятия 8", ред. 2.0 в "1С:Управление торговлей 8", ред.11 / КА 2 / ERP 2). Обновлено до УТ 11.4.10.х, КА 2.4.10.х, ERP 2.4.10.х! Промо
Перенос позволяет загрузить в УТ 11 / КА 2 / ERP 2 документы за выбранный период, справочную информацию и остатки по счетам бух. учета. Переносятся остатки денежных средств, взаиморасчетов, остатки товаров и материалов на складах. Переносятся девятнадцать основных видов документов за выбранный период и вся нормативно-справочная информация. Есть фильтр по организации. Если нужно переносить что-то дополнительно, то обычно бесплатно дорабатываю правила (перед покупкой согласуйте необходимые доработки).
29700 руб.
Обнуление остатков регистров бухгалтерии и накопления 41
2 стартмани
19.11.2018 11107 181 morozov.sv 30
Специальное предложение по 1С:Документооборот 8! Промо
Оперативно навести порядок в документообороте? Легко! Воспользуйтесь специальным предложением! Внедрение за 2 недели! Фиксированная цена и гарантия результата!
Правила обмена данными из Бухгалтерии предприятия ред. 3.0 в Управление производственным предприятием ред. 1.3 2
3 стартмани
06.11.2018 5598 байт 0
Подборка решений для взаимодействия со ФГИС «Меркурий» Промо
С 1 июля 2019 года все компании, участвующие в обороте товаров животного происхождения, должны перейти на электронную ветеринарную сертификацию (ЭВС) через ФГИС «Меркурий». Инфостарт предлагает подборку программ, связанных с этим изменением.
Подборка программ для взаимодействия с ЕГАИС Промо
ЕГАИС (Единая государственная автоматизированная информационная система) - автоматизированная система, предназначенная для государственного контроля за объёмом производства и оборота этилового спирта, алкогольной и спиртосодержащей продукции. Инфостарт рекомендует подборку проверенных решений для взаимодействия с системой.
Универсальный инструмент для переноса данных через табличный документ (УФ) 35
5 стартмани
15.10.2018 16366 96 json 19