我想在有向图上的两个顶点之间找到一条低成本路径，其中每条边的成本都相同。算法的易实现性和执行时间非常重要，所以如果算法更简单、更快，我愿意牺牲一个接近最优的最优解。
边缘可以被障碍物阻挡。一条边被阻塞的概率是事先已知的。阻塞是相互独立的。当到达边缘头部的顶点时，发现边缘未被阻塞或被阻塞。
我的问题类似于加拿大旅行者问题，但我的理解是随机规划问题的解决方案相对难以实现，并且寻找最优策略所花费的时间可能相对较长。
目前，我正在考虑将问题转换为确定性问题，以便可以使用 A* 等搜索算法来解决它。这是一个好方法吗？如果是，我该怎么做？
最佳答案
此问题是一个部分可观察的马尔可夫决策过程 (POMDP)。 POMDP 可以确定性地解决，但通常使用随机算法来找到近似最优解。找到真正的最优策略没有多项式时间解，即使是近似解也可能很慢。从好的方面来说，一旦您找到政策，就可以很快地遵循它。
一些可用的求解器:
关于algorithm - 边缘可以被障碍物阻挡的图搜索算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15595722/