2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

Užtvankos tuneliai

Taškai: 12

Užtvankoje įrengti tuneliai, jungiantys keturis kambarius (A, B, C, F). Pirmieji trys kambariai (A, B ir C) yra gyvenamieji, ketvirtame kambaryje (F) įrengta valgykla (žr. paveikslą).

Kambaryje A gyvena 10 bebrų. Kai bebrai išalksta, nori kuo greičiau patekti į valgyklą F.

Kelionė tuneliu trunka 1 minutę. Vienu metu tunelyje gali būti tik vienas bebras. Kambariai sujungti tam tikru skaičiumi tunelių:

• tarp A ir B yra 4 tuneliai,

• tarp A ir C yra 1 tunelis,

• tarp B ir C yra 2 tuneliai,

• tarp B ir F yra 1 tunelis,

• tarp C ir F yra 3 tuneliai.

Visi kambariai yra dideli, todėl juose gali tilpti neribotas skaičius bebrų.

Kiek minučių trunka greičiausias visų bebrų perėjimas iš kambario A į valgyklą F? Įrašyk skaičių.

Paaiškinimas

Grafų teorijoje tunelių tinklą galima įsivaizduoti kaip srautą tinkle. Tai orientuotasis grafas, kurio kiekviena briauna yra tam tikro pralaidumo (didžiausias tunelių ar keliaujančių bebrų skaičius tarp kambarių). Kiekvienos briaunos srautas negali viršyti jos pralaidumo.

Siekiama optimizuoti bebrų srautą tinkle, kad visi bebrai kuo greičiau atvyktų į tikslą. Pvz., toks tinklas gali būti naudojamas eismui modeliuoti transporto kelių sistemoje. Šioms problemoms spręsti gali būti naudojami keli algoritmai, vienas kurių yra Fordo–Fulkersono algoritmas.

Mūsų sprendžiamas uždavinys taip pat yra vienas iš šios problemos atvejų: jei nėra galimybės toliau keliauti, leidžiama laukti kambariuose B ir C. Klasikinio srauto tinklo uždavinio formuluotėje laukimas nenumatomas. Viskas, kas ateina, turi iš karto pasiskirstyti per kitus kanalus. Be to, paprastai formuluojant šią problemą nurodomos kiekvieno tunelio kryptys. Čia galima laisvai pasirinkti, kuria kryptimi einama tuneliais.

Raktiniai žodžiai: grafai, planavimas, tinklo pralaidumas.

Atsakymas

Geriausiu atveju visi bebrai valgyklą pasieks per 4 minutes.

Grafas turi du trumpiausius maršrutus, kurių abiejų pralaidumas yra po 1 bebrą, o abi kelionės trunka 2 minutes:

• nuo A iki B ir nuo B iki F

• nuo A iki C ir nuo C iki F

Yra ir pralaidesnis kelias (2 bebrai), bet juo kelionė trunka 3 minutes:

• nuo A iki B, nuo B iki C ir nuo C iki F.

Norint optimizuoti bendrą laiką, pralaidumas tarp A ir B turi būti sumažintas. Optimalus sprendimas – iš A į B siųsti tris bebrus pirmąją minutę ir tris antrąją minutę. Tai daroma atsižvelgiant į tai, kad iš B kambario išeina tik 3 tuneliai. Todėl, jei A ir B kambarių jungtis naudojama, kai pralaidumas didžiausias (4 bebrai), B ir C, B ir F kambarių jungtyse susidaro spūstis, todėl vienas bebras lieka laukti B kambaryje. Pateiktoje lentelėje aiškinami veiksmai, atliekami kiekvieną minutę, kol visi bebrai pereina į valgyklą. Šį optimalų uždavinio sprendimą (4 minutės), galima gauti keliais būdais. Pasirenkame tą būdą, kuriuo keliaujantiems bebrams nereikėtų laukti kambaryje B.

Veiksmas / situacija

Bebrų skaičius kambariuose (atlikus veiksmą)

A

B

C

F

Pradinė situacija

10

0

0

0

3 bebrai pereina iš A į B (kai pralaidumas nėra didžiausias)

 

 

 

 

1 bebras pereina iš A į C

 

 

 

 

Situacija po 1 minutės

6

3

1

0

3 bebrai pereina iš A į B (kai pralaidumas nėra didžiausias)

 

 

 

 

1 bebras pereina iš B į F

 

 

 

 

2 bebrai pereina iš B į C

 

 

 

 

1 bebras pereina iš C į F

 

 

 

 

1 bebras pereina iš A į C

 

 

 

 

Situacija po 2 minučių

2

3

3

2

1 bebras pereina iš A į B (pasirenkamas trumpiausias kelias)

 

 

 

 

1 bebras pereina iš B į F

 

 

 

 

2 bebrai pereina iš B į C

 

 

 

 

1 bebras pereina iš A į C (pasirenkamas trumpiausias kelias)

 

 

 

 

3 bebrai pereina iš C į F

 

 

 

 

Situacija po 3 minučių

0

1

3

6

1 bebras pereina iš B į F

 

 

 

 

3 bebrai pereina iš C į F

 

 

 

 

Situacija po 4 minučių

0

0

0

10
Interaktyvi užduotis