Algoritmus-segítség (programozás)

 ( yorkeetech | 2018. február 9., péntek - 16:53 )

Sziasztok!
Segítséget szeretnék kérni, szükség lenne valamilyen algoritmusra, ami képes a következőre:
Adott egy adathalmaz, embereket szimbolizál, minden embernek vannak adott készségei pontozva 1-5ig terjedő skálán. Kellene egy algoritmus, ami képes munkacsoport-beosztás szerűséget készíteni úgy, hogy a készségeik alapján leginkább hasonló képességű emberek kerüljenek párba. Kellene hozzá egy paraméterezhető tűréshatár, tehát mondjuk általánosságban a 2 pont differencia elfogadható, ha nem érint többet, mint a készségek 50%-a. Ráadásul elég sok emberrel kellene számolni, illetve gyakran változó készségekkel és állománnyal, tehát a gyorsaság is szempont.
Remélem nem túl ködös, gondoltam már valamiféle Élő-pont számításra, vagy a készségek alapján valamiféle hash-mezőt kellene készíteni, viszont ebbe nem nagyon lehet beletenni a a készségek hasonlóságát illető tűréshatárt. Van valakinek esetleg valami ötlete?
Előre is köszi.

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Hány fajta képesség van? Muszáj mindenkit beosztani? Mekkora méretű csoportok kellenek?

Olvasnivaló: https://en.wikipedia.org/wiki/Clustering_high-dimensional_data

Köszi, ez jó olvasmány volt.
A képességek száma elég sok, a példa kedvéért legyen mondjuk negyven. A csoportok mérete nem igazán releváns, igazából a jól együttműködő párok összeállítása a lényeges. Mindenkit nem muszáj beosztani, a probléma egyszerre egy személyre vonatkozik, tehát mindig egy személynek kell megfelelő partnert találni a még pár nélküli személyek közül. Tulajdonképpen amire szükségem van valóban egyfajta klaszteranalizis, amiben a negyven képességet le lehetne vezetni egy olyan könnyen kereshető, egydimenziós adatra, ami alapján az adott eltérési határértékeken belül mellé lehetne csapni egy másik személyt. Az olvasmány tényleg hasznos volt, jött belőle ötlet, köszi :)

----------------
Bruce Lee

Az Adatbányászat c. könyv elég részletesen tárgyalja a problémát.

> Sol omnibus lucet.

Utánanézek, köszi :)

----------------
Bruce Lee

Megvan, hogy hány csoport kell, melyik csoportnál melyik készség a fontos, mekkora max egy csoport?

Igazából ezek jelenleg nem lényegesek, a fókusz ott van, hogy egy adott személynek válasszon az algoritmus egy másik személyt párnak, aki nagyjából ugyanazon a szinten van a készségek terén. Tehát a csoportméret igazából nem fontos, mert két fős csoportok képezik az alapját mindennek, illetve előfordulhat olyan, hogy valakinek nincs párja, nem kötelező mindenképpen találni alkalmas személyt.

----------------
Bruce Lee

De nem biztos, hogy az első megoldás kell, ami épp megfelel, ha van annál optimálisabb. De mennyi ideig keresed (brute force, össze permutáció) az ideális esetet? Mennyivel lennél elégedett? Végig lehet-e játszani minden kombinációt életszerű idő alatt? Ha egyforma megoldások vannak, akkor lehet-e finomítani a megoldást (korábban párban voltak, most is legyenek egy pár).
Operációkutatás a barátunk.

Operációkutatás a témakör.

Jó lenne kicsit több információ :-)

Az bizony, csak kicsit vakon vagyok benne :)

Igazából a válaszokban mindent leírtam, amit tudok a problémáról, alapvetően két fős csoportot kell összeállítani hasonló képességű tagokkal. Előfordulhat olyan, hogy valakinek egyszerűen nincs párja, ezt az esetet majd külön kezeljük.

----------------
Bruce Lee

A graphviz ezt ugy csinalja (oke, az az idealis kirajzolast), hogy rugoero csillapitast vegez a node-ok kozott.
Ledob egy kvazi random felallast, majd megprobalja lazitani az edge-ek mint rugok feszultseget. Ha talal kisebb ossz-feszultsegu iteraciot egy adott delta felett, akkor atvalt ra.

Te is csinalhatnad azt, hogy csinalsz egy random beosztast, majd a csoporteltereseket probalod minimalizalni. Ha talalsz jobb felallast, elmesz oda. Ilyen (kvazi) egyzeru algoritmust meg _talan_ stored procedure-ban is meg tudsz csinalni.

Ha jol ertem a feladat, egy forditott legkisebb negyzetek modszeret szeretnel csinalni, sok idezojelben.

