条件付き経路検索アルゴリズム

Question

私は3種類の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が含まれていなければなりません）。他にもいくつかの経路発見アルゴリズムがありますが、私の特定の問題に対する解決策を見つけることができませんでした。

助けてください。

EDIT：

任意のパスが行います（最短経路をへの持っている、素敵な、しかし必須ではありません）とターゲットが収集されるの順番は重要ではありません。

Answer 1

はここで、粗アプローチです：

1. は入り口が最初の出発点とします。
2. まだ選択されていないターゲットを1つ選択してください。
3. 幅優先（または深さ優先）検索を実行してそのターゲットへのパスを検索し、そのパスに沿って他のターゲットをマークします。
4. すべてのターゲットが見つかった場合は停止します。
5. 選択したターゲットが配置された部屋を次の開始点にします。
6. 後藤（2）。

私が理解しているように、すべてのセグメントを結合することによって形成されたパスが要件を満たします。