NézetNyomtat

Szigetek
Címkék > Feladat
Címkék > Hiányzó algoritmus

Szigetek

A feladat alapötletét Oláh Gábortól kaptam, aki beszédfelismerés kapcsán találkozott a probléma egy magasabb dimenziós változatával.
Az egyszerűsített változat:
Adott véges sok pont a síkon, egész koordinátákkal. Csoportosítsuk a pontokat "szigetekre".

Példa

Az alábbi első ábrán látható ponthalmazt a legtöbb ember a második ábrán látható módon csoportosítaná.

A kérdés pontosítása

Nem definiáltuk, mit jelent a "sziget", és rövid gondolkozás után látható, hogy a definíció egyáltalán nem nyilvánvaló.

Küszöbszámokkal

Távolságarányokkal

Alkalmazások

Web-keresők találatainak csoportosítása

Az egyik érdekes alkalmazás a következő: a web-keresések rengeteg találatot ("pontot") adnak, jó lenne ezeket a találatokat csoportosítani, és a csoportokat megjeleníteni. Ha definiálni tudunk a talált weblapok ("pontok") absztrakt terében egy jó távolság mértéket, akkor egy "sziget-kereső" (clustering) algoritmus segítségével csoportosíthatjuk a találatokat.

Beszédfelismerés

Szakirodalom

Tesztadat

91 36
43 92
401 136
182 72
361 241
420 238
120 293
57 337
110 349
185 358