(Lehet, hogy akinek csak kalapácsa van az mindent szögnek lát, de) én valamilyen evolúciós algoritmussal állnék neki.

+1

+1
egy pár jósága kijön a két n-dimenziós pont távolságából, a teljes halmaz pedig akkor állt be, ha a pár nélkül maradtak száma a lehetséges minimum.

Eléggé alulspecifikált a feladat. Nem világos, hogy egyik megoldás mikor jobb egy másiknál.

Habár a képességek egészekkel vannak leírva, a képességek vektora tekinthető az n-dimenziós tér egyik pontjának.
A feladat szerint párokba kellene sorolni a pontokat. A hagyományos euklideszi távolságfogalom mellett itt szóba jöhet a Manhattan, vagy a Csebisev távolság is, amikor a dimenziók menti eltérések összegét illetve maximumát kell tekinteni.

Ha minél közelebbi párok elérése a cél:
Mohó módszerrel lehetne tekinteni azokat a párokat, ahol a legkisebb a távolság, s ezeket a párokat eltávolítani a rendszerből. Ez mehet mindaddig, amíg el nem érjük a "tűréshatárt". Ekkor már minden pont izoláltnak tekinthető, újabb pár nem alakítható ki. Ezért tekintjük ezen izolált pontok halmazát, és miután az eddig eltávolított pontpárokat visszaadjuk az izolált pontokhoz, az izolált pontok mindegyikéhez hozzárendeljük a legközelebbi pontot. Végül a megmaradt pontokra újra a legkisebb távolságok szerint rendezve kapcsolhatjuk össze.

Ha az a cél, hogy minél kevesebb munkatárs maradjon pár nélkül:
A legközelebbi szomszéd távolsága szerint csökkenő sorrendben érdemes sorba állítani a pontokat, és ebben a sorrendben kell a az egyes pontokhoz párt találni (természetesen a hozzá legközelebbit), majd haladni a többiekkel. Ha igazán szépen akarunk haladni, a már kötött párok elemeihez tartozó távolságokat el kell felejteni, és eszerint a maradék sort újrarendezni. Ez már jelentősen ronthat a hatékonyságon. Bár az egyes ponttól mér távolságokat kupac/heap segítségével nyilvántartva, egy-egy pont törlése viszonylag olcsón megúszható.

Tulajdonképpen a "minél közelebbi párok" elérése a cél, így az a rész amit írtál teljesen jó is. Inkább az a szűk keresztmetszet, hogy ha majd több ezer párt kell összeállítani, akkor ott hogyan lehetne a futásidővel kicsit takarékoskodni.
Én arra gondoltam, hogy az n+1 képességet csoportosítom/összevonom valamiféle reláció alapján, ezekből kapok egy indexet, értéket, pontszámot, így már csak (n+1)/5 értéket kell vizsgálni, az összevonásnál már ügyelek a tűréshatárra, így ez elfogadható pontosságot eredményez majd, (n+1)/5 értéket pedig gyorsabb és könnyebb lesz majd vizsgálni, mint az eredeti mennyiséget.
Ha pedig még pontosabb szűrésre lesz igény, az összevont pontszám akkor is megfelel a kezdő intervallum szűkítésére.

----------------
Bruce Lee

Ha mohó módon kell alkalmazni a legközelebbi szomszédot, akkor a hagyományos keresőfa kiterjesztése lehet a megoldás: https://en.wikipedia.org/wiki/K-d_tree

Viszont mohó módon dolgozva a sorban hátul lévő (azaz izolált) elemeknél nagyon nagy távolság is előjöhet.

Az a kérdés, hogy az párok távolságának szummájára vagy maximumára kívánunk optimalizálni.

https://hu.wikipedia.org/wiki/Legkisebb_n%C3%A9gyzetek_m%C3%B3dszere

Két ember képességeinek a különbségének a négyzetösszegét kell kiszámolni, majd ha van egy sorrended a lehetséges párokról, akkor ezek közül kiválasztod azt, ami az egyéb feltételeid szerint legjobb.

Ha jól értem, itt volna egy vezértulajdonság, ami a párpotentátokat kijelöli, és a többi tulajdonság csak mint másod-harmad-satöbbirendű tulajdonság határozná meg a pár jóságát.

Így ha a Tv vezértulajdonság különbsége nagy, ezért nem hozza össze A-t és B-t lehetséges párként, akkor a T1, T2, T3... tulajdonságok összege hiába volna esetleg jobb, mint amivel a Tv a többi párt összeköti, A és B sosem lesz párban.

Szóval nekem úgy tűnik, itt elvész a feladat sokdimenziós jellege, ami az izgalmát adja.

