2

行列内の隣接するセルのグループを見つけたい。

たとえば、以下の2Dマトリックスについて考えてみましょう。

2次元バイナリ行列

与えられたマトリックスには、値を持つ2つの連続したセルのグループがあります1。

バイナリ行列の連続する1

これらのグループを見つける1つの方法は次のとおりです。

  1. 値1の最初のセルに別の値を割り当てます。たとえば、A。1次に、隣接する値を持つセルを調べA、それらのセルの値をとして設定しますA。隣接するセルがなくなるまで、この方法で検索します。

  2. 次のステップでは、値がのセルにインクリメントAして開始します。次に、上記と同じ手順に従います。B1

これは一種のブルートフォースであり、3Dでは効率的ではありません。少し調整するだけで使用できるアルゴリズムを知っている人はいますか？

または、この問題の簡単な解決策はありますか？

4

3 に答える 3

5

あなたがやろうとしていることは、多くの場合、接続されたコンポーネントのラベル付けというラベルの下にあります。これ以上詳しく説明することはしませんが、ウィキペディアの記事は、私ができる、またはするよりもうまく説明しています。

しかし、私が答えている間...

あなたと SO の他の多くの人は、配列のすべての要素に対する単純な反復 (ブルートフォースという軽蔑的な用語で特徴付けられる) は、絶対に避けるべきものだと考えているようです。現代のコンピューターは非常に高速です。配列の各要素に順番にアクセスすることは、ほとんどのコンパイラが完全に最適化できるものです。

3D 配列のすべての要素にアクセスすると、 は時間的に複雑であると考える罠に陥ったようですO(n^3)。ここnで、 は配列の各次元に沿った要素の数です。そうではありません。配列の要素へのアクセスは、配列内O(n)のn要素の数です。

配列内の各要素を訪問する時間の複雑さが、O(n^3)より優れた漸近的な時間の複雑さを提供する多くの洗練されたアルゴリズムであったとしても、実際には、より単純なアルゴリズムよりもパフォーマンスが低下することが証明されます。高度なアルゴリズムの多くは、コンパイラがコードを最適化することを非常に困難にします。そして、O(n^2)これはアルゴリズムの等価クラスであり、とO(m+k*n^2)の両方が定数である場合など、真の時間の複雑さを持つアルゴリズムを含むことに注意してください。mk

于 2012-07-31T09:50:46.373 に答える
3

以下は、単純なフラッド フィル アルゴリズムの疑似コードです。

>>> def flood(i, j, matrix):
...     if 0 <= i < len(matrix) and 0 <= j < len(matrix):
...         if matrix[i][j] == 1:
...             matrix[i][j] = 0
...             for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
...                 flood(i + dx, j + dy, matrix)

>>> count = 0
>>> while True:
...     i, j = get_one(matrix)
...     if i and j: #found a one
...         count += 1
...         flood(i, j, matrix)
于 2012-07-31T12:05:06.320 に答える
0

これは、グラフで強連結成分を見つけるのとまったく同じですが、全体が 3 次元に拡張されています。したがって、2D グラフに任意の線形時間アルゴリズムを使用し、DFS を 3 次元にも適応させることができます。これは簡単です。

これらのアルゴリズムは線形時間であるため、実行時間の複雑さに関しては改善できません。

于 2012-07-31T09:50:50.133 に答える