Automation of technological and business processes

ISSN-print: 2312-3125
ISSN-online: 2312-931X
ISO: 26324:2012
Архiви

Электрическая модель с идеальными элементами для поиска кратчайшего пути на взвешенном ориентированном графе

##plugins.themes.bootstrap3.article.main##

В. Ю. Гнатенко
П. В. Ступень
К. В. Дікусар
Е. І. Шутєєв

Анотація

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

В задачах небольшой размерности можно использовать аналоговые электрические модели. Однако для больших графов аналоговые модели становятся весьма громоздкими из-за необходимости включения в каждую цепь изолированного источника электрической энергии, а точность решения низкой из-за не идеальности характеристик элементов.

В данной статье рассматривается развитие модели представления взвешенного ориентированного графа без использования структурной матрицы или каких-либо других топологических матриц. Вместо этого предлагается формировать и обрабатывать в процессе анализа список ветвей с присущими им характеристиками и параметрами.

Целью работы является обоснование электрической модели для поиска кратчайшего пути во взвешенном ориентированном графе, представление алгоритма для реализации и иллюстрации эффективности метода.

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

Ключові слова:
Для цієї мови відсутні ключові слова

##plugins.themes.bootstrap3.article.details##

Як цитувати
Гнатенко, В., Ступень, П., Дікусар, К., & Шутєєв, Е. (2018). Электрическая модель с идеальными элементами для поиска кратчайшего пути на взвешенном ориентированном графе. Automation of Technological and Business Processes, 10(2). https://doi.org/10.15673/atbp.v10i2.976
Розділ
МЕТОДИ ТА АЛГОРИТМИ ЕФЕКТИВНОГО УПРАВЛІННЯ ОБ‘ЭКТАМИ

Посилання

1. Хмельник С.И. Электрические цепи постоянного тока для моделирования и управления. Алгоритмы и аппаратура. Израиль; Россия, 2006. 177 с.
2. Деннис Дж. Б. Математическое программирование и электрические цепи. М.: Изд-во иностр. лит., 1961. 214 с.
3. Шутеев Э. И. Моделирование нелинейных электрических цепей постоянного тока для решения задачи поиска кратчайшего пути / Э.И. Шутеев, Д.О. Белокопытов, Д.Ф. Димитров Тр. Одес. политехн. ун-та. 2009. Вып 2(32). С. 88-91 .
4. Атабеков Г.И. Основы теории цепей. СПб.: Издательство «Лань», 2009. 432 с.
5. Шеин А.Б., Лазарева Н.М. Методы проектирования электронных устройств. М.: Инфра-Инженерия, 2011. 456 с.