Módszerek csatája
2011-01-28T20:09:32+01:00
2011-01-31T12:26:38+01:00
2022-07-01T13:05:57+02:00
  • Kerdes: Az A modszert at lehet-e alakitani apro muveletek sorozataval B modszerré?

    Ha igen, akkor folyamatos atalakitasok, es hatekonysagok meresevel hosszutavon kozelithetunk az optimalis modszerhez. (Ha zsakutcak vannak, akkor tobb randomot bele!)

    Tehat van egy A modszerunt, ebbol tudjuk az An-bol vegrehajthato elemi modositasok halmazát és ebbol a halmazbol kell kivalasztani a legjobbat, aztan johet a kov. optimizalas. Ez lenne az egyszintes kereses, de lehetne tobbszintes is a feladatol fuggoen.

    Na ez nalam asm utasitasok idealis sorrendjenek keresésénél segített, igaz ott sem látta a gép az egész feladatot egyszerre (tul sok variacio), csak lokalisan optimizalt (16 utasitast latott elore, aztan ha azok kozul megvolt a legjobb idô, lépett tovabb 1-el)
    Mutasd a teljes hozzászólást!
  • Igen valószínű hogy igaz a feltételezésed és összehasonlító rendezést is rá lehet engedni. A probléma továbbra is a nagy n-ekkel és m-ekkel van.

    Közben írtam egy kis algoritmust javaban ami kiszámolja a dolgokat. Korábbi példánkban
    A = {1,2,500}
    B = {5,6,7}
    ekkor A várható eredményessége -0.33

    Azonban érdekes, hogy mi van akkor, ha 2 fordulón át választhatunk e két módszer közül, és csak az számít, hogy a végére kinek lesz nagyobb az egyes fordulókban szerzett pontszámok összege?! Ekkor ha mindkétszer az A módszert választjuk:
    AA = {2,3,501,3,4,502,501,502,1000} , ha mindkétszer B-t:
    BB = {10,11,12,11,12,13,12,13,14}
    Majd ha összemeccseltetjük őket, azt kapjuk hogy AA jobb lett, eredménye: +0.11
    Tehát fordult a kocka, egy forduló alatt A rosszabb, de kettő után már jobb! De mi van ha egyszer az A-t, egyszer pedig B-t választom:
    AB = {6,7,8,7,8,9,505,506,507}
    AA ez utóbbitól kikap: -0.185
    BB viszont legyőzi +0.33

    Ez eléggé körbeverés szagúnak tűnik, tehát lehet hogy mégsem lehet összehasonlító rendezést ráengedni, ám még érdekesebb hogy akkor most mi van, melyik módszer is a legjobb?

    AA-AB -0.185 , AA-BB +0.11 , AA = -0.075
    AB-AA +0.185 , AB-BB -0.33 , AB = -0.145
    BB-AA -0.11 , BB-AB +0.33 , BB = +0.22

    Tehát végülis BB a legjobb, kivéve ha ellenfelünk tudja hogy ezt alkalmazzuk, mert akkor AA-val lever minket
    Remélem jól számoltam. Kezd érdekes lenni a dolog ha igen...
    Mutasd a teljes hozzászólást!
  • Ami érdekes kérdés, de nem láttam még be, hogy P(A,B) relációként rendezés-e, vagyis igaz-e hogy:

    P(A,B) > 0.5 és P(B,C) > 0.5 -> P(A,C) > 0.5

    Ha igen, akkor nyilván valamely ismert összehasonlító rendezőalgoritmust használva átlag O(m*log(m)) összehasonlítást használva (m a módszerek száma) berendezhetjük az összes módszert ahol egy összehasonlítás az előző hozzászólásomban meghatározott O(n*log(n)) lépésből áll.

    Ekkora teljes futásidő:

    O(n*m*log(n)*log(m))

    ahol n a legtöbb kimenettel rendelkező módszer kimeneteinek száma, m a módszerek száma.

    (Ha azonban a fenti nem látható be, akkor az összehasonlító rendezés nem használható, kénytelenek vagyunk O(m*m) összehasonlítással megkeresni a legjobbat )
    Tulajdonképpen ugye m*m*n*log(n) idő alatt a teljes, a módszerek közötti valószínűségmártixot kiszámolhatjuk . Ha ezt eltároljuk, utána elég ezzel számolni bármilyen eredményességi mutatót.
    Mutasd a teljes hozzászólást!
  • Szia!

    Nem sokat gondolkodtam rajta, de a következőt vettem észre:

    Ahogy észrevettétek egy módszernek az eredményességét egy számba sűríteni nem trivi.

    Viszont legalább egy módszer egy kimenetelének könnyen megmondható az eredményessége egy tlejes másik módszer ellen.

    Pontosabban A és B módszerek esetén A módszer k kimenetlére megmondható, hogy mekkora valószínűséggel veri B módszert.

    Ezt jelölhetjük:
    P(A,k,B)

    -vel. Kiszámítása nyilvánvaló: kiszámoljuk hogy 'k' B kimeneteli közül hány darabnál nagyobb és elosztjuk B kimeneteleinek számával. (Az egyezőségeket csak 0.5-ös szorzóval adjuk hozzá)

    P(A,k,B) ekkor O(log(n)) időben számolható, hiszen B kimeneteleit nagyságszerint egy tömbben tartjuk: log(n) ideig tart mire kikereesük a minket érdeklő tömbindexet (k hány elemnél nagyobb...)

    Jelüljük A nyerési esélyét B ellen P(A,B)-vel.

    P(A,B) = szumma minden k-ra P(A,k,B) / (A kimenteinek száma)

    Vagyis P(A,B) egzakt kiszámítása megoldható O(n*log(n)) időben.
    ahol n A és B kimenteleinek számának maximuma.
    Mutasd a teljes hozzászólást!
  • Igen, nagyon jó a példa, teljesen hasonlót akartam felhozni!

    Eddig összeszerzett tudásanyagomból azt gondoltam volna hogy egy optimális stratégia elég ha veszi az értékek számtani átlagát és azt igyekszik maximalizálni. Ám példádból is kitűnően látszik, hogy az könnyen legyőzhető, ezért is írtam ide, hátha valaki ismeri ennek az elméletét.

    Az hát a problémám egyik része, hogy átlagolás helyett miként lehetne egyszerűsíteni a dolgon. Mert az átlagolás amúgy praktikus lenne, mivel tízmillió adatból is egyet csinál. Csak épp túl nagy hibával.

    A tournament módszerrel nincs semmi baj, ha azt értjük alatta, hogy például körmérkőzést játszatunk, vagyis az A módszer minden lehetséges kimenetelét megmérkőztetjük a B módszer minden lehetséges kimenetelével és szépen kiszámoljuk a végeredményt. Ez a triviális megoldása a feladatnak, csak megint az a baj, hogy ha a módszerek mindegyike 10 az 50-ediken kimenetelt tartalmaz, akkor ez nem egy járható út , egyéb esetekben meg megint jön a hiba.

    Szóval valami frankó egyszerűsítés kellene szerintem.
    Mutasd a teljes hozzászólást!
  • Ha a bonyolult sakk tournament rendszerek sem johetnek szoba, amik elvileg jol megbirkoznak azzal a helyzettel, ha valaki az egyik meccs elott bal labbal kelt fel. Szoval, te jol ismered a sakk tournamenteket, akkor nekem halvany lila gozom sincs mi ez a feladat.

    Ha kulon objektiv modon lehetne kiertekelni a modszereket, akkor pontszam alapjan mehetne, de ahogy irod, itt 2 modszert kell megmérettetni, ha azok elegge osszevissza mennek, akkor sok fordulo kell:

    Pelda: van 2 modszerunk es egyenlo valoszinuseggel ilyen eredmenyesek lehetnek:
    A:(1,2,500) <- A 1/3 aranyban nagyon folenyesen tud nyerni, amugy bena
    B:(5,6,7)

    A meccs lehetseges eredmenyei:
    1 - 5 -> B
    1 - 6 -> B
    1 - 7 -> B
    2 - 5 -> B
    2 - 6 -> B
    2 - 7 -> B
    500 - 5 -> A
    500 - 6 -> A
    500 - 7 -> A

    Hiaba van ott az a nagyon jo 500-as eredmeny, de hosszutavon B fog nyerni.

    Mutasd a teljes hozzászólást!
  • Nos engem valójában csak a két résztvevős eset érdekelne, tehát egy ellenfelet kellene legyőzni, ez gondolom az egyszerűbb eset is egyben.

    A véletlen összesorsolós módszer nyilván nem rossz, de nem oldja meg a problémát, ami miatt nyitottam ezt a diskurzust. Vagyis ha a módszereknek sokféle kimenetelük lehet (vagy sok a forduló), akkor túl sokáig tartana így elfogadható hibahatáron belül megjósolni a végeredményt, vagy fordítva, másodperc töredéke alatt a kis eltérést mutató módszerek közül rosszul választana.

    A sakkversenyek sorsolási szisztémáit jól ismerem mesterjelöltként, még programot is írtam a svájci és körmérkőzéses rendszerekre ultiversenyekhez, de azt sem látom hol segítene.

    Egyébként rémlik az egyetemről valami tournament dolog, de már nem emlékszem az pontosan miről is szólt mert csak az egyik tanár említette egyszer véletlenül.
    Mutasd a teljes hozzászólást!
  • Hi! Tournament a modszerek kozott szoba johet? (Mint pl. a foci VB) Veletlen szeruen osszesorsolt modszerekkel, minnel tobb ilyen tournament es amelyik modszer lesz a vegen legtobbszor az elso, valoszinuleg hosszu tavon az lesz a leghatekonyabb is.

    Vagy itt vannak még bonyolultabb tournament rendszerek-> Category:Chess tournament systems - Wikipedia, the free encyclopedia
    Mutasd a teljes hozzászólást!
  • Üdv!

    Legyenek adottak módszerek, amik közül lehet választani. Mindegyik módszernek ismerjük a lehetséges kimeneteleit, melyek egyszerű pontszámok (legyen az értéktartomány [0..500] vagy valami hasonló), és azonos valószínűséggel fordulhatnak elő, ha ezt a módszert választjuk. Egy pontszám többször is előfordulhat egy módszer eredményeként.

    Két módszer közül legyen az a jobb, amit ha kiválasztok, várhatóan leghatékonyabban legyőzi a többi lehetséges módszert.
    Egyik módszer akkor győzi le a másikat, ha kiválasztva belőle egy véletlenszerű pontszámot, az várhatóan nagyobb lesz, mint a másik módszerből véletlenszerűen kiválasztott pontszám. Illetve a győzelem legyen +1, a döntetlen 0, a vereség pedig -1 értékű.

    A kérdés: melyik módszert válasszuk? Hogyan állapítható meg leggyorsabban, hogy melyik a legjobb módszer, valamint ennek mennyi a várható értéke a többi módszerrel szemben?

    Ha a módszerek közül nem csak egy, hanem több fordulón át válogathatunk, és csak az számít, hogy a fordulókban szerzett pontszámok összege kinek lesz a végén nagyobb, akkor mi a helyes taktika? Hogyan kell módszereket összevonni?

    A probléma: a módszerek lehetséges kimenetelei (pontszámai) lehetnek nagyon sokan is (főleg összevonások után). Azokat sem eltárolni, sem összehasonlítani nem költséghatékony.
    Létezik-e mód az egyszerűbb kezelésre? Mi lehet a legjobb egyszerűsítés?
    Van-e ennek már meglévő elmélete?
    Mutasd a teljes hozzászólást!
abcd