1
我被困在一個圖形問題上。我正在與OpenSG合作，並試圖找到建築物中兩點之間的路徑。最小化保持連接性的圖形
我寫這個圖：
我用它來尋找在建築物兩點之間的最短路徑：
這是我找到的路徑：
- 我在圖中添加起始/目標節點
- 我從啓動/目標節點是可達的所有節點（這與 IntersectAction在OSG完成）
- 我用的是A * -algorithm找到 最短路徑
現在我要儘量減少圖形。如果兩點之間的路徑稍長一些，我只想減輕我現在擁有的冗餘度並不重要。例如，所有淺綠色的節點都可以被刪除。房間沒有任何「看不見」門的點，所以不需要節點。它應該看起來像這樣： 
所以我有一個或多或少做我想要的算法，但我只是認爲這必須是一個衆所周知的問題。這不是最小的頂點覆蓋，因爲例如如果在最小頂點覆蓋範圍內不包含門節點，我不會在兩個房間之間找到一條路。
我用各種圖形的問題相比，但我無法找到一個真正的比賽...
它非常晚（早上6:20），我應該去睡覺，也許這似乎有點有點混亂或者也許它真的很明顯。感謝您對這個問題的任何意見。