Generi c математическое уравнение

Question

У меня есть сеть (график), состоящая из вершин и дуг, как показано ниже.

Что я хочу:

Желание совершить набор случайных блужданий по сети со дня 1 до дня m таким образом, чтобы все вершины посещались как минимум за одно случайное блуждание в наборе случайных блужданий.

I сделать это через некоторое время l oop.

Проблема:

Наименьший возможный экземпляр (сеть) состоит из трех типов вершин (день, вечер и ночь) в течение 28 дней.

Что приводит к тому, что l oop работает вечно. Это связано с тем, что случайное блуждание, скорее всего, закончится в ночном случае, и вероятность случайного блуждания, состоящего из вершины (n-2), равна (1/3 ^ 28 = 0,00000000000000131%).

Отправной точкой в ​​случайном блуждании является то, что следующая вершина / ar c выбирается равномерно случайной среди возможных вершин / дуг. В моей сети это привело бы к следующим вероятностям:

[(1/3, 1/3, 1/3), (0, 1/2, 1/2), (0, 0, 1)]
#Equivalent to
[(33, 33, 33), (0, 50, 50), (0, 0, 100)]
#[(day),(evening),(night)]

Где каждый кортеж представляет, с какими вероятностями следующая вершина больше всего будет выбрана, когда последняя выбранная вершина была соответственно днем, вечером и ночью.

Решение:

Решение, которое я нашел, состояло в том, чтобы изменить вероятности [(33, 33, 33), (0, 50, 50), (0, 0, 100 )] к fx [(80, 15, 5), (0, 80, 20), (0, 0, 100)].

Я бы обусловил это исходя из количества дуг от каждого типа вершина для каждого типа вершины.

#list1
[[27,27,27], [0,27,27], [0,0,27]]
#list2
[(80, 15, 5), (0, 80, 20), (0, 0, 100)]

Суммируя:

Первый вектор в матрице (в списке 1) представляет количество ребер от типа вершины 1 до соответственно типа вершины. 1, тип 2 и тип 3. Аналогично, вектор 2 представляет число ребер от вершины типа 2 до соответственно вектора типа 1, типа 2 и типа 3 и аналогично с вектором 3.

list2 представляет, с какой вероятностью следующая вершина в случайном блуждании будет выбрана соответственно для вершины типа 1 введите 2 и 3, когда последняя выбранная вершина была соответственно типа 1, типа 2 и типа 3.

Требуется помощь:

Я хочу получить нечто подобное к [(80, 15, 5), (0, 80, 20), (0, 0, 100)] на основе [[27,27,27], [0,27,27], [0,0, 27]].

Как я могу математически сделать это?

(Это не обязательно должно давать точно такие же значения, но в том же соотношении размеров, что и в list2 (так как они основаны только на логике) c))

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

Информация о бонусе: Другим примером, где я хочу найти набор вероятностей, может быть следующий, который является вторым наименее сложным расширением [[27,27,27,27], [0,27,27, 0], [0,0,27,0], [27,27,27,27]].

Обновление: Мне подсказали, что, возможно, я могу смоделировать это, но не могу понять, как это сделать на практике. Какие вероятности я должен тогда использовать? и как я могу использовать эту симуляцию, чтобы получить наилучшие проценты?

Answer 1

Проблема несколько нечеткая. Только при присвоении 100% одному и 0 остальным вероятности могут оставаться неизменными. В зависимости от того, насколько вы отклоняетесь от 100%, результат будет отклоняться больше.

Вероятности для каждого дня можно рассчитать как матричное умножение. Для примера, в первый день это умножение выглядит следующим образом:

  [1/3]   [ 0.80 0.15 0.05 ]
  [1/3] · [ 0    0.80 0.20 ]
  [1/3]   [ 0    0    1    ]

Продолжение умножения с той же матрицей дает вероятности для следующего дня.

Приведенный ниже код отображает эволюцию вероятности. Чтобы немного упростить количество параметров, код начинается с присвоения вероятности 80% одному, а затем 80% других 20% второму.

from matplotlib import pyplot as plt
from matplotlib import ticker
import numpy as np

N = 29
x0 = np.array([1, 1, 1])
x0 = x0 / x0.sum() # starting probabilites, suppose all equal; make them sum to 1
a = 80 / 100
b = (1 - a) * a
c = a
m = np.array([(a, b, 1-a-b), (0, c, 1-c), (0, 0, 1)])
# m = m / m.sum(axis=1, keepdims=True)  # normalize such that rows sum to 1

x = np.zeros((N, len(x0)))
x[0,:] = x0
for i in range(N-1):
    x[i+1, :] = np.matmul(x[i], m)

labels = ['day', 'evening', 'night']
ind = np.arange(N)
for i, lab in enumerate(labels):
    plt.plot(ind, x[:,i], label=lab, marker='.', ls='-')
plt.xticks(ind)
plt.xlabel('day')
plt.gca().yaxis.set_major_formatter(ticker.PercentFormatter(1))
plt.title(f'Highest weight for going to next day: {a*100:.1f} %')
plt.legend()

Участок с наибольшей вероятностью 80%:

Участок с наибольшей вероятностью 99%:

Только при 100% вероятности остаются постоянными до 33,3% каждая.

Вот как будет выглядеть другой пример с данными весами:

x0 = np.array([1, 1, 1, 1])
x0 = x0 / x0.sum()  # all values sum to 1
m = np.array([[27, 27, 27, 27], [0, 27, 27, 0], [0, 0, 27, 0], [27, 27, 27, 27]])
m = m / m.sum(axis=1, keepdims=True)  # normalize such that rows sum to 1
labels = ['A', 'B', 'C', 'D']

В качестве вероятностей для A и D всегда равны, кривые совпадают.

Опять-таки, оптимальным решением является присвоение веса 0 узлам, которые уже имеют слишком много входящих стрелок:

[[50, 0, 0, 50], [0, 100, 0, 0], [0, 0, 100, 0], [50, 0, 0, 50]]