10

ここでどのアルゴリズムを適用すべきか知りたかったのです。DFSはそうしますか？

2次元行列が与えられます。その行列で接続されているセットの総数を見つけます。

接続されたセットは、1が言及され、そのセット内に隣接関係を共有する他のセルが少なくとも1つあるセルのグループとして定義できます。1が含まれ、周囲に1が含まれていないセルは、1つのセルが含まれるセットと見なすことができます。ネイバーは、8つの可能な方向（つまり、N、W、E、S、NE、NW、SE、SW方向）で特定のセルに隣接するすべてのセルとして定義できます。セルはそれ自体の隣人ではありません。

例えば：

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

接続セット数は3

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

接続セット数は9です。

4

11 に答える 11

7

これを一般的なグラフの問題と考えて、 BFSやDFSなどのアルゴリズムを適用する必要はないと思います。

マトリックスを 3 回スキャンする必要があります。

スキャン 1:

上から始める

  1. あなたの例では、最初の行はそのステップの後に次のようになります

    1 0 0 2

  2. 次の行に移動し、行のすべての 1 について、左側の隣人が非 0 かどうかを確認します
    • 0 以外の場合は左の値を取る
    • 0 の場合、前の行で 0 以外の隣人をチェックし、最も左側の値を取ります
    • それらのすべてが 0 の場合、これまでに指定された最大数に 1 を追加するだけです
  3. 最後の行が処理されるまで 2 を繰り返します

あなたの例は次のようになります

1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2

スキャン 2:

下から始めて、各隣人が左端の隣人と同じ番号、およびその下の行の隣人と同じ番号を持っているかどうかを確認します

基本的に、このようなマトリックスがある場合

1 0 2

1 0 2

0 1 0

セットが本当に同じ数を持っていることを確認する

スキャン 3:

行列内の一意の非 0 エントリの数を数えます

于 2012-06-28T21:49:46.780 に答える
3

連結成分ラベリングアルゴリズムは、エレメントの連結グループをマークすることを目的としています (4 連結性と 8 連結性の両方)。

于 2012-06-29T11:35:58.873 に答える
2

Pythonic 実装、よりわかりやすいコード:

# sea is 2 D array of 0 and 1s we have to find 1's group surrounded by 0's
def dfs(sea, i, j, b, h, visited):
    surround = ((-1, -1), (0, -1), (1, -1),
                (-1, 0), (1, 0),
                (-1, 1), (0, 1), (1, 1)
                )
    if can_visit(sea, i, j, b, h, visited):
        for s in surround:
            visited[(i, j)] = 1
            dfs(sea, i + s[0], j + s[1], b, h, visited)


def can_visit(sea, i, j, b, h, visited):
    if i >= 0 and j >= 0 and i < b and j < h:
        if (i, j) not in visited and sea[i][j] == 1:
            return True


def find_island(sea):
    visited = {}
    h = len(sea)
    count = 0
    for i, row in enumerate(sea):
        b = len(row)
        for j, item in enumerate(row):
            if can_visit(sea, i, j, b, h, visited):
                count += 1
                dfs(sea, i, j, b, h, visited)
    return count


sea = [[1, 1, 0, 0, 0],
       [0, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 1, 0, 1]
       ]

print find_island(sea)
于 2015-10-19T11:52:29.987 に答える
1

素集合のデータ構造とアルゴリズムを使用したい。これにより、接続されたコンポーネントごとに一意の代表が選択され、最後に数えることができます。

1どの要素が隣接しているかを効率的に評価するために、現在の行のどのセグメントがそれらに隣接しているかを判断しながら、前の行からの(連続した の) セグメントのリストを維持しながら、行列を行ごとにスキャンできます。

于 2012-06-28T21:40:23.467 に答える
0

これは見た目ほど難しくはありません。実際、これは、教授が1年目のコンピュータサイエンスの課題に割り当てるもののように非常に強く感じます。したがって、これが宿題の場合は、そのようにタグ付けする必要があります。

ただし、解決策はかなり簡単です。

for (int y = 0; y < arr.height(); y++)
{
   for (int x = 0; x < arr.width(); x++)
   {
      if (arr[x][y] == 1)
      {
         if (CheckIfConnected(x, y, arr))
         {
            connectedPositionsX.Add(x);
            connectedPositionsY.Add(y);
         }
      }
   }
}

connectedPositionsは、リンクリストまたはセットを保存したいものです。

