python - 通用数学方程

Question

我有一个由顶点和弧组成的网络（图），如下所示。

我想要的是：

A 希望从第 1 天到第 m 天在网络中进行一组随机游走，以便在该组随机游走中的至少一个随机游走中访问所有顶点。

我在 while 循环中执行此操作。

问题：

最小的可能实例（网络）在 28 天内由三种类型的顶点（白天、晚上和夜晚）组成。

这导致 while 循环永远运行。这是因为随机游走最有可能在夜间结束，并且包含顶点 (n-2) 的随机游走的概率是 (1/3^28 = 0,00000000000000131%)。

随机游走的起点是在可能的顶点/弧中均匀随机地选择下一个顶点/弧。在我的网络中，这将导致以下概率：

[(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)]

Where each tuple represents with which probabilities the next vertex most be chosen when the last vertex chosen was respectively day, evening and 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)]

总结一下：

矩阵中的第一个向量（在 list1 中）表示从顶点类型 1 到分别顶点类型 1、类型 2 和类型 3 的边数。同样，向量 2 表示从顶点类型 2 到分别向量类型 1 的边数, 类型 2 和类型 3 并且与向量 3 类似。

list2 表示当最后选择的顶点分别为类型 1、类型 2 和类型 3 时，随机游走中的下一个顶点将分别被选择为顶点类型 1、类型 2 和类型 3 的概率。

需要帮助：

我想基于 [[27,27,27], [0,27,27] 获得类似于 [(80, 15, 5), (0, 80, 20), (0, 0, 100)] 的东西, [0,0,27]]。

我怎么能在数学上做到这一点？

（它不一定给出完全相同的值，但与 list2 中的大小比率相同（因为它们只是基于逻辑））

我认为它可以以某种方式以通用的方式在数学上表达，以便它适用于不一定具有相同图形结构的更复杂的网络。

奖励信息： 另一个例子，我想找到一组概率可能如下，这是第二个最不复杂的扩展 [[27,27,27,27],[0,27,27,0],[0 ,0,27,0],[27,27,27,27]]。

更新： 我被告知，我可能可以模拟它，但无法弄清楚如何在实践中做到这一点。然后我应该使用哪些概率？以及如何使用此模拟来获得最佳百分比？

标签： pythonmathlogic

Answer 1

这个问题有点不明确。只有将 100% 分配给 1，将 0 分配给其余部分，概率才能保持不变。根据您偏离 100% 的程度，结果会偏离更多。

每天的概率可以计算为矩阵乘法。对于示例情况，第一天这个乘法看起来像：

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

继续与相同的矩阵相乘得到下一天的概率。

下面的代码绘制了概率的演变。为了稍微简化参数的数量，代码首先将 80% 的概率分配给一个，然后将另外 20% 的 80% 分配给第二个。

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]]