Optimointitehtävä

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Pienin tunnettu lottoharava sisältää 329 riviä, joka antaa 100 prosentin varmuudella aina vähintään yhden 4-oikein tuloksen. Teoreettinen minimiharava 4-oikein tulokselle voisi kuitenkin olla reilusti alle 100 riviä.

Miksi kukaan ei ole pystynyt tekemään tuota mahdollisimman lähellä teoreettista minimiä olevaa haravaa vähintään 4-oikein tulokselle? Nykyaikana tietokoneiden muisti ja teho eivät enää olisi pullonkauloina.

-torstai

Sivut

Kommentit (77)

Vierailija

Et varmaankaan tarkoita veikkauksen valmiita haravia, koska jopa 18 rastin haravassa on kohtuullinen mahdollisuus, ettei arvotussa rivissä ole neljää oikein. On jopa mahdollista, ettei ole yhtään oikein! Haravasi koostuu siis vähintään 36:stä (luultavasti kaikista 39:stä) mahdollisesta numerosta, jotta tuollainen voidaan taata. Ihan uteliaisuuttani: missä olet törmännyt moisiin haraviin?

Vierailija
torstai
Teoreettinen minimiharava 4-oikein tulokselle voisi kuitenkin olla reilusti alle 100 riviä.

Jos tarkoitat sitä, että todennäköisyys saada yhdellä rivillä vähintään 4 oikein on n. 1/89, niin tätä 89:ää ei käsittääkseni voi pitää teoreettisenä miniminä. Toki se on raja, jonka alle ei voi millään päästä, mutta luulen teoreettisenkin minimin olevan korkeampi. Tämä tosin on vain "mutua", enkä ole laskenut sitä mitenkään.

maalaisukko
Seuraa 
Viestejä495
Liittynyt15.10.2006

Tein kerran tietsikalla ohjelman nimellä "lottosimulaattori". Se oli ohjelma jolle syötettiin "viikon oikea rivi" jota kone lähti sitten tekemään. Ohjelma ylläpiti tilastoa tuloksista. Tilastoa lisänumeroista ei siihen sisältynyt. Ohjelmassa oli tila johon laitettiin simuloitava lotto-ohjelma. Lähdinkin etsimään ohjelmaa joka tekee juuri 4-oikein tuloksen mahdollisimman pienellä rivimäärällä.
Kun simulaattorissa testasin lotto-ohjelmaa joka valitsi numerot pelkästään satunnaisluku-generaattorilla vaadittiin silloin keskimäärin 74 riviä 4-oikein tulokseen. Erilaisia ehtorakenteita käyttämällä ohjelmaan sai "älykkyyttä" jolloin pääsi 4-oikein tulokseen keskimäärin 40 rivillä. Esim. ei kolmea peräkkäistä numeroa. Max. kolme numeroa välillä 1-13, 13-26, 26-39. Rivien välinen ehdollinen vertailu. Tilasto käytetyistä numeroista jne.
Kumminkin liian mutkikas ja tiukka ehtorakenne huononsi tulosta. Myös tehtyjen rivien lukumäärä suhteessa ehtorakenteiden laajuuteen antoi huonomman tuloksen.

Siihen aikaan oli tietsikat 8-bittisiä ja toimivat muutaman megan kellotaajuudella. Muistaakseni kone simuloi n. 20000 riviä vuorokaudessa. Kuvaavaa on, vaikka kone pyöritti ohjelmaa viikonkin yötä-päivää ei koskaan tullut 7-oikein tulosta.

Siitä vaan lotto-ohjelmaa tekemään. Älkää kumminkaan laittako simulaattorin ohjeriviksi sitä viikon oikeaa, ettei jälkeenpäin harmita kun ei tullut kuponkeja vietyä.

Ilmeisesti lotossa on suuren voiton mahdollisuus suoraan verrannollinen sijoitettuun panokseen. Napeilla pelatessa tähtitieteellinen.

Lue vähemmän-tiedät enemmän.

Vierailija
Esim. ei kolmea peräkkäistä numeroa.

Ne pallot eivät noudata tuollaisia päättelyitä. Kun ne pallot sieltä esille pommpivat, niin ne eivät tiedä

a) omaa numeroarvoaan
b) edellisiä numeroita

Eli aika turhaa tuollainen ainakin teorian kannalta. Sama kun tekisi konetta joka arvaa millaisen sarjan (kruuna & klaava) kolikko tekee kun sitä heittelee 10 m korkeudelta asfalttiin. 10 x klaava peräkkäin on ihan yhtä todennäköinen kuin mikä tahansa muukin 10 kuvion sarja.

Onko ohjelman sorsia vielä tallella? Miten generoit satunnaisluvut? Pitikö ohjelma kirjaa eri lukujen esiintymistiheyksistä? Monesti se on ongelma tällaisissa simulaatioissa.

Vierailija
Kale
...todennäköisyys saada yhdellä rivillä vähintään 4 oikein on n. 1/89, niin tätä 89:ää ei käsittääkseni voi pitää teoreettisenä miniminä...

Tarkemmin laskennallinen minimi vähintään 4-oikein tulokselle on:

15380937/184241 on 84 riviä.

Tämä tarkoittaa, että on olemassa sellainen 84 rivin harava, joka antaa joka kierroksella vähintään yhden 4-oikein tuloksen.

msdos464
Ne pallot eivät noudata tuollaisia päättelyitä. Kun ne pallot sieltä esille pommpivat, niin ne eivät tiedä

a) omaa numeroarvoaan
b) edellisiä numeroita
...


Tee itsellesi tilasto, niin huomaat olevasi väärässä.

Vierailija
_jone_
msdos464
Ne pallot eivät noudata tuollaisia päättelyitä. Kun ne pallot sieltä esille pommpivat, niin ne eivät tiedä

a) omaa numeroarvoaan
b) edellisiä numeroita
...


Tee itsellesi tilasto, niin huomaat olevasi väärässä.



Edelleen olen tätä mieltä:

Sama kun tekisi konetta (edit: algoritmia) joka arvaa millaisen sarjan (kruuna & klaava) kolikko tekee kun sitä heittelee 10 m korkeudelta asfalttiin.

Eli mahdoton tehtävä. Pallot eivät tiedä mikä numero niihin on kiinnitetty. Miten ne voisivatkaan?

On kyllä totta, että jos generoidaan satunnainen jono numeroita (esim. lotolla) niin on epätodennäköisempää että jonossa on esim. 3 peräkkäistä numeroa. Tämä kuitenkin johtuu siitä yksinkertaisesta syystä, että sellaisia rivejä on vähemmän. Jokainen yksittäinen rivi on (ideaalisessa tilanteessa) yhtä todennäköinen kuin muutkin.

L2K2
Seuraa 
Viestejä150
Liittynyt27.10.2006
_jone_

msdos464
Ne pallot eivät noudata tuollaisia päättelyitä. Kun ne pallot sieltä esille pommpivat, niin ne eivät tiedä

a) omaa numeroarvoaan
b) edellisiä numeroita
...


Tee itsellesi tilasto, niin huomaat olevasi väärässä.

Ei msdos464 ole väärässä _LAINAAMASSASI_ asiassa. Se missä päättelyketju menee metsään on entropia. Tapauksia, joissa on peräkkäisiä numeroita on huomattavasti vähemmän kuin muita. Tuo päättely on tosin hyödytön nykyaikana, tuon ideaalisen lotto"haravan" löytää Pythonilla[size=59:j26trf2b](kin)[/size:j26trf2b] muutamassa CPU-tunnissa brute-forcella. Eikö vain _jone_.

vale -> emävale -> tilasto

Vierailija
msdos464
Sama kun tekisi konetta (edit: algoritmia) joka arvaa millaisen sarjan (kruuna & klaava) kolikko tekee kun sitä heittelee 10 m korkeudelta asfalttiin.

No tee se tilasto, äläkä selosta. Olkoon kruunu x, ja klaava y. Nyt teet tilaston, että kun on x, mikä on todennäköisyys seuraavalla kerralla x:lle.

Siten tutkit todennäköisyyden, että on tullut xx, ja mikä on sen jälkeen x:n todennäköisyys.

Edelleen tutkit x:n todennäköisyyttä xxx:n jälkeen, jne.

Arvaa kaksi kertaa, onko ylimääräistä energiaa ruveta inttämään. Jos et viitsi itse kirjoittaa tilastointiin sitä 10 rivin algoritmia, on oma asiasi.

L2K2
...tuon ideaalisen lotto"haravan" löytää Pythonilla(kin) muutamassa CPU-tunnissa brute-forcella...

No teepä se sitten sillä Pythonillasi

L2K2
Seuraa 
Viestejä150
Liittynyt27.10.2006
_jone_

L2K2
...tuon ideaalisen lotto"haravan" löytää Pythonilla(kin) muutamassa CPU-tunnissa brute-forcella...

No teepä se sitten sillä Pythonillasi

Mitä yli 17 rivin mittaisella 4-oikein-järjestelmällä tekee?

Vierailija
_jone_
Kale
...todennäköisyys saada yhdellä rivillä vähintään 4 oikein on n. 1/89, niin tätä 89:ää ei käsittääkseni voi pitää teoreettisenä miniminä...

Tarkemmin laskennallinen minimi vähintään 4-oikein tulokselle on:

15380937/184241 on 84 riviä.


Aivan oikein! Ajattelin, että 5 oikein ja suuremmat olisivat osumat olisivat niin harvinaisia, ettei niitä tarvitse huomioida, mutta se otaksuma ei pidäkään paikkansa. Tuo laskelmasi on täysin oikein.

_jone_
Tämä tarkoittaa, että on olemassa sellainen 84 rivin harava, joka antaa joka kierroksella vähintään yhden 4-oikein tuloksen.

Mielestäni edelleenkään ei ole mitenkään todistettu, että tuollainen harava on olemassa. Se on teoreettinen minimi, jota ei mitenkään voi alittaa, mutta se ei takaa, että sellainen olisi olemassa. Jos sellainen todella on olemassa, niin se vaatii erillisen todistuksen.

maalaisukko
Seuraa 
Viestejä495
Liittynyt15.10.2006
msdos464

Ne pallot eivät noudata tuollaisia päättelyitä. Kun ne pallot sieltä esille pommpivat, niin ne eivät tiedä

a) omaa numeroarvoaan
b) edellisiä numeroita

Eli aika turhaa tuollainen ainakin teorian kannalta. Sama kun tekisi konetta joka arvaa millaisen sarjan (kruuna & klaava) kolikko tekee kun sitä heittelee 10 m korkeudelta asfalttiin. 10 x klaava peräkkäin on ihan yhtä todennäköinen kuin mikä tahansa muukin 10 kuvion sarja.

Onko ohjelman sorsia vielä tallella? Miten generoit satunnaisluvut? Pitikö ohjelma kirjaa eri lukujen esiintymistiheyksistä? Monesti se on ongelma tällaisissa simulaatioissa.

Näin on. En ole tutkinut tilastoja numeroitten esiintymisistä, mutta noin äkkiseltään katsottuna kolme peräkkäistä esiintyy melko harvoin. Vaikka oikeaan riviin tulisikin kolme peräkkäistä jää ko. ehtorakenteella silti mahdollisuus 6-oikein tulokseen. Ja 4-oikein sillä ohjelmalla haettiin. Kokeilin myös numeroitten tilastointia ja jakamista tasapuolisesti vaan ei siitä ollut mitään hyötyä. Ihan satunnaisuuteen perustuva ohjelma tuo oli, mutta se karsi tehokkaasti pois kaikki "mahdottomat" rivit.
Ohjelmaa ei ole tallella. Se oli tehty basicilla. RND:n alkuluku time-funktiosta.

Lue vähemmän-tiedät enemmän.

Vierailija
_jone_
msdos464
Sama kun tekisi konetta (edit: algoritmia) joka arvaa millaisen sarjan (kruuna & klaava) kolikko tekee kun sitä heittelee 10 m korkeudelta asfalttiin.

No tee se tilasto, äläkä selosta. Olkoon kruunu x, ja klaava y. Nyt teet tilaston, että kun on x, mikä on todennäköisyys seuraavalla kerralla x:lle.

Siten tutkit todennäköisyyden, että on tullut xx, ja mikä on sen jälkeen x:n todennäköisyys.

Edelleen tutkit x:n todennäköisyyttä xxx:n jälkeen, jne.

Arvaa kaksi kertaa, onko ylimääräistä energiaa ruveta inttämään. Jos et viitsi itse kirjoittaa tilastointiin sitä 10 rivin algoritmia, on oma asiasi.

Mikä näistä numeroisarjoista on lotossa todennäköisempi:

a) 1, 2, 3, 4, 5, 6, 7
b) 1, 2, 3, 4, 5, 6, 25
c) 5, 9, 11, 20, 25, 29, 35

Olisi kiva saada myös vähän perusteluja. Tiedän kyllä että todennäköisyyksissä voi mennä helposti sekaisin (esim. se 3 ovea, 2 vuohta ja auto).

Jos laitan listan vaikka 1000 kolikon heiton tuloksesta, ei se auta seuraavan tuloksen arvamisessa, koska tapaukset ovat toisistaan riippumattomia. (...kunnes toisin todistetaan)

Vierailija
maalaisukko
Ihan satunnaisuuteen perustuva ohjelma tuo oli, mutta se karsi tehokkaasti pois kaikki "mahdottomat" rivit.
Ohjelmaa ei ole tallella. Se oli tehty basicilla. RND:n alkuluku time-funktiosta.

Yleensä nuo mukana tulevat randomi funkkarit ovat aika kehnoja ja hitaita.

L2K2
Seuraa 
Viestejä150
Liittynyt27.10.2006
msdos464
_jone_
msdos464
Sama kun tekisi konetta (edit: algoritmia) joka arvaa millaisen sarjan (kruuna & klaava) kolikko tekee kun sitä heittelee 10 m korkeudelta asfalttiin.

No tee se tilasto, äläkä selosta. Olkoon kruunu x, ja klaava y. Nyt teet tilaston, että kun on x, mikä on todennäköisyys seuraavalla kerralla x:lle.

Siten tutkit todennäköisyyden, että on tullut xx, ja mikä on sen jälkeen x:n todennäköisyys.

Edelleen tutkit x:n todennäköisyyttä xxx:n jälkeen, jne.

Arvaa kaksi kertaa, onko ylimääräistä energiaa ruveta inttämään. Jos et viitsi itse kirjoittaa tilastointiin sitä 10 rivin algoritmia, on oma asiasi.




Mikä näistä numeroisarjoista on lotossa todennäköisempi:

a) 1, 2, 3, 4, 5, 6, 7
b) 1, 2, 3, 4, 5, 6, 25
c) 5, 9, 11, 20, 25, 29, 35

Olisi kiva saada myös vähän perusteluja. Tiedän kyllä että todennäköisyyksissä voi mennä helposti sekaisin (esim. se 3 ovea, 2 vuohta ja auto).

Jos laitan listan vaikka 1000 kolikon heiton tuloksesta, ei se auta seuraavan tuloksen arvamisessa, koska tapaukset ovat toisistaan riippumattomia. (...kunnes toisin todistetaan)

Kaikki ovat yhtä todennäköisiä. Mutta rivejä muotoa 1,2,3,4,5,6,x x!=7 on useampia kuin jos x==7.
Sama pätee myös muille numeroille. Erikoistapauksia vähemmän kuin yleisiä tapauksia.

Sivut

Uusimmat

Suosituimmat