各エッジのコストが同じである有向グラフの 2 つの頂点間の低コスト パスを見つけたいと考えています。アルゴリズムの実装の容易さと実行時間は非常に重要であるため、アルゴリズムがより単純で高速である場合は、最適に近いソリューションを犠牲にすることを厭いません。
エッジが障害物によってブロックされる可能性があります。エッジがブロックされる確率は事前にわかっています。閉塞は互いに独立しています。エッジの先頭の頂点に到達すると、エッジがブロックされていないかブロックされていることがわかります。
私の問題はカナダ人旅行者問題に似ていますが、確率計画問題の解決策は実装が比較的難しく、最適なポリシーを見つけるのにかかる時間が比較的長くなる可能性があることを理解しています。
現時点では、A* のような検索アルゴリズムを使用して解決できるように、問題を決定論的な問題に変換することを考えています。これは良いアプローチですか? もしそうなら、どうすればこれを行うことができますか?