Býflugur og travelling salesman vandamálið

Ímyndaðu þér að þurfa að ferða milli hundrað borga og þú þyrftir að finna þá leið sem er hakvæmust og síðan komast aftur heim.  Þetta er vandamál í tölvunarfræðinni og kallast "the travelling salesman problem" og menn eru komnir með nokkuð gott algrím sem leysir þetta vandamál. Maður setur aðeins inn punktana og alla mögulegar leiðir milli allra punkta og hve dýrt er að fara á milli þeirra og síðan... bíður maður í dágóðan tíma eftir því að tölvan finnur út úr þessu.  Því fleiri punktar, því lengur er tölvan að finna út úr þessu.

Vill svo til að býflugur leysa þetta sama vandamál en gera það ótrúlega hratt og vel samkvæmt einni vísindarannsókn sem gerð var við Lundúnar háskólanum. Svona orðaði einn af vísindamönnunum þetta:

Professor Lars Chittka, University of London
‘In nature, bees have to link hundreds of flowers in a way that minimises travel distance, and then reliably find their way home—not a trivial feat if you have a brain the size of a pinhead! Indeed such travelling salesmen problems keep supercomputers busy for days.’

Við eigum eins og er ekki séns að búa til svona litla og öfluga tölvu sem getur reiknað þetta út. Það segir okkur að sá sem hannaði bífluguna er ennþá gáfaðri en við. Við getum alveg útilokað náttúruval og tilviljanir því að það eru ferli með engar gáfur en til að afreka þetta þá þarf gáfur, svo mikið getum við verið viss um.

Athugasemdir

[Jón Bjarni Steinsson (IP-tala skráð) 10.9.2012 kl. 12:52]

það er ypsilon í í býflugur

[Mofi, 10.9.2012 kl. 12:55]

Takk

[Tómas, 10.9.2012 kl. 18:52]

Ég veit ekki hvort þú skoðaðir rannsóknirnar sem Chittka og fl. hafa verið að vinna að, en þau próf sem ég sá, eftir (reyndar mjög stutt) yfirlit, voru einungis fyrir fáeinar nóður.

Ég er með lítið tæki í vasanum sem getur leyst þess lags vandamál á fáeinum sekúndubrotum.

Má vera að þeir hafi framkvæmt próf með fleiri tugum nóða, eða hundruðum, sem vissulega væri áhugaverðara, en ég fann ekkert slíkt. Ef þú finnur rannsókn sem styður þessa tilgátu, endilega sendu það hingað inn. Það getur nefninlega vel verið að býflugur geti ekki fundið bestu lausnina við aðeins erfiðari vandamálum, heldur séu bara með góðar nálganir fyrir fáar/nokkrar nóður. Sem er alls ekki jafn merkilegt..

Reyndar, ef maður les textann vandlega, þá er prófessorinn ekki að halda því fram að býflugur geti leyst verkefni sem tók ofurtölvu marga daga að leysa. Hann sagði einungis að býflugur virtust geta leyst verkefni af sama tagi. Sem er lítið mál. Ég gæti gert svona verkefni á A4 blaði fyrir 4 nóður (jafnvel 5, ef ég skrifa smátt).

Enn fremur er ég ósammála síðustu málsgreininni, bara svo það sé á hreinu :) Það er nefninlega alls ekki búið að sýna fram á að þróunarkenningin geti ekki "framleitt" gáfaðar lífverur. Ég veit þú segir það ómögulegt - en þú ættir ekki að gera það. Ég hef aldrei sagt að guð geti ekki verið til - vegna þess að ég get alltaf haft rangt fyrir mér.

[Mofi, 11.9.2012 kl. 08:18]

Tómas, þetta var niðurstaðan sem vísindamennirnir fengu en já, ég veit ekki hve margar nóður þeir staðfestu að býflugurnar leistu dæmið á hagkvæman hátt. Hann sagði beint út að býflugurnar gera þetta fyrir hundruði blóma í náttúrunni svo það virðist vera þeirra niðurstaða.

[Mofi, 11.9.2012 kl. 08:30]

Varðandi síðasta punktinn, er þetta rétta aðferðin til að nálgast svona spurningu?  Ætti það ekki frekar að vera að það þarf að sýna fram á að tilviljanir og náttúruval geti sett saman veru með gáfur?

[Tómas, 11.9.2012 kl. 13:02]

Niðurstaðan er ekki sú að þeir viti að býflugur geti fundið bestu lausn á TSP fyrir hundruðir nóða.

Chittka segir að býflugur verði að lágmarka ferðavegalengdina milli blóma, og að þess lags verkefni geti tekið ofurtölvur marga daga. Hann segir hvergi að þeir hafi sýnt fram á að býflugur finni virkilega bestu lausnina - né heldur virðast 3 rannsóknir þeirra, sem ég kíkti lauslega á, benda til þess.

Rannsóknirnar benda hins vegar til þess að þær finna oftast bestu lausnina fyrir mjög fáar nóður - sem er ekki mjög impressive.

Hægt er að finna nálgunarlausnir við stórum TSP á sæmilega góðum tíma, meðan besta lausnin (sem er kannski fáeinum prósentum betri en margar nálganir) krefst margra daga útreikninga.

Ég held þú takir orð hans of bókstaflega.

Varðandi athugasemd um síðasta punktinn. Ég hef margoft rætt þetta við þig, og reynt að sýna fram á að upplýsingar geti orðið til út frá náttúrulögmálum og handahófi. Ég veit ekki hvernig mér ætti að ganga betur að reyna að sýna þér fram á hvernig gáfur geti orðið til gegnum þróunarkenninguna.

Ég vil heldur ekki fara að rökræða það hér. Ég vildi bara benda á að mér þykir þú oftúlka orð Chittka, og að þó býflugur geti leyst (eða fundið nálganir) við erfiðum vandamálum, þá þykir mér það ekki jafn tilkomumikið og þér.

[Tómas, 11.9.2012 kl. 13:18]

Bara til að leggja áherslu á það sem ég sé athugavert við pistilinn þinn:

Ég sé hvernig þú getur túlkað orð hans þannig að hann viti að býflugur geti leyst stór TSP vandamál, sem taki ofurrölvur marga daga, en í fyrsta lagi túlka ég orð hans öðruvísi og í öðru lagi benda rannsóknirnar sjálfar ekki til þess að hann sé virkilega að meina þetta.

[Mofi, 11.9.2012 kl. 13:29]

Ég sé ekki betur en Chittka segir þetta beint út en er alveg sammála að kannski er hann að lesa of mikið út úr takmörkuðum gögnum ef þetta var aðeins prófað fyrir nokkra punkta. Hann er síðan sá sem rannsakaði þetta og honum fannst þetta tilkomumikið svo kannski vantar þig að rannsaka þetta eins og hann og þá finndist þér þetta líka tilkomumikið?