22 júla 2009

Čo najviac súkromia

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:

Rori povedal(a)...

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...

Radoslav Harman povedal(a)...

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ý.

Ruziklan povedal(a)...

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

misof povedal(a)...

- 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)

Radoslav Harman povedal(a)...

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é.