0

私は2次元のブール配列を持っています:

boolean [][] フィールド = new boolean[7][11];

私がやりたいことは、フィールド[0][0]からフィールド[7][11]への有効な「パス」があるかどうかを確認することです。

たとえば、これは最初から最後まで有効なパスです: 0 = false、1 = true

1 1 0 0 0
0 1 0 0 0
1 1 0 0 0
1 0 0 0 0
1 1 1 1 1

0,0 から 4,4 までを真の値で接続できます。

無効なパスの例:

1 1 0 0 0
0 1 0 0 0
1 0 0 0 0
1 0 0 0 0
1 1 1 1 1

0,0 から 4,4 までは接続できません。(垂直方向と水平方向の値のみが有効なパスであり、対角線ではありません)

これにアプローチする最良の方法は、再帰を使用することだと思います。0,0 から開始し、隣人が「真」であることを確認し、そうであれば次に進みます。次に、隣人をもう一度確認します。すべてのネイバーが false の場合は、戻って別のパスを見つけます。

これにアプローチする最良の方法は何ですか？

編集 ：

これは私がこれまでに持っているものです。アルゴリズムは正しいパスを正確に出力しますが、戻り値は常に正しいとは限りません。

誰でもエラーがどこにあるかを見ることができますか?

static boolean isValidPath(boolean [][] field, int i, int j, int previ, int prevj) {

        if(i >= field.length && j >= field[0].length) return true;


        if(field[i][j] == true) {

            System.out.println("Valid i: " + i + ", j: " + j);
            if(i + 1 < field.length && i + 1 != previ) isValidPath(field, i + 1, j, i, j);
            if(j + 1 < field[0].length && j + 1 != prevj) isValidPath(field, i, j + 1, i, j);
            if(i - 1 >= 0 && i - 1 != previ) isValidPath(field, i - 1, j, i, j);
            if(j - 1 >= 0 && j - 1 != prevj) isValidPath(field, i, j - 1, i, j);

            return true;

        } else return false;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        boolean[][] field = new boolean[][] { { true,  true, false, false, false}, 
                                              { false, true, false, false, false},
                                              { true,  true, false, false, false},
                                              { true, false, false, false, false}, 
                                              { true, true, true, true, true }};

        System.out.println("Is this path valid: " + isValidPath(field, 0, 0, 0, 0));
    }

これは出力です：

Valid i: 0, j: 0
Valid i: 0, j: 1
Valid i: 1, j: 1
Valid i: 2, j: 1
Valid i: 2, j: 0
Valid i: 3, j: 0
Valid i: 4, j: 0
Valid i: 4, j: 1
Valid i: 4, j: 2
Valid i: 4, j: 3
Valid i: 4, j: 4
Is this path valid: true

ご覧のとおり、アルゴリズムは配列全体で実行され、有効なパスが出力されます。しかし、たとえば [4][4] の値を false に変更しても、結果は true のままです。

false と true を返す場所が本当にわかりません。

4

3 に答える 3

1

ここにあるのは、より非標準的な方法で表示された単なるグラフです。どのタイプのグラフ検索でも、問題を解決できます。BFSまたはDFSを使用することをお勧めします。実際、DFS は通常、再帰を使用して実装されるため、再帰を使用してこの問題を解決できます。

于 2013-01-18T09:55:47.340 に答える
0

私には、古典的な TSP 問題 ( http://en.wikipedia.org/wiki/Travelling_salesman_problem ) のように見えます。

次のような再帰的な方法がおそらく最良の方法です。

bool right_path(int x, int y)
{
// check whether you have a true neighbors 
// (you can do it by yourself I hope ;)
....
// if yes, call recursive the next one

if (right_path(x+1, y) || right_path(x, y+1))
   return true;
else
   return false;
}
于 2013-01-18T10:01:58.233 に答える
0

これは、多くのアルゴリズムがすぐに利用できる、広く知られているプログラミング タスクです。あなたが提案することは、深さ優先検索と呼ばれます。A*またはDijkstraを使用すると思います。

于 2013-01-18T09:54:11.947 に答える