我被困在一个图表问题上。我正在使用 OpenSG 并试图找到建筑物中两点之间的路径。
我构建了这个图表：
我用它来找到建筑物中两点之间的最短路径：
这就是我找到路径的方式：
- 我在图中添加开始/目标节点
- 我将开始/目标节点的边添加到所有可到达的节点（这是通过 OSG 中的 IntersectAction 完成的）
- 我使用 A* 算法找到最短路径
我现在想最小化图表。如果两点之间的路径变长一点也没关系，我只想消除我现在拥有的冗余。例如，可以删除所有浅绿色节点。房间里没有“看到”门的地方，所以不需要节点。它应该看起来像这样：
所以我有一个算法可以或多或少地做我想要的，但我只是认为这一定是一个众所周知的问题。这不是最小顶点覆盖，因为例如，如果在最小顶点覆盖中不包括门节点，我将无法在两个房间之间找到路。
我与各种图形问题进行了比较，但我找不到真正的匹配......
很晚了（早上 6 点 20 分），我应该去睡觉了，也许它看起来有点混乱，或者它真的很明显。感谢您就该问题提出任何意见。