6

我有一个有限的无向图，其中一个节点被标记为“开始”，另一个被标记为“目标”。

一个代理最初被放置在起始节点，它随机地在图形中导航，即在每一步它随机均匀地选择一个邻居节点并移动到它。当它到达目标节点时，它会停止。

我正在寻找一种算法，该算法为每个节点提供有关代理访问它的概率的指示，同时从起点到目标。谢谢你。

4

1 回答 1

12

与图表的情况一样，只需了解描述问题的适当方式即可。

编写图的一种方法是作为邻接矩阵。如果你的图 G = (V, E) 有 |V| 节点（其中 |V| 是顶点的数量），这个矩阵将是 |V| x |V|。如果一对顶点之间存在边，则将邻接矩阵中的项设置为 1，如果不存在则设置为 0。

对此的自然扩展是加权图。在这里，邻接矩阵不是 0 或 1，而是有一些权重的概念。

在您描述的情况下，您有一个加权图，其中权重是从一个节点转换到另一个节点的概率。这种类型的矩阵有一个特殊的名称，它是一个随机矩阵。根据您排列矩阵的方式，该矩阵将分别具有总和为 1 的行或列，右侧和左侧随机矩阵。

随机矩阵和图之间的链接之一是马尔可夫链。在马尔可夫链文献中，您需要的关键是一个转换矩阵（权重等于一个时间步后转换概率的邻接矩阵）。让我们称转换矩阵P。

计算出在 k 个时间步之后从一种状态转换到另一种状态的概率由P ^k 给出。如果你有一个已知的源状态 i，那么P ^k的第 i 行会给你转换到任何其他状态的概率。这可以让您估计短期内处于给定状态的概率

根据您的源图，P ^k 可能达到稳态分布 - 也就是说，对于某个 k 值，P ^k = P ^(k+1)。这使您可以估计长期处于给定状态的概率

顺便说一句，在你做任何这些之前，你应该能够查看你的图表，并说出在某个时间处于给定状态的概率是多少。

  1. 如果您的图表具有不相交的组件，则位于您未开始的组件中的概率为零。
  2. 如果您的图表有一些正在吸收的状态，也就是说，一旦您输入了某些状态（或状态组），它们就不可避免，那么您需要考虑这一点。如果您的图形是树状的，则可能会发生这种情况。
于 2013-03-20T13:00:05.437 回答