3

私は、2 点間の最短経路を見つける必要がある学校のプロジェクトに取り組んでいます。基本的に、幅優先検索を使用してグラフをトラバースしてから、マップを使用して各都市の先行者を追跡します。私の考えでは、最後に到達したら、エッジ マップを使用して都市がどのように到達したかを調べ、本質的に逆方向に作業するというものです。ただし、マップから値を取得しようとすると、内容を印刷するとそこに何かがあることが示されますが、取得されるのはすべて null です。誰かが私が問題を追跡するのを手伝ってくれたら、私はそれを感謝します.

各都市とその近隣の入力ファイルの内容:

basic
Bismark      Fargo
Minneapolis  Chicago
StPaul       Chicago
Minneapolis  StPaul
Minneapolis  Fargo
Fargo        GrandForks

コード(修正されたバージョンであるため、このコードでは説明されている問題は発生しません):

import java.util.*;
import java.io.*;

public class BFSBasics {
    public static void main(String[] args) throws FileNotFoundException {
        Map<String, List<String>> graph = new HashMap<>();
        openFile(graph, args[0]);
        String start = args[1];
        String end = args[2];

        BFS(graph, start, end);
    }

    public static void openFile(Map<String,List<String>> graph, 
            String file) 
            throws FileNotFoundException{
        Map<String,List<String>> aGraph = new HashMap<>();
        try (Scanner scan = new Scanner(new File(file))){
            if(!scan.next().equals("basic")){
                System.err.println("File cannot be read.");
                System.exit(1);
            }else{
                while(scan.hasNext()){
                    String city1 = scan.next();
                    String city2 = scan.next();
                    addEdge(graph, city1, city2);
                    addEdge(graph, city2, city1);                   
                }   
            }   
        }
    }

    private static void addEdge(Map<String, List<String>> graph, String city1,
            String city2){
        List<String> adjacent = graph.get(city1);
        if(adjacent == null){
            adjacent = new ArrayList<>();
            graph.put(city1, adjacent);
        }
        adjacent.add(city2);
    }

    public static void BFS(Map<String, List<String>> graph, String start,
            String end) {
        boolean done = false;
                //cities that still need to be worked on
        Queue<String> work = new ArrayDeque<>();
                //cities that have already been seen
        Set<String> seen = new HashSet<>();
                //cities predecessor i.e. how it was gotten to
        Map<String, String> edges = new HashMap<>();
        LinkedList<String> path = new LinkedList<>();

        String city = start;
        work.add(start);
        while (!done && !work.isEmpty()) {
            city = work.remove();
            for (String s : graph.get(city)) {
                if (!seen.contains(s)) {
                    edges.put(s, city);
                    work.add(s);
                    seen.add(s);
                    if (s.equals(end)) {
                        done = true;
                    }
                }
            }
        }

        //Work backwards through the edges map and push onto the path stack
        path.push(end);
        String temp = edges.get(end);
        while(!temp.equals(start)){
            path.push(temp);
            temp = edges.get(path.peek()};
        }
        path.push(start);
        //print out the path
        while(!path.isEmpty()){
            System.out.println(path.pop());
        }
    }
}
4

2 に答える 2

1

パス構築コードに何か問題があります:

path.push(end);                 // push node (n - 1)
String temp = edges.get(end);   // temp = node (n - 2)
while(!temp.equals(start)){
    path.push(edges.get(temp)); // push node (n - 3) down to and including node 0
    temp = path.peek();         // temp = node (n - 3) down to and including node 0
}
path.push(start);               // push node 0

したがって、ノード ( n - 2) はパスにプッシュされませんが、ノード 0 は 2 回プッシュされます。

しかし、これを除けば、プログラムは私にとってはうまくいきます。したがって、 Hbcdevが示唆するように、実際には到達不能なターゲットがある可能性があります。実際に終了ノードに到達したかどうかを確認する必要があります。グラフ データトラ構造は有向グラフをモデル化することに注意してください。したがって、入力を無向エッジとして解釈する場合は、入力の各行に 2 つの有向エッジを挿入する必要があります。

また、最初のノードを確認済みとしてマークしないことに注意してください。他のすべてのノードは、キューに追加すると確認済みとしてマークされます。最初にもマークする必要があります。

編集：（
ほぼ）完全なコードを貼り付けた後、次の方法で修正しました：

  • との 2 つのワイルドカード インポートを追加java.util.*しましjava.io.*た。ワイルドカードのインポートは迅速で汚いです。
  • }クラス定義を閉じるために、最後にクロージングを追加しました。
  • basic入力データに単語を含む行を追加しました。System.exit(1)そのキーワードが欠落している場合は、一貫性のない状態で続行するのではなく、実際に行う必要があります。

これらの変更を加えて、2 つの都市のすべての可能な組み合わせを、常に両方の順序でテストし、都市自体へのパスを含めました。null出力にも、印刷された例外の原因としても、値の証拠はどこにもありません。

于 2012-08-02T18:48:08.293 に答える
-1

ここにいくつかの問題があります。直接の原因は次のとおりです。ロジックは、特定のノードに到達する方法が1つしかないことを暗黙的に想定しています。これは本当かもしれませんが、私はそれを疑っています。同じノードに到達する方法が2つある場合は、マップ内の最初の方法を2番目の方法で上書きします。

たとえば、入力が次のとおりであるとします。

A->B
C->B
B->E
D->E

AからEに移動したい。これは、A、B、Eに移動することで実行できます。ただし、マップを作成するときに、B、Aのエッジエントリを作成します。次に、B、Cを記述し、上書きします。 B、A。次にE、Bと書きます。次に、E、Dを記述し、E、Bを上書きします。したがって、完了したら、エッジマップにあるのは（B、C）と（E、D）だけです。次に、Eから後方に歩こうとします。E、Dが見つかります。しかし、これは間違っています。E、Bが必要でしたが、上書きされました。Dのエントリを見つけようとすると、エントリがないため、Aに戻ることはできません。

2番目の問題は、目標が最初から最後まで最短経路を見つけることであると言ったことです。しかし、最短経路を見つけるために何もしていません。経路を見つけたら、探すのをやめます。原則として、実際にはすべての可能なパスを見つけて、そのリストから最短のパスを選択する必要があります。（または、うまくいけば、何らかの方法で、進むにつれて長いパスを削除します。）

于 2012-08-02T18:55:27.977 に答える