4

背景：私が小さなロボットを持っていると想像してください。このロボットをマップ（グラフ）のノードに配置します。ロボットはgiveMeMapCopy（）メソッドを呼び出して、自分が座っているマップ全体のコピーを取得できます。私の小さなロボットに、幅優先探索を使用して出口ノードへの最短経路を見つけることができる関数を提供したいと思います。 。このようなマップの例を次に示します。

ここに画像の説明を入力してください

私はYouTubeでグラフの幅優先探索を行う方法についてのビデオを見たので、何をする必要があるかについて良い考えを持っています。問題は、ロジックを再帰的にするのが難しいと感じていることです。これが私のコードです：

public class Robot
{
    // fields required for traversal
    private Queue<ArrayList<String>> queue;
    private ArrayList<ArrayList<String>> result;
    private String workingNode;
    private ArrayList<String> routeSoFar;

    private Queue<String> knownShortestPath;

    public Robot() {
        queue = new LinkedList<ArrayList<String>>();
        result = new ArrayList<ArrayList<String>>();
        routeSoFar = new ArrayList<String>();
        knownShortestPath = new LinkedList<String>();
    }

    // Runs when Robot has reached a node.
    public void enterNodeActions() {
        knownShortestPath = determineIdealPath();
    }

    // Runs to determine where to go next
    public String chooseNextNode() {
        if(!knownShortestPath.isEmpty())
        {
            // TODO: Need to go through the 
        }
    }

    public LinkedList<String> determineIdealPath()
    {
        try {
            // Get the map
            Map m = giveMeMapCopy();

            // Get all entry nodes of map
            Set<String> entryNodes = m.getEntryNodes();

            /*
             * Loop through all Entry nodes, and find out where we are.
             * Set that as current working node.
             */
            for (String n : entryNodes) {
                if(n == getMyLocation())
                {
                    workingNode = n;
                }
            }

            // All enighbours of working node.
            Set<String> neighboursNames = getNeighboursNames(workingNode);

            /*
             * For each neighbour, construct a path from working node to the neighbour node
             * And add path to Queue and Result (if not already present).
             */
            for(String node : neighboursNames)
            {
                if(!node.equals(getMyLocation()))
                {
                    ArrayList<String> route = new ArrayList<String>();
                    route.add(getMyLocation());
                    route.add(node);
                    if(!containsRoute(result, route))
                    {
                        if(!containsRoute(queue, route))
                        {
                            queue.add(route);                           
                        }
                        result.add(route);
                    }
                }
            }       
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

再帰を発生させたいのは、エントリノード[A]のすべてのネイバーを通過した後、次の[B]に移動して同じことを実行する、つまり、各ネイバーを通過する（Aを無視する） 、結果リストにすでに存在しているため）、それらをキューリストと結果リストに追加します。

問題が明確になっていることを願っています。そうでない場合はお知らせください。不明な点はすべて明確にしようと思います。

4

2 に答える 2

3

幅優先探索は、（この場合は部分パスの）キューに基づいているため、通常は再帰なしで実行されます。一方、深さ優先探索はスタックに基づいており、再帰関数の呼び出しスタックを使用して非常に自然に実装できます。

于 2013-01-26T14:17:26.813 に答える
0

基本的に、必要なのは、ダイクストラのアルゴリズムなどを実装して、グラフ内のソースと宛先の間の最短パスを見つけることです。

このような実装は、Javaでここにあります。すべての重みをに設定するだけ1です。

于 2013-01-26T14:39:33.960 に答える