Krátko po tom ako som sa vrátil z konferencie spomenutej v predchádzajúcom príspevku, odcestoval som na ďalšiu konferenciu: Petersburg Workshop on Simulation. Samotná návšteva Petrohradu bola pre mňa dosť veľký zážitok (konečne som videl na vlastné oči napríklad Auroru a Zimný palác, ktoré nám ako pionierom toľko tlačili do hláv), ale tým Vás nebudem obťažovať; cestovateľských, prípadne politických blogov je veľa.Určite viete, že v Petrohrade je jedna z najväčších galérií na svete - Ermitáž. Pri jej návšteve som mal dvojité šťastie. Po prvé, vybrali sme sa na prehliadku náhodou práve v jediný deň v mesiaci, počas ktorého je voľný vstup a po druhé bola s nami Anastasia Ivanova, ktorá si kedysi popri učení na univerzite privyrábala robením sprievodkyne práve v Ermitáži. Takže sme nielenže nezablúdili, ale dokonca sme videli výber z tých najzaujímavejších exponátov.
V jednej z miestností utrúsila Anastasia poznámku, že nechápe, ako mohla cárska rodina bývať v budove s takmer samými priechodnými miestnosťami; nepotrebovali väčšie súkromie? Nech už to bolo s cárskou rodinou akokoľvek, ak obmedzíme maximálny počet dverí v každej miestnosti, tak istý počet priechodných miestností je nutný. A máme nasledovný rekreačný problém na náš blog:
Predpokladajme, že každá z n (nie nutne štvorcových ani obdĺžnikových) miestností v budove má nanajvýš troje dverí, ktoré ju spájajú so susednými miestnosťami. Koľko maximálne môže byť v tejto budove miestností, ktoré majú len jedny dvere? Samozrejme predpokladáme, že z každej miestnosti sa dá prejsť do každej inej miestnosti.
Na obrázku je budova s 10 miestnosťami, z ktorých je až 6 "súkromných" a žiadna miestnosť nemá viac ako troje dverí. Vítané sú samozrejme nielen riešenia, ale akékoľvek postrehy a komentáre, prípadne zovšeobecnenia.
5 komentárov:
Najzakladnejsi postreh asi je, ze sa to bude riesit pomocou grafov. Miestnost je vrchol, dvere su hrany. Podmienky potom
- suvisly graf
- najviac 3 hrany z kazdeho vrchola
- pocet vrcholov s jednou hranou = pocet sukromnych miestnosti
Nenapada ma hned ako maximalizovat to posledne - ale podla toho by sa to dalo jednoducho naprogramovat...
Rori: Presne tak; grafový pohľad problém sprehľadní, umožní sa vyjadrovať terminológiou teórie grafov stručne a presne a naviac nám pri jeho riešení môžu pomôcť niektoré dobre známe tvrdenia.
Ešte pár ďalších drobných postrehov a príklad bude vyriešený.
Mne to vychadza tak, ze na k sukromnych miestnosti je treba aspon k-2 priechodnych, takze pre n parne, n>2 je pocet sukromnych (n/2)+1 a pocet priechodnych (n/2)-1. Nad detailami sa mi teraz v tom teple nechce rozmyslat :-P
- optimalna topologia je zjavne strom (ak by sme mali cyklus, namiesto jednej jeho hrany pridame dva listy)
- ak mame dva vrcholy stupna 2, mozeme z nich presmerovanim hrany spravit vrchol stupna 1 a vrchol stupna 3
cim je dokazana optimalnost toho co napisal Ruziklan -- najlepsie riesenie je strom, kde su vsetky vnutorne vrcholy stupna 3, mozno az na jeden stupna 2
Pripomenulo mi to peknu (ale vyrazne tazsiu) ulohu: problem D tuto.
Zhrnutie zadania: Dane su rozmery M a N, treba nakreslit planik rozmerov MxN, kde niekde na obvode je jedno policko oznacene ako vchod a niektore z policok su postele. Kazda postel musi byt dosiahnutelna od vchodu (clovekom co sa vie hybat vzdy len na volne policko susediace stranou s tym kde prave je) a posteli musi byt co najviac.
Priklad: pre 4x7 moze riesenie vyzerat takto:
B_B_BEB
B_BBB_B
B_____B
B_BBB_B
(E je vstup, B postel, _ volne miesto)
Fajn chalani; našli ste samozrejme správne riešenie. Ja ho ešte prehľadne zhrniem:
Nech n je počet miestností. Ak je n párne, tak maximálny počet súkromných miestností je 1+(n/2) a ak je n nepárne, tak maximálny počet súkromných miestností je (1+n)/2.
misof: To je naozaj trochu podobný a zrejme dosť ťažký problém, ale tam ak sa nemýlim bolo potrebné napísať algoritmus, ktorý nájde optimálne rozmiestnenie vchodov a postelí. Nájsť formulku, ktorá určuje maximálny počet postelí v závislosti od rozmerov miestnosti, bude asi dosť ťažké.
Zverejnenie komentára