{"id":482,"date":"2010-01-11T19:52:17","date_gmt":"2010-01-11T17:52:17","guid":{"rendered":"http:\/\/naukowy.blog.polityka.pl\/?p=482"},"modified":"2018-07-25T20:50:18","modified_gmt":"2018-07-25T18:50:18","slug":"mrowki-snieg-i-wiatr","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/naukowy\/2010\/01\/11\/mrowki-snieg-i-wiatr\/","title":{"rendered":"Mr\u00f3wki, \u015bnieg i wiatr"},"content":{"rendered":"

\"\"<\/a><\/p>\n

Istnieje taka klasa algorytm\u00f3w heurystycznych, kt\u00f3r\u0105 okre\u015bla si\u0119 jako algorytmy mr\u00f3wkowe. Generalnie wykorzystuje si\u0119 je do wyszukiwania najkr\u00f3tszych \u015bcie\u017cek w grafach. Idea ich dzia\u0142ania opiera si\u0119 na symulacji kolektywnego zachowania kolonii mr\u00f3wek, kt\u00f3re poszukuj\u0105 po\u017cywienia.<\/p>\n

<\/p>\n

Na pocz\u0105tku mr\u00f3wki b\u0142\u0105kaj\u0105 si\u0119 losowo, a gdy kt\u00f3ra\u015b pokarm znajdzie, wyrusza na poszukiwanie mrowiska, znacz\u0105c swoj\u0105 tras\u0119 feromonem. Gdy ju\u017c dotrze do domu, jej \u015blad zapachowy zaczyna przyci\u0105ga\u0107 inne mr\u00f3wki, kt\u00f3re zaczynaj\u0105 r\u00f3wnie\u017c wykorzystywa\u0107 t\u0119 drog\u0119, a wracaj\u0105c ni\u0105 ju\u017c ze zdobycz\u0105 dodaj\u0105 w\u0142asny \u015blad feromonowy – wzmacniaj\u0105c go w ten spos\u00f3b. Jednak feromon nie ma absolutnej si\u0142y przyci\u0105gania i wiele mr\u00f3wek nadal b\u0142\u0105ka si\u0119 i znajduj\u0105c pokarm wraca trasami innymi ni\u017c ta pierwsza albo zbacza z niej, nawet gdy ni\u0105 pocz\u0105tkowo p\u00f3jdzie. Gdy oznakowanych jest wi\u0119cej \u015bcie\u017cek, te d\u0142u\u017csze powoli popadaj\u0105 w zapomnienie. Dzieje si\u0119 tak dlatego, \u017ce feromon jest substancj\u0105 lotn\u0105 i powoli wyparowuje, trac\u0105c z up\u0142ywem czasu atrakcyjno\u015b\u0107 dla mr\u00f3wek. Im d\u0142u\u017csza trasa, tym wi\u0119ksze s\u0105 \u015brednio odst\u0119py pomi\u0119dzy w\u0119druj\u0105cymi mr\u00f3wkami i\u00a0 tym s\u0142abiej od\u015bwie\u017cany jest jej \u015blad zapachowy, podczas gdy kr\u00f3tsze s\u0105 mocno od\u015bwie\u017cane i systematycznie zyskuj\u0105 na atrakcyjno\u015bci w por\u00f3wnaniu z nimi. \u017beby dostrzec ten efekt, wystarczy wyobrazi\u0107 sobie tras\u0119 tak d\u0142ug\u0105, \u017ce w momencie powrotu do gniazda pierwszej mr\u00f3wki, jej \u015blad zapachowy w okolicy pokarmu ju\u017c prawie ca\u0142kowicie wyparowa\u0142. Nast\u0119pna u\u017cytkowniczka drogi w okolicy pokarmu mo\u017ce pob\u0142\u0105dzi\u0107, a wracaj\u0105c wybierze zapewne zupe\u0142nie inn\u0105 tras\u0119 i nie wzmocni \u015bladu na tej starej. Ten efekt<\/a> jest tym silniejszy, im d\u0142u\u017csza jest droga do przebycia, ale wyst\u0119puje tak\u017ce dla kr\u00f3tkich \u015bcie\u017cek. Jego efektem jest to, \u017ce w\u0119drowczynie generalnie preferuj\u0105 \u015bcie\u017cki kr\u00f3tsze.<\/p>\n

Takie zachowanie mr\u00f3wek mo\u017cna \u015bwietnie symulowa\u0107 za pomoc\u0105 komputera, ka\u017c\u0105c wirtualnym mr\u00f3wkom biega\u0107 po \u015bcie\u017ckach grafu i u\u017cywa\u0107 mechanizmu skopiowanego z przyrody do wyszukiwania w nim najkr\u00f3tszych \u015bcie\u017cek, a po stosownych modyfikacjach rozwi\u0105zywa\u0107 tak\u017ce inne, trudniejsze problemy obliczeniowe.<\/p>\n

Pierwszy takie algorytmy opisa\u0142 w swoim doktoracie Marco Dorigo<\/a> z W\u0142och. Przypomnia\u0142y mi si\u0119 w sobot\u0119, gdy w\u0119drowa\u0142em z psem na nartach biegowych po \u0142\u0119gach na praskim brzegu Wis\u0142y. Bo ludzie w tak\u0105 pogod\u0119 zachowuj\u0105 si\u0119 jak mr\u00f3wki. Brn\u0105 w \u015bniegu, przecieraj\u0105c drog\u0119, ale w miar\u0119 up\u0142ywu czasu wiatr ich \u015blady zawiewa. Jak \u015bcie\u017cka jest ju\u017c solidnie zasypana, coraz mniej sensu ma trzymanie si\u0119 jej i w\u0119drowcy z niej zbaczaj\u0105. Gdyby Dorigo by\u0142 Polakiem (albo Eskimosem), pewnie te algorytmy nazywa\u0142yby si\u0119 dzi\u015b algorytmami w\u0119drowc\u00f3w w zadymce.<\/p>\n

Jerzy Tyszkiewicz<\/strong><\/p>\n

Fot. Mesq<\/a>, Flickr (CC SA)<\/em>
\n<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"

Istnieje taka klasa algorytm\u00f3w heurystycznych, kt\u00f3r\u0105 okre\u015bla si\u0119 jako algorytmy mr\u00f3wkowe. Generalnie wykorzystuje si\u0119 je do wyszukiwania najkr\u00f3tszych \u015bcie\u017cek w grafach. Idea ich dzia\u0142ania opiera si\u0119 na symulacji kolektywnego zachowania kolonii mr\u00f3wek, kt\u00f3re poszukuj\u0105 po\u017cywienia.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60,43,6],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/482"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/comments?post=482"}],"version-history":[{"count":2,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/482\/revisions"}],"predecessor-version":[{"id":6216,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/posts\/482\/revisions\/6216"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/media?parent=482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/categories?post=482"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/naukowy\/wp-json\/wp\/v2\/tags?post=482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}