プロジェクトに取り組んでいるときに、解決できなかったグラフ アルゴリズムの問題に出くわしました。問題は次のとおりです。
重み付けされた有向グラフがあり、指定されたノードを訪問しながら、開始ノードと終了ノードの間の最短経路を見つけたいと考えています (特定 のノードを訪問するグラフで最短経路を見つける と非常によく似ています)。ただし、ノードとエッジに加えて、このグラフには「アイテム」の概念もあり、ノードに存在し、そのノードに入ると「ピックアップ」します。ここで、特定のエッジに必要なアイテムI を取得した場合にのみ、エッジをトラバースできるという追加の制約があります。ドアの鍵と考えてください。ドアを通過する前に鍵を取得する必要があります。
指数関数的に爆発する力ずくの方法しか思い浮かびません。誰かがより良いものを考えたり、この問題が解決される場所を教えてくれますか? それとも、これが「難しい」（計算的に言えば）ことを私に納得させますか？助けてくれてありがとう！