Mamy kilkadziesiąt - sto punktów. Należy znaleźć grupy punktów, np.
piątki punktów które leżą blisko siebie, takie "kliki", gdzie mamy
bliskich sąsiadów; pozostałe kilkadziesiąt jest oddalone od innych.
Czy to ma coś wspólnego z
https://en.wikipedia.org/wiki/Maximum_independent_se
t#Finding_maximum_independent_sets

do góry

On Friday, February 6, 2015 at 1:15:43 PM UTC+1, Borneq wrote:
> Mamy kilkadziesiąt - sto punktów. Należy znaleźć grupy punktów, np.
> piątki punktów które leżą blisko siebie, takie "kliki", gdzie mamy
> bliskich sąsiadów; pozostałe kilkadziesiąt jest oddalone od innych.
> Czy to ma coś wspólnego z
> https://en.wikipedia.org/wiki/Maximum_independent_se
t#Finding_maximum_independent_sets

Raczej http://en.wikipedia.org/wiki/Category:Data_clusterin
g_algorithms,
np. http://en.wikipedia.org/wiki/K-means_clustering

w.

do góry

W dniu 2015-02-06 o 13:32, Wojciech Muła pisze:
> On Friday, February 6, 2015 at 1:15:43 PM UTC+1, Borneq wrote:
>> Mamy kilkadziesiąt - sto punktów. Należy znaleźć grupy punktów, np.
>> piątki punktów które leżą blisko siebie, takie "kliki", gdzie mamy
>> bliskich sąsiadów; pozostałe kilkadziesiąt jest oddalone od innych.
>> Czy to ma coś wspólnego z
>> https://en.wikipedia.org/wiki/Maximum_independent_se
t#Finding_maximum_independent_sets
>
> Raczej http://en.wikipedia.org/wiki/Category:Data_clusterin
g_algorithms,
> np. http://en.wikipedia.org/wiki/K-means_clustering

Dzięki, przyjrzę się

do góry

On Fri, 06 Feb 2015 13:17:26 +0100, Borneq
<b...@a...hidden.pl> wrote:
> Mamy kilkadziesiąt - sto punktów. Należy znaleźć grupy punktów, np.

Swego czasu była książka na ten temat, Algol, "Analiza skupień" czy
jakoś tak.

Zwróć uwagę: bliskie (metryka euklidesowa) punkty są bliskie co do X
i zarazem bliskie co do Y. Posortuj.

do góry

On Friday, February 6, 2015 at 1:15:43 PM UTC+1, Borneq wrote:
> Mamy kilkadziesiąt - sto punktów. Należy znaleźć grupy punktów, np.
> [...]
> Czy to ma coś wspólnego z

Formalnie, dla jednej grupy, jak takie zadanie powinno być zdefiniowane?
Znaleźć obszar 2D o najmniejszym polu, zawierający 5 punktów? A może
znaleźć 5 punktów pomiędzy którymi suma odległości (czyli suma 10 liczb) jest
najmniejsza? A może suma kwadratów? Dla N grup, odpowiednio, znaleźć N
obszarów, lub N sum?

Pięć punktów ze 100 można wybrać na 75mln sposobów, jeśli nie masz dużo
takich zadań, to siłowo bez problemu dasz radę.


Pozdrawiam

do góry