Примеры сетевых топологий


Эффективные алгоритмы для ограниченных классов - часть 3


Спустя некоторое время при известном (гамма) распределении, один из бегунов достигает конца своего ребра. В этой точке бегун останавливается, и новые бегуны устремляются вдоль ребер, исходящих из данной вершины. (Бегуны не посылаются бежать по ребрам, откуда прибыл бегун предыдущего этапа). Благодаря экспоненциальному распределению (отсутствие памяти) для времен пробега, следует, что в точке, откуда стартуют бегуны, они начинают новый этап одновременно. Короче говоря, процесс путешествия бегунов по сети является цепью Маркова с непрерывным временем. Состояние этой цепи Маркова соответствует возможному набору вершин, которые бегуны посетили и набору ребер, по которым они движутся в данный момент, а состояния поглощения соответствуют тем, что помечены t в качестве вершины адресата. Среднее время для вероятности поглощения этой цепи Маркова в точности равно длине наикратчайшего пути. Вероятность состояния поглощения может быть вычислена легко путем соответствующего упорядочения состояний цепи Маркова. Хотя время вычисления является линейным по отношению к числу состояний цепи Маркова, это число растет экспоненциально с ростом размера сети. Для сетей порядка 15-20 дуг, этот метод вполне эффективен при нахождении соответствующих решений.




Начало  Назад  Вперед