有向概率图 - 减少周期的算法？

3 回答

• 1

  我不是马尔可夫链领域的专家，虽然我认为算法可能因你遇到的那种问题而闻名，但我很难找到它们 .

  如果没有这方面的帮助，那么你可以考虑自己动手 . 我在这里看到至少两种不同的方法：

  • 模拟 .

  检查系统状态如何随着时间的推移从状态1中的系统以100％概率开始，并执行多次迭代，其中应用转换概率来计算在执行步骤后获得的状态的概率 . 如果可以从每个节点到达（非零概率）至少一个最终（"absorbing"）节点，那么在足够的步骤中，系统处于除最终状态之外的任何其他概率将逐渐减小为零 . 您可以将系统在最终状态S结束的概率估计为在n步之后处于状态S的概率，其中该估计中的误差的上限由系统处于非最终状态的概率给出经过n步 .

  实际上，这与计算 Tr n相同，其中 Tr 是您的转移概率矩阵，对于所有最终状态，以100％概率自我边缘进行扩充 .

  • 精确计算 .

  考虑一个图G，如您所描述的 . 给定两个顶点i和f，使得从i到f至少有一条路径，并且f除了自边之外没有外边缘，我们可以将路径从i到f划分为以它们的次数为特征的类 . 在到达f之前重温我 . 可能存在无数个这样的类，我将指定 C if（n），其中n表示 C if（n）中的路径重新访问节点i的次数 . 特别是， C ii（0）包含G中包含i（ clarification ：以及其他路径）的所有简单循环 .

  假定系统从节点i开始遍历图G，则在节点f处结束的总概率由下式给出

  Pr（f | i，G）= Pr（ C if（0）| G）Pr（ C if（1）| G）Pr（ C if（2）| G）...

  现在观察一下，如果n> 0，则 C if（n）中的每个路径都具有两个路径 c 和 t 的并集形式，其中 c 属于 C ii（n-1）， t 属于 C if（0） . 也就是说， c 是一个从节点i开始并在节点i结束的路径，在它之间经过i-1次，而 t 是从i到f再次不通过i的路径 . 我们可以用它来重写我们的概率公式：

  Pr（f | i，G）= Pr（ C if（0）| G）Pr（ C ii（0）| G）* Pr（ C if（0）| G）Pr（ C ii（1）| G） * Pr（ C if（0）| G）...

  但请注意 C 中的每个路径ii（n）是属于 C ii（0）的n 1个路径的组合 . 由此得出Pr（ C ii（n）| G）= Pr（ C ii（0）| G）n 1，所以我们得到

  Pr（f | i）= Pr（ C if（0）| G）Pr（ C ii（0）| G）* Pr（ C if（0）| G）Pr（ C ii（0）| G）2 * Pr（ C if（0）| G）...

  现在，一个小代数给了我们

  Pr（f | i，G） - Pr（ C if（0）| G）= Pr（ C ii（0）| G）* Pr（f | i，G）

  ，我们可以解决Pr（f | i，G）得到

  Pr（f | i，G）= Pr（ C if（0）| G）/（1 - Pr（ C ii（0）| G））

  因此，我们已经将问题减少到一个不返回起始节点的路径，除了可能作为它们的结束节点 . 这些并不排除具有不包含起始节点的循环的路径，但是我们仍然可以根据原始图的子图上计算的原始问题的几个实例来重写此问题 .

  特别是，让 S （i，G）成为图G中顶点i的后继集合 - 也就是说，顶点集合s使得在G中存在从i到s的边缘，并且让X（G， i）是通过去除从i开始的所有边形成的G的子图 . 此外，设p是与G中的边（i，s）相关的概率 .

  Pr（ C if（0）| G）= pis * Pr（f | s，X（G，i）） S （i，G）中s的总和

  换句话说，从i到G而不重新访问i之间的f的概率是i的所有后继者的总和，其中i的一步到达s的概率乘以从s到G的f的概率没有遍历从i出站的任何边 . 这适用于G中的所有f，包括i .

  现在观察 S （i，G）并且所有的pis都是已知的，并且计算Pr（f | s，X（G，i））的问题是原始问题的一个新的，严格更小的实例 . 因此，可以递归地执行该计算，并且保证这种递归终止 . 如果您的图形很复杂，可能需要很长时间，看起来这种递归方法的简单实现会在节点数量上呈指数级扩展 . 有一些方法可以加快计算速度以换取更高的内存使用量（即memoization） .

  ---

  还有其他可能性 . 例如，我怀疑可能存在一种自下而上的动态编程方法来解决方案，但我无法说服自己图中的循环不存在不可克服的问题 .

  回复于 2024-04-30T05:56:55+08:00
