带条件的寻路算法

Question

我有三个 Java 型号类：Map、Room、Object。这些是使用 JAXB 从以下 XML 文件映射的：

<map>
   <room id="1" name="Stairway" east="2"/>
   <room id="2" name="Kitchen" north="4" south="3" west="1">
       <object name="Hat"/>
   </room>
   <room id="3" name="Hallway" east="1" south="4">
       <object name="Money"/>
   </room>
   <room id="4" name="Bathroom" south="2"/>
</map>

一个Map包含Room，一个Room可以包含Object。每个 Room 都具有指示可以从那里到达哪些其他 Room 的属性 (north/east/west/south)。
例如。 房间 3 的可能方向：
房间 1（东）
房间 4（南）

还有一个单独的 Object 列表，我们称它们为 targets。

目标是 "collect" 所有目标，意思是创建一条通过包含目标的 Room 的路径。
您可以将其视为具有节点 (Room) 和边（指向另一个 Room 的方向 north/east/west/south）的图形 (Map)。

public Route findRoute(Map map, Room startRoom, List<Object> targets) {
        // walk through the map, find all targets 
        // once found them all return the route
}

所以基本上我正在寻找一个干净的 way/algorithm 来创建一条通过该图的路径，其中每个节点都包含我的目标列表中的 Object。

我知道 Dijkstra 算法，但我认为它不适合我的用例，因为我有一个必须满足的条件（Room 必须包含特定的 Object）。几乎没有其他路径查找算法，但我无法为我的特定问题找到解决方案。

感谢任何帮助。

编辑：

任何路径都可以（最短路径是可有可无的，但不是强制性的）并且收集目标的顺序无关紧要。

Answer 1

这是一个粗略的方法：

以入口为初始起点
Select 1 个目标尚未达到。
执行广度优先（或深度优先）搜索以找到通往该目标的路径，并标记您沿该路径遇到的任何其他目标。
如果所有目标都已定位，则停止。
将选择目标所在的房间作为下一个起点
转到 (2)。

按照我的理解，将所有段连接起来形成的路径将满足您的要求。

带条件的寻路算法

Path finding algorithm with condition

java

algorithm

path

graph-algorithm