條件路徑搜尋算法

我有三個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 S和Room可以包含Object秒。每個Room都有屬性，指示可以從那裏（北/東/西/南）到達哪個其他的Room。
例如從3室可能的方向：
室1（東）
室4（南）

還有的Object個單獨的列表，我們姑且稱之爲目標。

目標是「收集」所有目標，意思是通過包含目標的Room創建路徑。
您可以將其視爲具有節點（Room）和邊緣（導致另一個Room的北/東/西/南的方向）的圖（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 
}

所以基本上我要尋找一個乾淨的方式/算法，通過圖表來創建路徑，其中每個節點包含我的目標列表中Object。

我知道Dijkstra算法，但我認爲它不適合我的用例，因爲我有一個必須滿足的條件（Room必須包含特定的Object）。還有其他很少的路徑查找算法，但我找不出解決我的特定問題的方法。

任何幫助表示讚賞。

編輯：

任何路徑都行（最短路徑是一個很好的到了，但不是強制性的），它的目標是收集不要緊和順序。

來源

2016-07-29 lenny

您是否正在尋找*最短的*這樣的路徑，或者只是任何路徑呢？ –

任何路徑都會執行並且收集目標的順序無關緊要。 – lenny

Dijkstra的算法不太適合，因爲它不會找到包含循環的路徑，而且您可能需要這樣一個路徑 - 例如，如果房間中只有一個入口/出口的對象。 –

這裏有一個粗糙的方法：

讓入口是最初的起點。
選擇一個尚未到達的目標。
執行廣度優先（或深度優先）搜索以找到該目標的路徑，並標記沿路徑遇到的任何其他目標。
如果所有目標都已找到，則停止。
讓選定目標所在的房間成爲下一個起點。
Goto（2）。

根據我的理解，連接所有段形成的路徑將滿足您的要求。

來源

2016-07-29 22:25:54

條件路徑搜尋算法

回答

相關問題