Портал психологических изданий PsyJournals.ru
Каталог изданий 120Рубрики 53Авторы 9402Новости 1855Ключевые слова 5095 Правила публикацииВебинарыRSS RSS

РИНЦ

0,727 — двухлетний импакт-фактор

Моделирование и анализ данных

Издатель: Московский государственный психолого-педагогический университет

ISSN (печатная версия): 2219-3758

ISSN (online): 2311-9454

DOI: https://doi.org/10.17759/mda

Лицензия: CC BY-NC 4.0

Издается с 2011 года

Периодичность: 4 номера в год

Язык журнала: русский

Доступ к электронным архивам: открытый

 

Практическая реализация алгоритма декомпозиции путей ориентированного графа 8

|

Золотарев И.А.
студент магистратуры, Московский авиационный институт (НИУ МАИ), Москва, Россия
ORCID: https://orcid.org/0000-0002-6437-2212
e-mail: yngvar.antonsson@gmail.com

Рассказова В.А.
кандидат физико-математических наук, доцент кафедры 804 «Теория вероятностей и компьютерное моделирование», Московский авиационный институт (НИУ МАИ), Москва, Россия
ORCID: https://orcid.org/0000-0003-4943-3133
e-mail: varvara.rasskazova@mail.ru

Аннотация

Работа направлена на прояснение некоторых особенностей программной реализации алгоритма декомпозиции путей ориентированного графа. Разобраны алгоритмы для формирования таблицы M для декомпозиции множества путей, сортировки таблицы M по полю NΣ и расчета балансов. На основе данных алгоритмов и исходного алгоритма декомпозиции путей ориентированного графа разработан комплекс программ на языке программирования Python. Проведены расчеты для случайного графа размерности 100 вершин и приводится время работы предложенного алгоритма. Полученные результаты могут быть использованы при решении задачи организации грузовых железнодорожных перевозок на этапе назначения и перемещения локомотивов. Научная и практическая новизна работы заключается в существенном снижении размерности исходной задачи, что особенно важно в условиях транспортных сетей сложной топологии.

Ссылка для цитирования

Фрагмент статьи

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

Литература
  1. Гайнанов Д.Н., Коныгин А.В., Рассказова В.А. Моделирование грузовых железнодорожных перевозок методами теории графов и комбинаторной оптимизации // Автоматика и телемеханика. 2016. № 11. С. 60–79.
  2. Гайнанов Д.Н., Кибзун А.И., Рассказова В.А. Теоретико-графовый алгоритм решения задачи о назначении и перемещении локомотивов // Вестник компьютерных и информационных технологий. 2017. № 5. С. 51–56.
  3. Гайнанов Д.Н., Кибзун А.И., Рассказова В.А. Задача о декомпозиции множества путей ориентированного графа и ее приложение // Автоматика и телемеханика. 2018. № 12. С. 142–166.
 
О проекте PsyJournals.ru

© 2007–2021 Портал психологических изданий PsyJournals.ru  Все права защищены

Свидетельство регистрации СМИ Эл № ФС77-66447 от 14 июля 2016 г.

Издатель: ФГБОУ ВО МГППУ

Creative Commons License Репозиторий открытого доступа     Рейтинг репозиториев Webometrics

Яндекс.Метрика