ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2017 г.)
2-летний импакт-фактор РИНЦ: 0,500
2-летний импакт-фактор РИНЦ без самоцитирования: 0,405
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,817
5-летний импакт-фактор РИНЦ: 0,319
5-летний импакт-фактор РИНЦ без самоцитирования: 0,264
Суммарное число цитирований журнала в РИНЦ: 6012
Пятилетний индекс Херфиндаля по цитирующим журналам: 404
Индекс Херфиндаля по организациям авторов: 338
Десятилетний индекс Хирша: 17
Место в общем рейтинге SCIENCE INDEX за 2017 год: 527
Место в рейтинге SCIENCE INDEX за 2017 год по тематике "Автоматика. Вычислительная техника": 16

Больше данных по публикационной активности нашего журнале за 2008-2017 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2018

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

01.08.2018

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

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

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

Основная проблема графов с отрицательными весами ребер – так называемые отрицательные циклы, в которых сумма весов ребер отрицательна. Исследование данных циклов представляет собой отдельную задачу, для решения которой применяется алгоритм Флойда–Уоршелла. Исследованию их в динамических графах посвящена работа.

Подробное описание дается в статье «Точное решение задачи поиска минимального ациклического пути во взвешенных графах, содержащих ребра отрицательного веса», авторы: Н.И. Гданский (Московский политехнический университет, г. Москва), Н.Л. Куликова (Национальный исследовательский университет «Московский энергетический институт», г. Москва), Е.В. Чумакова (Московский авиационный институт (национальный исследовательский университет), г. Москва).