Существуют ли какие-нибудь алгоритмы для вычисления "транспортной нагрузки" в рёбрах (или узлах) в циклическом графе?

objMihail, 415 просмотров

Т.е. есть направленный граф, веса рёбер равны 1. У любого узла может быть любое число входящих и выходящих рёбер. Задача заключается в том, что какому-то узлу даётся "импульс" (равный единице) и надо просчитать как он распространился на другие узлы (какие там примет значения).

Если граф ациклический, то всё просто. Например, если от узла A идут связи к B и C, то если сообщить узлу A импульс = 1, то в B и C он будет равен по 0,5 в каждом. Если потом от B и C идут связи к D, то в D импульс снова равен единице. И т.д. и т.п.

А вот в случае с циклами возможно столько всяких разных ситуаций, что мозги закипают. Есть ли какой-нибудь готовый алгоритм для такой задачи или как она называется?

Ответы:

Арчи0007

Три хаха, а на мат форум сходить?! Можете сходить на форум Новосибирского универа, там наверняка найдётся чел который вам что то посоветует. НО ТАМ ПРАВИЛО, было по крайней мере, показать своё решение.

Андрей_2009

Ваша задача -- скорее, вероятностный граф, а не транспортный граф. Возможно, решение есть в книге "Кормен. Алгоритмы и структуры данных" (точно уже не помню).
Возможно решается так (но не уверен):
1) Нормируем веса рёбер. Составляем матрицу переходов A (её элемент a[i][j] = нормированный вес ребра, связывающего вершину i с j, или 0, если такого ребра нет). Составляем вектор первоначального состояния V0 (у него все нули, кроме единицы у той вершины, которой даём испульс). Каждый раз, когда мы умножаем вектор на матрицу (Vi * A = V[i+1]), мы получаем один шаг распространения. То есть нам нужно бесконечно раз умножить наш вектор на матрицу. Чтобы каждый раз двигаться не по одному шагу, а быстрее, возводим нашу матрицу в квадрат, потом ещё раз и т.д. (получим A^2, A^4, A^8) и после необходимого кол-ва умножаем на вектор.
2) Исключением вершин. Допустим, из А идёт ребро в B с весом 0.8, а из B в C с весом 0.5. Исключаем B и получаем ребро из A в C с весом 0.4 .

Без имени

посмотрите на www.reshmat.ru, решение непосредственно на сайте с подробными комментариями.

14 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

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

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.