bulmak kümeler

Question

: kümelerinin

0 0 0 0 0 
0 2 3 0 1 
0 8 5 0 7 
7 0 0 0 4 

Çıktı olmalıdır grupları:

Küme 1: <2,3,8,5,7>

Küme 2: <1,7,4>

Answer 1

Bunu yapmanın bir yolu grafiktir. Matrisi bir sırayla hareket ettirin (soldan sağa, yukarıdan aşağıya doğru giderdim). Sıfır olmayan bir öğeyle karşılaştığınızda, grafiğe ekleyin. Sonra tüm komşularını kontrol edin (8 bağlantılı komşuları istediğiniz gibi) ve sıfır olmayan her biri için, düğümünü grafiğe ekleyin ve mevcut öğeye bağlayın. Grafikteki öğeler muhtemelen bir koordinat ekleyip eklemediğinizi görebilmeniz için koordinatlarını takip etmelidir. Matrisi geçtiğinizde, bir dizi küme içeren bir grafiğiniz vardır. Kümeler, bağlı elemanların alt grafikleri olmalıdır.

Answer 2

Sorununuz, bağlı bileşenleri bulma gibi görünüyor. Bir travers yöntemi kullanmalısınız (BFS veya DFS işi yapacak). Tüm elemanlar üzerinde yineleyin, sıfır olmayan her öğe için bir travers başlatın ve bu traverste gördüğünüz tüm öğeleri kaydedin ve her bir ziyaret edilen öğeyi sıfıra dönüştürün. Aşağıdaki kodu gibi bir şey: Eğer grubu sayısını bilmek veya grupların statik numaraya veri sığdırmak istiyorsanız

void DFS(int x, int y) 
{ 
    printf("%d ", g[x][y]); 
    g[x][y] = 0; 
    // iterate over neighbours 
    for(dx=-1; dx<=1; dx++) 
    for(dy=-1; dy<=1; dy++) 
     if (g[x+dx][y+dy]) DFS(x+dx, y+dy); 
} 

for(i=0; i<n; i++) 
    for(j=0; j<n; j++) 
    if (g[i][j]) 
    { 
     DFS(i, j); 
     printf("\n"); 
    } 

Answer 3

, sen k-ortalama yapabilirsiniz.

http://en.wikipedia.org/wiki/K-means_clustering

Answer 4

Sen Connected Component Labeling yapmak istiyorum. Bu genellikle bir görüntü işleme algoritması olarak kabul edilir, ancak tanımladığınızla eşleşir.

numaralar ait 2D dizi söyledi çünkü Ayrıca K-araçlarının öneriler alacak ve 2D numaralarının ait dizi olarak tercüme etmek kolaydır. K-demek, istediğiniz gibi bir 2D dizide bağlı olmayan gruplar halinde bir düzlemde nokta kümeleri bulur.

Answer 5

kod örneği:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Practice 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var matrix = new[] { new StringBuilder("00000"), new StringBuilder("02301"), new StringBuilder("08507"), new StringBuilder("70004") }; 
      var clusters = 0; 
      for (var i = 0; i < matrix.Length; i++) 
       for (var j = 0; j < (matrix.Any() ? matrix[i].Length : 0); j++) 
        if (matrix[i][j] != '0') 
        { 
         Console.Write("Cluster {0}: <", ++clusters); 
         var cluster = new List<char>(); 
         Traverse(matrix, i, j, ref cluster); 
         Console.WriteLine("{0}>", string.Join(",", cluster)); 
        } 
      Console.ReadKey(); 
     } 

     private static void Traverse(StringBuilder[] matrix, int row, int col, ref List<char> cluster) 
     { 
      cluster.Add(matrix[row][col]); 
      matrix[row][col] = '0'; 
      for (var i = -1; i <= 1 && row + i >= 0 && row + i < matrix.Length; i++) 
       for (var j = -1; j <= 1 && col + j >= 0 && col + j < (matrix.Any() ? matrix[row + i].Length : 0); j++) 
        if(matrix[row + i][col + j] != '0') 
         Traverse(matrix, row + i, col + j, ref cluster); 
     } 
    } 
} 

Algoritma açıklama:

• o satır her sütun için: her satır için

  • • öğe bir ziyaret edilmemiş ise sıfır olmayan:
      1. Bulunan küme üyesini kaydedin;
      2. Ziyaret edilen yeri [satır, sütun] olarak işaretleyin; [- kolon, 1 - satır 1]
         • ;: bir edilmemiş sıfır olmayan komşuları için
         • ara içinde sınırları matris kalırken
         • [satır - 1, sütun];
         • [satır - 1, sütun + 1];
         • [satır, sütun - 1];
         • [satır, sütun + 1];
         • [satır + 1, sütun - 1];
         • [satır + 1, sütun];
         • [satır + 1, sütun + 1].
      3. Eğer komşu, sıfırlanmamış bir sıfır değilse, tüm komşuları ziyaret edilene kadar (tüm küme üyeleri bulunana) yinelemeli olarak 1-4 numaralı adımları yineleyin.