BEBRO konkurso užduotys 2017

 

Robotas siurblys

Taškai: 12

Robotas valo kvadratinėmis plytelėmis išklotas grindis pagal šias komandas:

  • P – paeina viena plytele į priekį (sugaišta 1 minutę),
  • D – pasisuka 90° dešinėn (tai daro akimirksniu),
  • V – išvalo plytelę (sugaišta 1 minutę).

Robotas pradeda ir baigia vienoje iš kampinių plytelių (A, B, C, D), bet nebūtinai toje pačioje.

Kiek mažiausiai minučių sugaišta robotas, kol išvalo visas prieinamas grindų plyteles?

Paaiškinimas

Šis uždavinys yra atskiras keliaujančio pirklio atvejis: reikia rasti trumpiausią kelią, kai norima aplankyti visas grafo viršūnes. Galėtume ir kitaip traktuoti šį uždavinį – kad tai išplėsta Hamiltono kelio problema, kai reikia nustatyti, ar yra kelias per visas grafo viršūnes, aplankant jas po vieną kartą. Deja, nėra jokio optimalaus algoritmo nei vienam iš šių uždavinių išspręsti. Jei plytelių būtų daug, tuomet net galingi kompiuteriai neįveiktų skaičiavimų per žmogui priimtiną laiką.

Plačiau skaitykite:
https://en.wikipedia.org/wiki/Travelling_salesman_problem
https://en.wikipedia.org/wiki/Hamiltonian_path_problem

Raktiniai žodžiai: algoritmas, keliaujančio pirklio uždavinys, Hamiltono kelias.

Atsakymas

Teisingas atsakymas: 55.
Iš viso yra 36 – 9 = 27 grindų plytelės, taigi jas visas išvalyti reikia 27 minučių.
Jei kiekvieną plytelę pavyktų pereiti tik vieną kartą, tai siurblys ėjimui sugaištų 26 minutes (pirma plytelė neskaičiuojama, joje jau stovima). Taigi reikia mažinti skaičių plytelių, per kurias reikėtų eiti antrą kartą.  
Panagrinėkime paveikslą kairėje. Plytelė X yra ypatinga – ja teks pereiti du kartus nepriklausomai nuo to, kurį kelią pasirinktume.
Plytelės, „įleidžiančios“ į kampus A B C D pažymėtos atitinkamai raidėmis E F G H. Plytelės E ir F yra „įleidžiančios“ į kampą A , plytelė G – į kampą D ir plytelė H – į kampą C . Kampas B neturi tokios „įleidžiančios“ plytelės.
Jei kampas nėra nei pradžios, nei pabaigos kampas, tai robotui tenka šių kampų „įleidžiančias“ plyteles pereiti du kartus. Jei robotas pradeda ir baigia tame pačiame kampe, tai jis turi pereiti abi „įleidžiančias“ plyteles du kartus. Jei robotas pradeda viename kampe, o baigia kitame kampe, tai jų „įleidžiančios“ plytelės gali būti pereinamos po vieną kartą. Žinodami visa tai, galime suplanuoti roboto kelią taip, kad jam reikėtų pereiti kuo mažiau „įleidžiančių“ plytelių.
Kadangi kampe A yra dvi „įleidžiančios“ plytelės E ir F, tai gera strategija yra pradėti (arba baigti) šiame kampe. Toliau tenka pasirinkti antrą kampą (pabaigos) - C arba D (abiem atvejais vieną iš „įeinančių“ plytelių G arba H pereitume tik vieną kartą).
 


Kairiajame paveiksle parodytas kelias iš A į C, kurį sudaro 28 ėjimai į priekį (jame yra ypatingos plytelės X ir G). Keliui iš A į D reikėtų nelyginio skaičiaus ėjimų, taigi padarius 28 ėjimus į priekį viena plytelė liktų nevalyta (tai būtų plytelė, pažymėta mėlyna dėme dešiniajame paveiksle), taigi šis kelias yra ilgesnis nei iš A į C.
Mažiausias plytelių valymo laikas yra: 27 (valymui) + 28 (judėjimui) min. = 55 min.stumas, trumpiausias kelias

Interaktyvi užduotis

 

 
Informacija atnaujinta 2017-11-13 16:52:39
Informuojame, kad nuo 2019 m. rugsėjo 2 d. Ugdymo plėtotės centro veiklas vykdo Nacionalinė švietimo agentūra. Ši interneto svetainė toliau nebus atnaujinama, tačiau visa informacija išliks aktyvi ir prieinama tol, kol bus perkelta į Nacionalinės švietimo agentūros interneto svetainę www.nsa.smm.lt.