-1

サイズ N のバイナリ マトリックスの「パス」は、パス内の各セルのエントリが 1 になるように、(0,0) から始まり (N,N) で終わるセルの順序付きコレクションです。

例-> マトリックス:

1100
1100
0010
0001

と の 2 つのパスがあります
(0,0)->(0,1)->(1,1)->(2,2)->(3,3)。
(0,0)->(1,0)->(1,1)->(2,2)->(3,3)

考えられるすべてのパスを印刷するための最良の方法は何ですか? 現在、私は最も低い「1」をたどり続け、それらを1つずつゼロにするというブルートフォースソリューションしか考えられません。

4

2 に答える 2

3

問題をグラフ としてモデル化しますG=(V,E)。ここで
V = { all nodes marked as 1 }、および
E = { (u,v) | u,v are in V and u,v are "neighbors" in the matrix }

すべてのパスを見つける最も簡単な方法は、セットを維持せずにDFSvisitedを使用することです。そして、すべての可能なパスを使い果たすまで、それを繰り返し実行します。

グラフにサイクルがある場合（そして、サイクルのあるグラフには無限の数のパスが存在する可能性があるため、実際にはすべての単純なパスが必要です）-visitedパスごとに「特別な」セットを維持する必要があります-このセットは現在探索されているパス内のすべてのノードを保持します。DFSで再帰呼び出しから「戻る」と、頂点はそのパスから削除されます。

パスの数は指数関数的であり、すべてを出力する必要があるため、実行時間はこの問題に対して指数関数的ではないことに注意してください。

于 2012-11-07T08:58:29.970 に答える
1

あなたの質問はあまり明確ではありません.私は、可能な方向が1ステップ正しいと仮定します(例: (1,1) -> (1,2) )、1ステップ下(例:(1,1,) -> (2, 1)) または右と下の両方 (例: (1,1) -> (2,2))。そうしないと、amit が説明したように、無限の数のパスが存在する可能性があります。

あなたの質問の場合、3つの可能なパスがあるはずです。nav_jan が述べたように、(0,0)->(1,1)->(2,2)->(3,3) も可能なパスです。

私は再帰的な方法を設計しました。それは非常に理解しやすいです。(0,0) 点から開始し、3 方向に移動してみます。現在のポイントが 1 の場合、移動を続けます。それ以外の場合は戻ります。(n-1,n-1) ポイントに到達すると、有効なパスが見つかります。

コードは Java で書かれています。

public static List<String> getMatrixPaths(int[][] matrix){
    List<String> pathList = new ArrayList<String>();
    if(matrix != null && matrix.length > 0){
        getMatrixPaths(matrix, 0,0, "", pathList);
    }
    return pathList;
}
public static void getMatrixPaths(int[][] matrix, int i, int j, String path, List<String> pathList){
    int n = matrix.length - 1;
    if(i > n || j > n){
        return;
    }else if( matrix[i][j] == 1){//only 1 is valid
        path += String.format(" (%d,%d)", i , j);
        if( i ==n && j == n){ // reach (n,n) point
            pathList.add(path);
        }else {
            getMatrixPaths(matrix, i +1, j , path, pathList);
            getMatrixPaths(matrix, i , j +1, path, pathList);
            getMatrixPaths(matrix, i + 1 , j +1, path, pathList);
        }
    }
}

問題の行列をテストに使用します。私の結果は [ (0,0) (1,0) (1,1) (2,2) (3,3), (0,0) (0,1) (1) です。 ,1) (2,2) (3,3), (0,0) (1,1) (2,2) (3,3)] .

この質問を参照できます: Algorithm for Find all paths in a NxN grid . とても似ていると思います。

于 2012-11-08T09:45:38.270 に答える