[megoldva] Algoritmus csoportképzésre

Fejlesztés

Van valami bevett algoritmus a következő feladat megoldására?

Adott néhány entitás, mondjuk város, és mindegyiknek van többfajta azonosítója: id1, id2, id3, ... idn.
(Nem biztos, hogy minden városnak van minden azonosítóból.)
Szeretnénk egy csoportba sorolni azokat, amelyeknek valamelyik azonosítója megegyezik.

Példa:

Ajka - a - 1
Baja - b - 2
Cikó - b - 3
Dány -   - 3
Ebes - d -

Itt Ajka az egyik csoport, Baja-Cikó-Dány a másik, Ebes a harmadik.

Szerk1: így fest egy egyszerűcske megoldás: http://pastebin.com/dGBxWRtg - azért csak egyszerűcske, mert egy városnak csak egy sora lehet.

Szerk2: Kár, hogy senki nem írta azt, hogy "ó, hát az Algoritmusok könyv 384. oldalán (22.1.1 Diszjunkt-halmaz adatszerkezetek alkalmazása) pont ezt írják le".

  • 1185 megtekintés

( SzBlackY | 2017. 01. 14., szo – 08:27 )

Mi van, ha egymásnak ellentmondó adataid vannak? Pl. a fentiben Dány kap egy d azonosítót, akkor kérdés, hogy melyik lesz a helyes: {{Ajka}, {Baja, Cikó}, {Dány, Ebes}} vagy {{Ajka}, {Baja, Cikó, Dány}, {Ebes}} vagy {{Ajka}, {Baja, Cikó, Dány}, {Dány, Ebes}} (< ez tűnik leglogikusabbnak, amikor egy-egy elem több halmaz része is lehet)?

BlackY
--
"en is amikor bejovok dolgozni, nem egy pc-t [..] kapcsolok be, hanem a mainframe-et..." (sj)

( csortu v | 2017. 01. 14., szo – 08:41 )

Én ezeket az adatokat, mint egy hálózat fognám föl, ahol a hálózat csomópontjai a városok. Két város között akkor van él, ha van közös azonosítójuk. (Ízlés szerin lehet súlyozni az éleket a közös azonosítók száma alapján, ha van ennek értelme a pproblémánál.) Egy ilyen hálózatnál két eset van:

1.) Az adatok ellentmondásmentesek, azaz nincs olyan azonosító, ami adott várost az egyik csoporthoz, míg másik azonosító másik csoporthoz sorolja. Ekkor egyszerűen meg kell nézni, hogy az egész hány, egymással nem kapcsolt alhálózatra esik szét, azok a nem kapcsolt alhálók a csoportjaid.

2.) Az adatok nem ellentmondásmentesek, azaz lesz olyan város, ami egyik azonosító szerint az egyik, míg a másik azonosító szerint egy másik csoporthoz tartozik. Ekkor lesznek csoportok, amik főleg egymással kapcsoltak, de néhány kapcsolat van közöttük is. Egy ilyen gráfot vizualizálva általában könnyű megtalálni és kijelölni a csoportokat, ha nem túl sok ellentmondásos adat van. Ha sok van, akkor community analízist csinálnék, ami ízlés szerint kijelöli a csoportokat.

Az egészet elég könnyű megcsinálni R-ben az igraph csomaggal.

Csaba

--
Csaba

Köszi az ötletet és a meglátást a gráfelméleti párhuzammal!

Annyit fűznék hozzá, hogy az ellentmondásosság kérdése nemigen kerül elő, mert nem jelent gondot akárhány város összekapcsolása sem. Végletes esetben egyetlen csoportunk lesz, ami minden várost tartalmazza (vagy a másik véglet, hogy mindenki önálló csoportban van.)

A példánkat módosítva:
- ilyen esetben egyetlen csoportunk van, amiben A, B, C, D, E is benne van:

Ajka - a - 1 - x
Baja - b - 2 - x
Cikó - b - 3
Dány - d - 3
Ebes - d -

- ilyen esetben pedig öt csoportunk van, külön A, külön B, külön C, külön D, külön E számára:

Ajka - a - 1
Baja - b - 2
Cikó - c - 3
Dány - d - 6
Ebes - e - 8 - x

( joco01 v | 2017. 01. 14., szo – 10:28 )

Legyen az azonosítók száma N, a városok száma M. Minden azonosítót cserélj le egy pozitív számra, 1-től indulva max M-ig. Ehhez minden azonosítón és minden soron végig kell menni, közben egy Map struktúrát kell építeni minden azonosító esetén. Ez O(NM). Utána minden egyes városon végigmész megint. Azt fogod látni, hogy egy város több csoporthoz is tartozik. Egy Map-ben eltárolod ezekre a csoportszámokra páronként, hogy a nagyobb szám a kisebbhez tartozik. Pl. Ajka 4 1 2 esetén 4->1 és 2->1, tehát Ajka város miatt az 1, 2 és 4 csoport ugyanaz, és 1-nek fogjuk hívni. Gyakorlatilag így vonjuk össze a csoportokat. Adott esetben néhol egyszerűsíteni lehet majd, pl. egyszer elteszed, hogy 4->2, utána 2->1, akkor 4->2->1 egyszerűsítve 4->1. Ez talán O(MN^2) vagy O(MNlogN), nem vagyok biztos benne. Végül ez a Map adja meg minden városhoz, hogy melyik csoporthoz tartozik.

Másik megközelítés. Minden azonosítót beindexelsz azonosító->városok kereséshez (Map>). Megfogod az első várost, beteszed egy egy elemű halmazba. Az összes azonosítóján végigmész, és mindegyikhez megkeresed a többi várost, aki rendelkezik ugyanavval az azonosítóval. Beteszed őket is ebbe a halmazba. Utána végigmész az újonnan betetett városokon, és ismételsz. Egészen addig, amíg már nem találsz többet. Utána mész a következő városra, ami még nincs csoportba rendelve, és kezded elölről. Tippre itt is a fentihez hasonló lesz a futásidő. Kicsit bonyolultabb adatstruktúrák vannak itt, de kicsit egyszerűbb lekódolni.

--

Köszi az ötletet!!! Az első algoritmus király, azt valósítottam meg először.
Aztán, amikor kiderült, hogy egy városhoz több sor is tartozhat, ily módon lehet olyan várospár, amelyik csak egy harmadik város révén tartozik össze (de egymással nincs közös azonosítójuk), mégis a második stratégia lett jobb.

Egy időre picit elcsábított az az irány, csortu révén, hogy fogjam föl gráfként, és számoljon helyettem az R (igraph), mert akkor egyszerűen annyi lenne a teendő, hogy oszloponként végigmenni, és a megegyező azonosítójú városokat összekötni, s a végén megnézni, kik az összefüggő gráfok. De még átgondolom, melyik is az egyszerűbb (és több százezer város + 20 azonosító esetén melyik a működőképes).

Kösz még egyszer mindenkinek, aki segített ezt végiggondolni.