2014 2015 2016 2017 2018

Savanaudės voverės

Taškai: 12

Medyje yra penkios viena virš kitos išsidėsčiusios drevės. Jose gyvena 16 voverių. Kasdien kiekviena voverė apžiūri, kiek turi kaimynų drevėje, kurioje gyvena, viena dreve virš (jei yra) ir viena dreve žemiau (jei yra). Nustato, kurioje iš šių drevių yra mažiausias kaimynų skaičius. Naktį kiekviena voverė persikelia į pasirinktą drevę (arba lieka savoje), kurioje kaimynų skaičius mažiausias. Jei tokių drevių ne viena, voverė pirmenybę teikia savo drevei, tada aukščiau esančiai drevei ir galiausiai – žemiau esančiai drevei.

Pavyzdžiui, voverės drevėse gyvena šitaip: 5, 0, 0, 4, 7 (pradedant nuo viršaus ir einant žemyn). Rytoj visos 5 viršutiniojo aukšto voverės apsigyvens viena dreve žemiau (0 kaimynų yra geriau nei 4), 7 voverės iš apatinės drevės persikels viena dreve aukščiau (4 kaimynai yra geriau negu 6) ir 4 voverės iš antrosios drevės nuo apačios persikels dreve aukščiau (0 kaimynų yra geriau nei 3).

Tarkime, kad voverės drevėse gyvena šitaip:

6

3

3

0

4

Kiek dienų reikės, kad visos voverės atsidurtų vienoje ir toje pačioje drevėje?

A. 2   B. 3   C. 4   D. Tai neįmanoma
Paaiškinimas

Tai skruzdžių kolonijos elgseną arba kitaip, skruzdžių intelektą imituojantis uždavinys. Šio algoritmo idėja remiasi tuo, kad bet kas gali išspręsti problemas net naudodamas paprastus įrenginius, jei tų įrenginių yra labai daug. Pavyzdžiui, skruzdės juda pagal elementarias taisykles ir nepriklausomai viena nuo kitos. Tačiau kai skruzdžių daug, jos gali padaryti įspūdingus dalykus. Todėl skruzdžių kolonijos modelis naudojamas daugeliui sudėtingų uždavinių spręsti: rasti optimalų kelią grafe, spręsti keliaujančio pirklio uždavinį, nuskabyti medžių lapus ir pan.
Šiame uždavinyje voverių drevių pasirinkimas pagrįstas paprastomis taisyklėmis. Tačiau voverių elgesys toli gražu nėra sumanus. Jos norėtų gyventi kuo erdviau, tačiau susigrūda į vieną drevę. Taigi šis uždavinys gana pamokantis: skruzdžių kolonijos algoritmą reikia taikyti apdairiai, pamatuotai, atsiminti, kad kartais geriau veikti bendradarbiaujant, o ne būti savanaudiškam.

Reikšminiai žodžiai: skruzdžių kolonijos elgsenos modelis, kolektyvinis intelektas, skruzdžių algoritmas.

Atsakymas

Teisingas atsakymas yra 3.
(6, 3, 3, 0, 4) –> (0, 9, 0, 7, 0) –> (9, 0, 7, 0, 0) –> (0, 16, 0, 0, 0)