i
i
“Lokar-crv” — 2010/6/14 — 10:47 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 16 (1988/1989)
Številka 4
Strani 214–220
Matija Lokar:
LAČNI ČRV
Ključne besede: matematika, računalništvo, matematično modelira-
nje, izometrična mreža.
Elektronska verzija: http://www.presek.si/16/940-Lokar.pdf
c© 1989 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
LACNI CRV
Črv Bine je kmalu prišel k sebi po padcu skozi luknjo . Razgledal se je okoli
sebe in bil vedno bolj navdušen.
"Saj to je Indija Koromandija. Povsod sama hrana ."
ln začel se je plaziti in jesti , jesti, ... Za njim je ostajala le za njegovo širino
široka sled brez hrane.
Nekaj podobnega se je dogajalo več tisoč let nazaj. Prazgodovinski črvi so
se hranili v blatu na dnu kotanj . Pri tem so razvili določene vzorce obnašanja.
Tako niso sledili poti , ki so jo že preplazili , saj je tam ostalo le malo hrane. Po
drugi strani je bilo pametno ostati blizu svojih sledi , saj je bila hrana običajno v
kupčkih. Tako so črvi pri iskanju hrane upoštevali nekaj preprostih pravil. Ta
pravila so določala , kako blizu 'pojedenim' potem naj črv ostane ; kako daleč
naj gre, preden se obrne; kakšen naj bo zasuk, ... Pravila so bila različna od pri -
merka do primerka in na osnovi primerjav fosilnih sledov palenteologi danes
raziskujejo obnašanje teh črvov. Pri raziskavah pa so poklicali na pomoč tudi
matematike in računalnikarje . Tako so na univerzi v Warwicku in vlaboratori·
ju za umetno iteligenco inštituta za tehnologijo v Massacchutesu izdelali mate-
matični model iskanja hrane teh črvov. Če črv naleti na vozlišče , kjer še ni no-
bena od poti preiskana (hrana pojedena) razen seveda poti, po kateri se je pri ·
plazil, se mora odločiti, kam naj gre. Če bi bilo v njegovih pravilih zapisano,
naj gre naravnost, bi se vedno gibal naprej, kar ni zanimivo ne za nas ne za
resničnega črva (zakaj?). Zato morajo biti pravila vseh črvov taka, da se obrne-
jo, če naletijo na novo vozlišče.
Denimo, da se črv giblje po
pravokotni mreži, torej da se vedno
obrača za 90° bodisi v levo ali v
desno. Osnovni zasuk naj bo le desni,
da se izognemo zrcalnim slikam . Ko
po štirih korakih črv opiše kvadrat,
ima na voljo le dve možnosti. Če se
giblje tako , da gre v levo natanko
takrat, ko ne more v desno, je njego'
va pot takšna
Slika 1. Pravokotniški črv
214
Ko jo opiše , nima na voljo več
hrane in črv pogine. Enaka usoda ga
čaka tudi v drugem primeru, le da ne-
koliko kasneje . Tu je pravilo tako , da
gre naravnost, ko ne more desno in v
levo le, če ne gre ne levo in ne desno .
Slika 2. Še drugi pravokotniški črv
To sta edina primerka enostavnih pravokotniških črvov. Več možnosti
imamo, če se črvi gibljejo po izometrični mreži iz enakostraničnih trikotnikov.
Tu se v vsakem vozlišču sreča namesto štirih šest poti. Na prvi pogled malenko-
stna razlika . Vendar nam ta mreža omogoča veliko raznolikost gibanja črvov.
Vsi črvi upoštevajo naslednja tri splošna pravila .
1. Če v vozlišču še ni pojeden noben del , se črv obrne v desno (dve možnosti).
2. Če so vsi deli v vozlišču pojedeni, črv pogine .
3. Če je v vozlišču nepojeden le en del , ga črv poje .
Kot smo že videli, pravokotniški črv naleti le na eno vozlišče, kjer se mora
odločati. Ker sta le dve možnosti, imamo le dva primerka pravokotniških
črvov. Izometrični črvi pa lahko naletijo na štiri tipe vozlišč, kjer se morajo
odločiti, kaj storiti. Oglejmo si "razpored odločitev", ki omogoča 1296 razli-
čnih pravil hranjenja črvov. Zakaj ravno tak razpored, bi na tem 'mestu težko
povedal i, zadovoljimo se s tem, da nam le tak omogočazanimivo nadaljevanje
zgodbe. Na sliki so označeni štirje tipi in možnosti odločitve. Polna črta ozna-
čuje nepojedeni del, črtkana pojedeni in puščica smer gibanja črva.
Štirje tipi so naslednji:
1. Črv dospe do vozlišča, kjer noben del še ni pojeden (razen ravno preplaze-
nega). Zasuk v desno je lahko blag (120°) ali pa oster (60°). Možnosti sta
torej dve.
2. Črv pride v vozlišče z enim pojedenim delom. Svojo odločitev izbere
izmed štirih možnosti:
215
IZBIRA
___------'A~--~
TIP
1
a b
**
c d
TI P
4
IZB IRA
.---------'----,
a b
-ff- *2
3
216
-1, -X l ' \,t I :- - ~ 7\-
~ ~ ~'i. \1
7\ 7\-1\ 7\
-*-X- -*-X-
-V__V_~_~L
"\ /\ /\ ---:\
--\1- -~- ~- -iL1 , , \ ,, \ \ \
-Y--V--V-, \ , \ I \
I \ " , \
(1) --\.L -V- _V_
I" 1\ /:
--v- _:\~- --~-
,\ I I, , I
(2)
1,' \,' \,'- - ~--'/.-\ 1\ / \
\L 'L \1
(3) -7\ --1\ -1\
'~ ~ '/' , ,-- -~-" "\ "\
\ I '\ I \ I
(4) i't --k-k
-)~ -X- -*
Slika 3 . Vsa možna križišča
\ I \ I
\ I '\ ,
~--~'\ ', 1
\
1 \ 1I ,
-- - ---:\-
/\ "\
,,/ "1---r.- - - -1:-/\ /\
\' \ I
\ I \ I
~--1-1, \" '
\ / \/
--~- - -7..-1 \ / \.
\ / \1
--~- -7-1, ,\ \
~
I \ I1 ,
~-~-I \ I \
I \ ,\
\1- \ 1-- - ---/'-...-I , I \
, \ I \
-:1- -y-
I '\ I \
I '\ I \
a) prvi možni zasuk v levo,
b) drugi možni zasuk v levo,
c) tretji možni zasuk v levo,
d) četrti možni zasuk v levo.
3. Črv je v tem vozlišču že bil, pojedena sta torej dva dela, ki pa po splošnih
pravilih ne moreta oklepati iztegnjenega kota. Pustimo v tem primeru črvu
več domišljije. Gibanje črva naj poteka po treh pravilih, toda neodvisno v
posameznih skupinah križišč . Kot kaže slika 3, smo križišča razvrstili v
štiri skupine. Glede na gibanje črva v križiščih z dvemi pojedenimi deli
imamo torej 34 = 81 različnih črvov .
4 . V vozlišču s tremi pojedenimi deli naj ima črv na razpolago le dve možno-
st i, glede na prvi oziroma drugi možni zasuk v levo, podobno kot v pri-
meru 2 .
Če se črv priplazi do vozlišča , kjer so pojedeni štirje ali pet odsekov, ruma
nobene izbire . V prvem primeru sledi preostalemu nepojedenemu odseku, v
drugem primeru pa pogine. Torej imamo 2 x 4 x 81 x 2 =1296 množic pravil ,
ki vsak določajo svojo vrsto izometr i čnega črva. Kako pa bomo ločili med po-
sameznimi črvi? Za vsako polje bomo povedali, katero možnost si črv izbere in
to nap isali nekako takole 1a2b3acac4b. Ta črv se torej pri novem vozlišču
odloči za blag zasuk, pri tipu dva se odloči za možnost b, pri tipu tri se v kri-
žiščih prve skupine odloči za pravilo a, v križiščih druge skupine za pravilo c, v
križiščih tretje skupine zopet za pravilo a in v križiščih četrte skupine spet za
pravilo c, pri tipu štiri izbere prvi možni zasuk v desno. Ta črv za sabo pusti
naslednjo sled
Tako pot pa ne pušča le opisani
črv, ampak tudi nekateri drugi. Po-
skusite jih najti. V pomoč naj vam
povem, da jih je 14. Z računalniškim
programom so raziskali obnašanje
vseh 1296 vrst izometričnih črvov.
Rezultati so pokazali, da 209 primer-
kov tvori le njim lastne poti, 46 poti
generirata po dve vrsti črvov in 44
poti več kot dve vrsti. Imamo torej
299 različnih poti. Najenostavnejša
pot je podobna simbolu za radioakti-
vnost in jo tvori kar 162 vrst. Poišči­
te jih nekaj I
217
Slika 5.
Vsi črvi, ki smo jih srečali do se-
daj. so z svojim obnašanjem obsojeni
na pogin od lakote. Mar tako pogine-
jo prav vsi? Hitro najdemo črva, ki
mu od lakote ne bo treba poginiti.
Tak je npr. črv z vzorcem
1b2d3abbb 4b
(jJ(j)0 /
Lačna ne bosta ostala tudi črva 1a2c3acba4a in 1a2d3caaa4b, katerih sled
je prav zanimiva
Raziskovalci so poskušali ugotoviti , kako dolga je najdaljša končna pot
takih črvov. Odgovora še ne poznajo. Najdaljša znana končna pot je dolga
220142 enot in jo tvori črv 1a2d3cbac4b. Tako so npr. črvu 1b2a3bcaa4b
sledili na njegovi poti več kot 10 milijonov korakov, a še vedno ne vedo, ali se
njegova pot kdaj zaključi. Odprtih vprašanj v obnašanju izometričnih črvov je
še veliko. Kaj se npr. zgodi, če sta na isti površini dva ali več črvov, kakšne so
218
poti črvov, če so določena območja brez hrane, kako se črv obnaša, če ima
možnost, da pregleda pot nekaj korakov naprej. Določene hipoteze najlaže za-
snujemo s pomočjo računalnika. Sestavite ustrezne programe za gibanje črvov
in nam jih pošljitel Za konec pa še črv 'oblaček'
219
Slika 9. Črv 1a2abaa3c4a
in črv 'zvezda'. Slika 10. Črv 1a2d3cbaa4b