• 1

  Problem Clarification

  输入数据是m行n列概率的集合，基本上是m乘n矩阵，其中m = n =有向图上的顶点数 . 行是边缘起点，列是边缘目的地 . 在提到问题中的循环的基础上，我们将图表是循环的，图中至少存在一个循环 .

  设's define the starting vertex as s. Let'也将终端顶点定义为没有出现边的顶点，并将它们的集合定义为大小为z的集合T.因此，我们在T中具有从s到顶点的z组路由，并且由于循环1，集合大小可以是无限的 . 在这种情况下，不能断定将以任意大量的步骤到达终端顶点 .

  在输入数据中，与不在T中的顶点对应的行的概率被归一化为总计1.0 . 我们将假设Markov属性，即每个顶点的概率不随时间变化 . 这排除了使用概率来优先化图搜索2中的路线 .

  有限的数学文本有时会将类似于这个问题的示例问题命名为Drunken Random Walks，以强调步行者忘记过去的事实，指的是马尔可夫链的无记忆性质 .

  Applying Probability to Routes

  到达终端顶点的概率可以表示为无穷大的乘积和 .

  Pt = lim s - >∞ΣΠPi，j，其中s是阶跃指数，t是终端顶点索引，i∈[1 .. m]和j∈[1 .. n]

  Reduction

  当两个或多个周期相交（共享一个或多个顶点）时，分析会因涉及它们的无限模式集而变得复杂 . 在经过一些分析和回顾之后，看来，利用今天的数学工具得到一组精确的终端顶点到达概率，最好用一个收敛算法来完成 .

  可以进行一些初步减少 .

  • 第一个考虑因素是枚举目标顶点，这很容易，因为相应的行的概率为零 .

  • 下一个考虑因素是为了区分任何进一步的减少与学术文献所称的不可约的子图 . 下面的深度优先算法记住在构建潜在路线时已经访问了哪些顶点，因此可以容易地对其进行改装以识别循环中涉及哪些顶点 . 但是，建议使用现有经过良好测试的，经过同行评审的图形库来识别子图并将其表征为不可简化的 .

  图的不可缩减部分的数学减少可能是合理的，也可能是不合理的 . 考虑在图中起始顶点A和唯一终止顶点B表示为{A-> C，C-> A，A-> D，D-> A，C-> D，D-> C，C-> B， D-> B} .

  虽然可以将图形减少到没有通过顶点A的循环的概率关系，但是如果不修改退出C和D的顶点的概率或者允许退出C和D的边缘概率的总和更小，则不能去除顶点A以进一步减少比1.0 .

  Convergent Breadth First Traversal

  忽略重访并允许循环的广度优先遍历可以迭代步骤索引s，而不是某些固定的smax，而是收敛趋势中的某个足够稳定和准确的点 . 如果循环重叠在由单个循环引起的更简单的周期中产生分叉，则特别需要这种方法 .

  ΣPsΔs .

  为了在s增加时 Build 合理的收敛，必须通过查看所有终端顶点处的结果的长期趋势来确定期望的准确度作为完成收敛算法的标准和用于测量精度的度量 . 提供一种标准，其中终端顶点概率的总和与趋势收敛度量一起接近于一，作为健全性检查和准确性标准 . 实际上，可能需要四个收敛标准3 .

  • 每个终端顶点概率趋势收敛增量

  • 平均概率趋势收敛增量

  • 统一总概率的收敛性

  • 总步数（由于实际计算原因，为了上限）

  即使超过这四个，程序也可能需要包含一个中断陷阱，允许在长时间等待之后写入和随后检查输出，而不满足上述所有四个标准 .

  An Example Cycle Resistant Depth First Algorithm

  有比以下算法更有效的算法，但它是相当容易理解的，它在没有C-Wall的警告的情况下编译，并且它为所有有限和合法的有向图以及起始和目标顶点产生所需的输出4.很容易使用addEdge方法5以问题中给出的形式加载矩阵 .

  #include <iostream>
  #include <list>
  
  class DirectedGraph {
  
      private:
          int miNodes;
          std::list<int> * mnpEdges;
          bool * mpVisitedFlags;
  
      private:
          void initAlreadyVisited() {
              for (int i = 0; i < miNodes; ++ i)
                  mpVisitedFlags[i] = false;
          }
  
          void recurse(int iCurrent, int iDestination,
                 int route[], int index,
                 std::list<std::list<int> *> * pnai) {
  
              mpVisitedFlags[iCurrent] = true;
              route[index ++] = iCurrent;
  
              if (iCurrent == iDestination) {
                  auto pni = new std::list<int>;
                  for (int i = 0; i < index; ++ i)
                      pni->push_back(route[i]);
                  pnai->push_back(pni);
  
              } else {
                  auto it = mnpEdges[iCurrent].begin();
                  auto itBeyond = mnpEdges[iCurrent].end();
                  while (it != itBeyond) {
                      if (! mpVisitedFlags[* it])
                          recurse(* it, iDestination,
                                  route, index, pnai);
                      ++ it;
                  }
              }
  
              -- index;
              mpVisitedFlags[iCurrent] = false;
          } 
  
      public:
          DirectedGraph(int iNodes) {
              miNodes = iNodes;
              mnpEdges = new std::list<int>[iNodes];
              mpVisitedFlags = new bool[iNodes];
          }
  
          ~DirectedGraph() {
              delete mpVisitedFlags;
          }
  
          void addEdge(int u, int v) {
              mnpEdges[u].push_back(v);
          }
  
          std::list<std::list<int> *> * findRoutes(int iStart,
                  int iDestination) {
              initAlreadyVisited();
              auto route = new int[miNodes];
              auto pnpi = new std::list<std::list<int> *>();
              recurse(iStart, iDestination, route, 0, pnpi);
              delete route;
              return pnpi;
          }
  };
  
  int main() {
  
      DirectedGraph dg(5);
  
      dg.addEdge(0, 1);
      dg.addEdge(0, 2);
      dg.addEdge(0, 3);
      dg.addEdge(1, 3);
      dg.addEdge(1, 4);
      dg.addEdge(2, 0);
      dg.addEdge(2, 1);
      dg.addEdge(4, 1);
      dg.addEdge(4, 3);
  
      int startingNode = 2;
      int destinationNode = 3;
  
      auto pnai = dg.findRoutes(startingNode, destinationNode);
  
      std::cout
              << "Unique routes from "
              << startingNode
              << " to "
              << destinationNode
              << std::endl
              << std::endl;
  
      bool bFirst;
      std::list<int> * pi;
      auto it = pnai->begin();
      auto itBeyond = pnai->end();
      std::list<int>::iterator itInner;
      std::list<int>::iterator itInnerBeyond;
      while (it != itBeyond) {
          bFirst = true;
          pi = * it ++;
          itInner = pi->begin();
          itInnerBeyond = pi->end();
          while (itInner != itInnerBeyond) {
              if (bFirst)
                  bFirst = false;
              else
                  std::cout << ' ';
              std::cout << (* itInner ++);
          }
          std::cout << std::endl;
          delete pi;
      }
  
      delete pnai;
  
      return 0;
  }
  

  ---

  Notes

  [1]有向图算法中处理不当的周期将在无限循环中挂起 . （注意一些简单的情况，其中有向图的路径从A到B的数量表示为{A-> B，B-> A}是无穷大 . ）

  [2]概率有时用于降低搜索的CPU周期成本 . 在该策略中，概率是优先级队列中元规则的输入值，以减少计算挑战非常繁琐的搜索（即使对于计算机） . 生产环境 系统中的早期文献称为无指导大搜索组合爆炸的指数特征 .

  [3]实际上可能需要检测每个顶点的广度第一概率趋势，并根据四个标准指定令人满意的收敛

  • Δ（ΣΠP）t <=Δmax∀t

  • Σt=0TΔ（ΣΠP）t / T <=Δave

  • |ΣΣΠP - 1 | <= umax，其中u是最终概率之和的最大允许偏差

  • s <Smax

  [4]如果有足够的计算资源可用于支持数据结构，并且有足够的时间来获得给定计算系统速度的答案 .

  [5]您可以使用嵌套的两个循环来加载带有输入数据的DirectedGraph dg（7），以迭代问题中枚举的行和列 . 内环的主体只是条件边缘加法 .

  if (prob != 0) dg.addEdge(i, j);
  

  变量prob是 P m，n . 路径存在仅涉及零/非零状态 .

  回复于 2024-04-30T05:56:55+08:00
• 3

  我理解为以下问题：

  给定每个节点上的初始分布作为向量b和矩阵A，其存储在每个时间步骤中从节点i跳到节点j的概率，有点类似于邻接矩阵 .

  然后，在一个时间步之后的分布b_1是A x b . 经过两个时间步后分布b_2是A x b_1 . 同样，分布b_n是A ^ n×b .

  对于b_infinite的近似值，我们可以执行以下操作：

  Vector final_probability(Matrix A, Vector b,
      Function Vector x Vector -> Scalar distance, Scalar threshold){
      b_old = b
      b_current = A x b
      while(distance(b_old,b_current) < threshold){
          b_old = b_current
          b_current = A x b_current
      }
      return b_current
  }
  

  （我使用数学变量名来方便）

  换句话说，我们假设分布序列在给定阈值之后很好地收敛 . 可能不成立，但通常会奏效 .

  您可能希望为此添加最大量的迭代 .

  欧氏距离应该与距离一样好 .

  （这使用了Markov Chain的概念，但更像是一种实用的解决方案）

  回复于 2024-04-30T05:56:55+08:00