АЛГОРИТМ ПОИСКА КРАТЧАЙШЕГО ПУТИ В РАСПРЕДЕЛЕННЫХ МИКРОСИСТЕМАХ С ПРЕДФРАКТАЛЬНОЙ ТОПОЛОГИЕЙстатья

Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 26 июня 2019 г.

Работа с статьей


[1] АЛГОРИТМ ПОИСКА КРАТЧАЙШЕГО ПУТИ В РАСПРЕДЕЛЕННЫХ МИКРОСИСТЕМАХ С ПРЕДФРАКТАЛЬНОЙ ТОПОЛОГИЕЙ / Л. А. Зинченко, В. А. Верстов, Б. С. Сорокин и др. // Известия ЮФУ. Технические науки. — 2018. — № 4. — С. 47–58. Рассмотрены особенности проектирования распределенных микросистем, которые могут быть использованы при создании Интернета вещей. Отмечено, что при решении практически важных задач задание веса ребра графа зависит от конкретного приложения. Показано, что в иерархических распределенных микросистемах вопросы обеспечения работоспособности отдельных узлов, являющих ретрансляторами информации для отдельных узлов системы, являются крайне важными. Отмечено, что при использовании распределенных микросистем в лабиринтных структурах, например, в условиях городской застройки, при использовании естественных каналов передачи информации также необходимо учитывать многолучевой характер распространения радиоволн. Для повышения вероятности сохранения работоспособности проектируемых устройств при внешних помехах предложено при синтезе топологии распределенных микросистем использовать самоподобные множества, в частности фракталы. Для одного из возможных вариантов реализации предложенного подхода рассмотрено использование предфрактальных графов, являющихся конечными аналогами фрактальных графов. Были проведены вычислительные эксперименты по исследованию временной сложности наиболее эффективных алгоритмов поиска кратчайшего пути. Анализ полученных результатов позволяет сделать вывод, что алгоритм сжатия иерархий в общем случае показывает лучшую по сравнению с другими алгоритмами производительность только для графов с небольшим количеством вершин, при этом алгоритм Дейкстры обладает лучшей асимптотической временной сложностью по сравнению с алгоритмом сжатия иерархий. Алгоритм A* показал свою асимптотическую эффективность, однако пространственная сложность алгоритма ограничивает его применение при исследовании распределенных микросистем. На основе анализа полученных экспериментальных результатов предложен алгоритм поиска кратчайшего пути, ориентированный на применение в распределенных микросистемах с предфрактальной топологией, учитывающий особенности выбранного проектного решения. Он является комбинацией алгоритма Дейкстры и алгоритма сжатия иерархий. Показано, что использование знаний позволяет снизить вычислительные затраты при поиске кратчайшего пути. Обсуждены особенности применения предложенного алгоритма при поиске пути в распределенных микросистемах с предфрактальной топологией в лабиринтных структурах. [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть