Vyhrajte balík

09. 08. 2007, zapsal #13
Kategorie: Uncategorized 

Skládáte rádi puzzle? Tak si kupte puzzle Eternity II . Má to 999 dílků, a když to složíte jako první na světě, dostanete za to dva milióny dolarů.

Možná si řeknete, že to je pro programátora lehký a bude to mít cobydup. Tak lehký to je, jenže vzhledem k tomu, že to má 999 dílků, tak počet možností, jak vedle sebe ty dílky poskládat, je 999! = 999 * 998 * 997 *… * 3 * 2 *1. A to je hodně vysoké číslo. Konkrétně 4,02387260077093773543702433923 * 10^2564. To znamená, že je to čtyřka a za ní ještě 2564 nějakých číslíček. Krásné číslo, ne? Tolik možností by i ten nejvýkonnější počítač zkoušel roky.

A právě o to jde! Matematici chtějí, aby nějaký sexy mozek přišel na to, jak se to všechno dá řešit jinak, rychleji. Nebo aspoň aby někdo dokázal, že to rychleji nejde.

Ostatně — zamysleli jste se někdy nad tím, že když máte navštívit třeba pět míst (musíte z domova do školy, do lékárny, na úřad, do pekárny, do trafiky a zpátky domů), tak nejde zjistit, jaká trasa je nejkratší? Tedy jde. Ale počítejte si všech 120 možností. Pro 10 míst už je těch možností 3,6 miliónu. Pro 17 už jsme v biliónech, pro 70 na googolu. Říká se tomu travelling salesman problem a je to asi nejdůležitější nevyřešený problém současné matematiky.

Firmy by zase rády věděly, jestli je levnější nejdřív montovat do auta vejfuk nebo volant (nadsázka). Zatím se tohle všechno dělá odhadem.

Takže přemejšlejte, jak to vypočítat jinak než brutální silou (dosazením do všech možností), spoustě lidem a firem ušetří spoustu času a peněz, dostanete hodně prachů a budete slavný.

Témata:

Komentáře

Komentáře (6) k článku “Vyhrajte balík”

  1. koroslav on 10. 08. 2007 1:48

    Ano to číslo jak náhodně poskládat puzle je vysoké, ale nutné podotknout, že eternity 2 má “jen 256 dílků” Ovšem zapomněl jsi na věc, která se u backtrackingu používá často, a tou je heuristika. Takže počet možností, které musí počítač projít je nesrovnatelně méně.

  2. Plumm on 10. 08. 2007 2:35

    “Ovšem zapomněl jsi na věc, která se u backtrackingu používá často, a tou je heuristika.” Hm, tak týhle větě sem uplně rozuměl :roll:

  3. Zdenis on 10. 08. 2007 16:29

    Já jí neporozumněl vůbec :)

  4. #13 on 10. 08. 2007 18:45

    koroslav: Sakra, máš recht. Ale kde jsem vzal těch 999? :)

    O té heuristice jsem četl taky, ale nepochopil jsem přesně, o co jde.

  5. koroslav on 10. 08. 2007 23:10

    no s heuristikou to bylo mysleno takhle:
    Byla by blbost zkouset vsechny dilky a vsechny jejich otoceni na vsechny pozice. To bys delal vecnost. Misto toho zuzis vyber dilku a jejich otoceni, ale musis to udelat tak, aby jsi vyberem nevyradil reseni. (momentalne se programovanim eternity - zatim jenom organizaci datovych struktur a vyberem vhodne heuristiky - tak trochu zabyvam, takze podrobnosti rozebirat nebudu)
    Uvedu priklad. Kdyz jsem programoval sudoku solver (a zaroven i generator), jedna z moznosti byla zkouset nahazet bruteforcem vsechna cisla do vsech policek a pak zkontrolovat validitu reseni. Misto toho se ale vybira na dane policko jenom validni cislo (ne vzdy plati, ze existuje jedno policko, do ktereho lze doplnit jenom jedine cislo). Rychlost a narocnost reseni pak zalezi na vhodnem naprogramovani heuristiky (obecne plati zrat co nejmin pameti a co nejmin casu - tzn. nemit zbytecne podminky a nejlepe veskera data do dalsiho cyklu predavat referenci)

  6. #13 on 10. 08. 2007 23:22

    No jo, teď jsi ještě připomněl, že každý políčko má čtyři otočení, takže je těch variant zase ještě víc :).

    Tu heuristiku jsem snad nějak přibližně pochopil. Dík.

Neboj se přidat komentář...
jo a jestli chceš mít u komentáře svůj obrázek, pořiď si gravatar!





*
Abys dokázal, že jsi člověk (a ne spamující robot), opiš bezpečnostní slovo z obrázku. V případě potíží s přečtením slova, klikni na obrázek, abys slyšel antispamové slovo.
Click to hear an audio file of the anti-spam word