0

私は学校の課題を抱えており、私の方法では、特定のノードから始まるすべての可能なパスを見つける必要があります。問題は、私の方法が最長のパスのみを見つけてから、新しいパスの作成を停止し、なぜこれを行っているのか理解できないことです (Java の経験が少なすぎる可能性があります)。char[3][3]メソッドが反復する必要がある配列を使用しています。基本的な考え方はうまくいっていますが、すべての道ではありません。

私が書いた方法：

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            currentFullPath.add(coord);
            if (!(paths.contains(currentFullPath))) {
                paths.add(currentFullPath);
                //start over again with same coord
                computeAllPaths(currentFullPath.get(0), new ArrayList<Point>()); 
            } else {
                //try to add another coord
                computeAllPaths(coord, currentFullPath); 
            }
        }
    }
}

メソッド呼び出し:

computeAllPaths(new Point(0, 0), new ArrayList<Point>());

宣言:

private List<ArrayList<Point>> paths = new LinkedList<ArrayList<Point>>();

3x3 配列の出力:

    Current paths size: 8

(0.0,0.0)(1.0,0.0)(0.0,1.0)(0.0,2.0)(1.0,2.0)(2.0,2.0)(2.0,1.0)(2.0,0.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(1.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(1.0,1.0)(0.0,2.0)(0.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)

多くの種類のリストとセットを試しましたが、誰も機能していないようで、理由がわかりません。誰かがこれを理解するのを手伝ってくれますか?

ボードの例:

ん | ん | あら
| え | T
N | T | T | 〇

許可される移動: R (1,0) から開始すると、許可される移動は次のようになります。

  • N(0,0)
  • N(0,1)
  • E(1,1)
  • T(2,1)
  • N(2,0) つまり、基本的には直接の隣人です。
4

1 に答える 1

0

ですから、私自身はJavaコーダーではありませんが、あなたはいくつかのことをうまくやっていないのです。

currentFullPathあなたはそれにポインタを追加しpathsているので、そのコピーにポインタを追加する必要があるので、何が起こるかを推測してください。追加しpathsた後、後でさらに変更します。基本的にこれをデバッグするにpathsは、内側のループのすべてのパスを出力するだけです。また、これを行わない場合はcurrentFullPath、それぞれcoordのコピーを作成する必要があります。最終的には、すべてのネイバーを同じパスに追加します。neighbouringCoords

Javaは常にオブジェクトへのポインタを渡していることを忘れないでください。

編集：私はまだたくさんのナンセンスが飛び回っているのを見る。これを試して：

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            ArrayList<Point> newList = new ArrayList<Point>(currentFullPath);
            newList.add(coord);
            if (!(paths.contains(newList))) {
                paths.add(newList);
                //start over again with same coord
                computeAllPaths(currentFullPath.get(0), new ArrayList<Point>()); 
            } else {
                //try to add another coord
                computeAllPaths(coord, newList); 
            }
        }
    }
}

結果を示す。

編集2：これははるかに高速になります。

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            ArrayList<Point> newList = new ArrayList<Point>(currentFullPath);
            newList.add(coord);
            paths.add(newList);                           
            computeAllPaths(coord, new ArrayList<Point>(newList));            
        }
    }
}
于 2013-03-02T11:29:13.317 に答える