Для больших r и b вы можете использовать метод, называемый интеграцией Монте-Карло, см., Например, интеграцию Монте-Карло в Википедии (и / или главу 3.1.2 SICP) для вычислениясумма.Для малых r и b и значительно различных вероятностей отказа узла p[i] точный метод является лучшим.Точное определение small и large будет зависеть от нескольких факторов, и его лучше всего опробовать экспериментально.
Конкретный пример кода : Этоэто очень простой пример кода (на Python), демонстрирующий, как такая процедура может работать:
def montecarlo(p, rb, N):
"""Corresponds to the binomial coefficient formula."""
import random
succ = 0
# Run N samples
for i in xrange(N):
# Generate a single test case
alivenum = 0
for j in xrange(rb):
if random.random()<p: alivenum += 1
# If the test case succeeds, increase succ
if alivenum >= b: succ += 1
# The final result is the number of successful cases/number of total cases
# (I.e., a probability between 0 and 1)
return float(succ)/N
Функция соответствует биномиальному тестовому сценарию и запускает N тесты, проверяя, если b выводит узлыr*b узлы живы с вероятностью отказа p.Несколько экспериментов убедят вас, что вам нужны значения N в диапазоне тысяч образцов, прежде чем вы сможете получить какие-либо разумные результаты, но в принципе сложность составляет O(N*r*b).Точность результата масштабируется как sqrt(N), т. Е. Чтобы повысить точность в два раза, нужно увеличить N в четыре раза.Для достаточно больших r*b этот метод будет явно лучше.
Расширение аппроксимации : вам, очевидно, нужно спроектировать тестовый пример такой, чтобы он учитывал все свойства системы.Вы предложили несколько расширений, некоторые из которых могут быть легко реализованы, а другие - нет.Позвольте дать вам пару советов:
1) В случае отличного, но некоррелированного p[i] изменения приведенного выше кода минимальны: в заголовке функции вы передаете массив вместо одного плавающего числаp и вы замените строку if random.random()<p: alivenum += 1 на
if random.random()<p[j]: alivenum += 1
2) В случае коррелированного p[i] вам потребуется дополнительная информация о системе.Ситуация, на которую я ссылался в моем комментарии, могла быть такой:
A--B--C
| |
D E
|
F--G--H
|
J
В этом случае A может быть «корневым узлом», а сбой узла D может означать автоматическийотказ со 100% вероятностью узлов F, G, H и J;в то время как отказ узла F автоматически приведет к отключению G, H и J и т. д. По крайней мере, это был тот случай, о котором я говорил в своем комментарии (это правдоподобная интерпретация, поскольку вы говорите о дереве).структура вероятностей в исходном вопросе).В такой ситуации вам потребуется изменить код, который p относится к древовидной структуре, а for j in ... пересекает дерево, пропуская нижние ветви текущего узла, как только тест не пройден.Конечно, итоговый тест все равно будет alivenum >= b, как и раньше.
3) Этот подход потерпит неудачу, если сеть представляет собой циклический граф, который не может быть представлен древовидной структурой.В таком случае вам нужно сначала создать узлы графа, которые либо мертвы, либо живы, а затем запустить алгоритм маршрутизации на графе для подсчета количества уникальных, достижимых узлов.Это не увеличит временную сложность алгоритма, но, очевидно, сложность кода.
4) Зависимость от времени является нетривиальной, но возможной модификацией, если вы знаете mtbf / r (среднее времямежду отказами / ремонтами), поскольку это может дать вам вероятности p древовидной структуры или некоррелированной линейной p[i] в виде суммы экспонент.Затем вам придется запускать процедуру MC в разное время с соответствующими результатами для p.
5) Если у вас просто есть файлы журналов (как указано в вашем последнем абзаце), это потребует существенногомодификация подхода, который выходит за рамки того, что я могу сделать на этой доске.Лог-файлы должны быть достаточно тщательными, чтобы позволить реконструировать модель для графа сети (и, следовательно, графа p), а также отдельных значений всех узлов p.В противном случае точность была бы ненадежной.Эти лог-файлы также должны быть значительно длиннее, чем временные масштабы сбоев и ремонтов, предположения, которые могут быть нереальными в реальных сетях.