25 októbra 2012

Fúrik

Prevážame fúrikom tehly z miesta A na miesto B. Doba trvania jednej "obrátky" (naloženie fúrika, prevoz z A do B, vyloženie, cesta naspať z B do A) závisí od toho, koľko tehál prevážame. Urobili sme 5 pokusných obrátok, ktorých výsledky sumarizuje nasledovná tabuľka.

Počet naložených tehál 3 6 9 12 15 18
Čas obrátky (v sekundách) 18 28 52 60 96 152

Koľko tehál by ste odporučili nakladať do fúrika?

Na rozdiel od väčšiny zábavných hlavolamov, táto úloha nemá "jediné správne" riešenie. V reálnych aplikáciách sa však často vyskytujú práve takéto problémy: údaje zaťažené náhodnou chybou, neznámy alebo veľmi komplikovaný matematický model, niekedy dokonca nie celkom presne definovaný cieľ.

Acknowledgements: Úloha je motivovaná podobnou úlohou, ktorú nám opäť poslal Peťo Mikloš.

7 komentárov:

rasťo povedal(a)...

Ja by som nahodil na furik vzdy nahodny pocet tehiel z intervalu 6-12 tehal a s lahkou hlavou, ze som usetril cas straveny dumanim by mi praca isla od ruky :-)

Ale vazne, je to dost zaujimave, vyzera to ako keby 6 tehiel bolo z tychto pokusov najvyhodnejsie ("4.67 sekundy na tehlu"), ale preco by malo dat 9 tehal horsi a 12 tehal opat lepsi vysledok a kde je skutocne optimum...

No, som zvedavy na fundovanejsie riesenia. Kym pridu, nosim nahodne pocty od 6 do 12 ks tehiel :-)

goober povedal(a)...

Mne sa najviac páčia počty okolo 7-8; pri niektorých modeloch to vychádza bližšie k jednému, pri iných k druhému... V reále by ale asi bolo jednoduchšie a rýchlejšie spraviť niekoľko ďalších (a podľa možnosti opakovaných) meraní s aj s chýbajúcimi počtami tehál.

Ale úplne najefektívnešie by bolo počkať, kým Rasťo všetky tehly odvezie... a potom víťazoslávne vrátiť prázdny fúrik Radovi :-)

Radoslav Harman povedal(a)...

Prevážať náhodný počet tehál medzi 6 a 12 môže byť z praktického hľadiska naozaj najlepšie riešenie, najmä ak je ich celkový počet malý a neoplatí sa míňať čas zbytočným špekulovaním. (Záleží samozrejme aj na tom, ako rýchlo vie človek dospieť k výsledku. :)

Dokonca, ako píše goober, aj ak by sme mali previesť veľmi veľa tehál, tak by sa mohlo oplatiť ešte trochu experimentovať s rôznymi nákladmi, aby sme získali viac informácie pre štatistický model, ktorým modelujeme čas obrátky v závislosti od počtu tehál.

(Vymyslieť efektívnu metódu "sekvenčného" experimentovania na zistenie najvhodnejšieho počtu tehál je pomerne náročné; je to problém stochastickej aproximácie, ktorý súvisí s optimálnym navrhovaním experimentov.)

Ja som bez ďalšieho experimentovania použil kvadratický regresný model a pre odhadnuté parametre mi optimálny počet tehál vyšiel 7. Tento odhad je však nelineárnou funkciou parametrov a bolo by zaujímave preň skonštruovať napríklad 95 percentnú oblasť spoľahlivosti.

katka povedal(a)...

Zaujimave, ze pre parny pocet tehal (6 a 12, 18 uz nie) vychadzaju o cosi lepsie hodnoty "priemerneho casu potrebneho na prenesenie 1 tehly" ako pre neparny pocet tehal. Napadlo mi taketo vysvetlenie tohto javu:

Do jednej ruky neviem chytit naraz viac ako jednu tehlu. Preto ak chcem nakladat tehly co najrychlejsie, nakladam dve naraz - jednu pravou a jednu lavou rukou. Takze 2n tehal nalozim za rovnaky cas ako 2n-1 tehal. A ci vo furiku tlacim o jednu tehlu viac alebo menej, to uz velky casovy rozdiel nespravi.

To asi znamena, ze tehly boli nahadzane na kope v mieste A, ak ich bolo treba nakladat takto. Ak by boli pekne poukladane do stlpcekov, tak by sa mi mozno podarilo nalozit do furika aj cely stlpec naraz :)

Radoslav Harman povedal(a)...

Katka, asi Ťa sklamem - tie časy nie sú namerané, ale len vymyslené :) Je iba náhoda, že prevážanie párneho počtu tehál sa javí ako efektívnejšie, čo by sa dalo vysvetliť tak ako píšeš, pokiaľ by išlo o reálne dáta.

Máš ale samozrejme pravdu v tom, že spôsob uloženia aj technika nakladania tehál by určite mali vplyv na strednú hodnotu času jednej obrátky. Táto stredná hodnota by mohla mať "vlnky" a žiadny jednoduchý spojitý model (ako napríklad kvadratický) by nebol úplne presný, dokonca by sa mohol meniť v čase ako by sa menil "tvar" kopy tehál...

Samozrejme, z praktického hľadiska nie je nutné, aby sme použili presný model. Ako povedal slávny štatistik G.E.P. Box, prakticky všetky modely sú chybné, napriek tomu sú niektoré z nich užitočné.

goober povedal(a)...

Ešte by Rado mohol prezradiť, akým náhodným generátorom tie časy generoval :-)

Radoslav Harman povedal(a)...

goober: Nasimuloval som to ako nezávislé realizácie kvadratického regresného modelu (čo je, trochu mätúco, špeciálny lineárny regresný model; kvadratická je závislosť na "nezávislej premennej" x označujúcej počet tehál, a lineárna je závislosť na parametroch modelu).

Ale ako si si už predtým všimol, optimálny počet tehál je okolo 7 pre viacero rôznych modelov. "Robustnosť" takýchto odhadov vzhľadom k voľbe modelov by sa zrejme dala študovať aj na serióznej vedeckej úrovni.