arr上で指定したタイプの行列を含む2D配列です。

CheckIfConnectedは、かなり簡単に実装することもできます。

bool CheckIfConnected(int x, int y, int[][]arr)
    {
       if (arr.width() >= 2) || (arr.height() >= 2)
       {
          if ((x < arr.width()) && (x >= 0) && (y < arr.height()) && (y >= 0))
          {
            if ((x-1) >= 0) //West
            {
                if (arr[x-1][y] == 1)
                {
                    adjCount[x-1][y] += 1;
                    return true;
                }
            }
            if (((x-1) >= 0) && ((y-1) >= 0)) //Northwest
            {
                if (arr[x-1][y-1] == 1)
                {
                    adjCount[x-1][y-1] += 1;
                    return true;
                }
            }
            if ((y-1) >= 0) //North
            {
                if (arr[x][y-1] == 1)
                {
                    adjCount[x][y-1] += 1;
                    return true;
                }
            }
            if (((x+1) < arr.width()) && ((y-1) >= 0)) //Northeast
            {
                if (arr[x+1][y-1] == 1)
                {
                    adjCount[x+1][y-1] += 1;
                    return true;
                }
            }
            if ((x+1) < arr.width()) //East
            {
                if (arr[x+1][y] == 1)
                {
                    adjCount[x+1][y] += 1;
                    return true;
                }
            }

            //I'll let you implement Southeast to Southwest on your own,
            //the pattern is clear now.
          }
       }
       return false;
    }

そこから、グリッド内の各位置でペアリングを見つけた回数がわかります。これは、接続を追跡するのに役立ちます。

2D配列のカウントは、adjCountこれを追跡します。

また、ダイクストラのアルゴリズムを調べて変更し、再帰的に実行することもできます。DFS（Depth First Search）についておっしゃっていたので、あなたの教授や先生があなたにそのように解決してほしいと思っていると思います。

その場合：

擬似コードでのダイクストラのアルゴリズムは次 のとおりです。http： //en.wikipedia.org/wiki/Dijkstra's_algorithm

お役に立てば幸いです。乾杯！

于 2012-06-28T22:27:50.850 に答える
0

行列をスキャンして 1 を探します。見つかったら、接続されたコンポーネントが接続されているとまだ識別されていない場合は、再帰関数を呼び出します。再帰を使用して連結要素を見つけます。特定のノードが接続コンポーネント内にあると既に識別されているかどうかをどこかですばやく調べて、接続コンポーネントを 2 回識別しないようにし、接続コンポーネントをトラバースする際の無限ループを回避します。

于 2012-06-28T21:28:33.010 に答える
0

Python を使用している場合は、scipyにこの番号を見つける関数があります。

from scipy.ndimage import label

data = [[0, 0, 1, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 1],
        [0, 0, 1, 0, 0, 1, 0, 1],
        [0, 1, 0, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 1, 1, 0],
        [1, 0, 1, 1, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 0]]

connection_structure = [[1,1,1],
                        [1,0,1],
                        [1,1,1]]

_, N = label(data, connection_structure)
    
print(N) 
>>> 9
于 2016-10-19T12:58:10.040 に答える
0

2D 配列内の接続されたコンポーネントの総数を見つけるのに役立つクラスがあります。私のクラスでは、合計数を提供するだけでなく、クラスターを提供し、それらを視覚化します。不要な部分はコメントアウトできます。(Java) でこのクラスを参照してください: https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/ConnectedComponetns.java

于 2016-08-06T20:10:51.637 に答える
0

マトリックスだけで（余分なメモリなしで）やりたい場合は、次のようにします。

スキャナの位置を [0,0] に設定

  1. カウンターをゼロに設定します。
  2. 現在のスキャナー位置から行ごとに (およびセルごとに) マトリックスをスキャンし、1 つを見つけ1て、この後の次の要素にスキャナー位置を設定します。1何もない場合1は、手順 6 に進みます。
  3. 関連するものを に設定しcounter+2、再帰的にそのすべての1隣人を見つけ、それらを に設定しますcount + 2。
  4. count = count + 1
  5. 手順 2 に進みます。
  6. 出力count。

PS: スキャナーの位置が行列のサイズよりも大きい場合、アルゴリズムが終了することは明らかです (混乱を避けるためにこれを書いたわけではありません)。

于 2012-06-28T22:21:24.863 に答える