グラフの問題で困っています。私は OpenSG を使用しており、建物内の 2 点間のパスを見つけようとしています。
私はこのグラフを作成しました：
これを使用して、建物内の 2 点間の最短経路を見つけます。
これは私がパスを見つける方法です：
- グラフに開始/ターゲット ノードを追加します
- 開始/ターゲット ノードから到達可能なすべてのノードにエッジを追加します (これは OSG の IntersectAction で行われます)
- A* アルゴリズムを使用して最短経路を見つけます
グラフを最小化したい。2 点間のパスが少し長くなっても問題ありません。現在の冗長性を排除したいだけです。たとえば、明るい緑色のノードはすべて削除できます。部屋にはドアが「見えない」ポイントがないため、ノードは必要ありません。次のようになります。
だから私は多かれ少なかれ私が望むことをするアルゴリズムを持っていますが、これはよく知られた問題であるに違いないと思いました. これは最小頂点カバーではありません。たとえば、最小頂点カバーにドア ノードが含まれていない場合、2 つの部屋の間の道が見つからないためです。
さまざまなグラフの問題を比較しましたが、実際に一致するものは見つかりませんでした...
非常に遅い時間 (午前 6 時 20 分) で、私は就寝する必要があります。問題に関するご意見をお寄せいただきありがとうございます。