Mit ertesz vezertulajdonsag alatt? Azt amelyiknel a legnagyobb a kulonbseg? (a feladat szerint egyebkent nem lehet tul nagy a kulonbseg az egyes tulajdonsagok kozott).

ha valami ilyesmi az adatszerkezet, és a képességekre van egy táblázat, valami ilyesmit tudnék elképzelni (hasraütésre rögtönözve, a teljesség minden igénye nélkül) a teljes egyezésre:

ember record {
.azonosito:string;
.kepesseg[] array of byte;
}

emberek[] array of ember;

par record{
.p1,p2:egesz;
}

parok[] array of par;

pp=0;i=0;j=0;k=0;

while (i;i<=maxemberek;i++){
.while (j;j<=maxemberek;j++){
..while (k;k<=maxkepessegek;k++){
...if emberek[i].kepesseg[k]=emberek[j].kepesseg[k] {pp++; parok[pp].p1=i; parok[pp].p2=j;}
..}
.}
}

további feltételek beiktatásábal pl. ha az adott képességben az egyiknek egyel kissebb pontja van, akkor alkosson még egy párt:

if emberek[i].kepesseg[k]-1=emberek[j].kepesseg[k] {par.p1=i; par.p2=j;}

ezekután már csak ki kell gyomlálni ha egy ember önmagával van párban, meg a duplikált párokat pl. {par(107,250) par(250,107)}

sőt, még meg is lehet számolni, hogy egy párnak hány egyezése van

-fs-
Az olyan tárgyakat, amik képesek az mc futtatására, munkaeszköznek nevezzük.
/usr/lib/libasound.so --gágágágá --lilaliba

Classical Multidimensional Scaling.
Csinálsz egy táblázatot, a sorok az emberek, oszlopok a tulajdonságok.
Súlyozod ahogy szeretnéd, majd normalizálsz.
Ekkor jöhet a CMDS, mondjuk csinálsz belőle 3d-s adatot.
a tengelyeknek nem lesz értelmük, de a művelet távolság aránytartó.
tehát akik közel vannak azok közel is maradnak, csak a sok dimenziós adatokból ez nem látszik
Kb minden ami kell hozzá implementálva van, pl. ; R, julia, matlab...stb nyelvekbe

Szerintem ez nagyon egyszerű. Két lépésben kell csinálni:

1) Az eredeti feature matrixban az emberek a sorok, a tulajdonságok az oszlopok. Ezt konvertálod távolság mátrixszá: két ember távolságát többféleképpen definiálhatod, legegyszerűbb, ha szimplán euklideszi távolságot számolsz, de használhatsz egyéb metrikákat is (tapasztalat alapján fölösleges), vagy ha vannak a többinél fontosabb tulajdonságok, akkor súlyozhatsz is akár.
2) A távolságmátrixból egyszerű iterációval kiszedegeted a párokat. Minden iterációban keresel egy párt, amik között a legkisebb a távolság (ha több ilyen van azok közül random módon választasz); a párt eltárolod; a páros résztvevőit eltávolítod a mátrixból. Ezt az iterációt addig folytatod, amíg egyetlen pár, vagy egyetlen ember marad.

Ha mindig csak egy emberhez kell párt találni, akkor is legenerálod a távolságmátrixot, és adott emberhez kiválasztod a legkisebb távolságra található embert (ha többen vannak, random választasz közülük). A létrejött párokat törlöd a távolságmátrixból.

Ez a megoldás egyszerű, nagy számú emberrel is veszett gyors, és elég jó eredményt ad.

(Bioinformatika után érdeklődőknek: a filogenetikában használatos UPGMA módszer adaptációja párképzésre.)

--
Csaba

https://en.wikipedia.org/wiki/Assignment_problem

Van egy matrixod, aminek a sorai es az oszlopai az emberek. Az egyes elemei az adott emberpar osszerendelesenek a koltsege (tehat a kepessegeik kozotti elteres nagysaga). Nyilvan a foatloban +vegtelen szerepel mindenhol.

N elemet kell kivalasztani ugy, hogy sem a soraikban sem az oszlopaikban nincs atfedes es a kivalasztott elemek osszege minimalis. SZTE Operaciokutatas tankonyben benne van az algoritmus, eleg egyszeru.

Valószínűleg valóban ez a legegyszerűbb.

> Sol omnibus lucet.

Jaigen, eszembe jutott a megoldasi algoritmus neve is: Magyar-modszer (https://en.wikipedia.org/wiki/Hungarian_algorithm)

Ez erosen polinomialis idoben oldja meg a problemat es megtalalja a globalis minimumot. Szoval a genetikus algoritmusoknal jobb eredmenyt ad es gyorsabban.

Optimum keresés: Holographic Research Strategy. Szintén magyar módszer. (-::

> Sol omnibus lucet.