У каквој су вези ефикасно паковање путне торбе, спајање компоненти матичне плоче и проблем трговачког путника?
Текст: Слађана Шимрак
Продајом Икозијанске игре једном лондонском дилеру 1859. године, Вилијам Хамилтон је зарадио укупно двадесет пет фунти. Судећи по његовом биографу, ово је био једини новац који је Хамилтон зарадио на својим открићима и публикацијама. Дилер је имао добро око: игра је, иако лагана, заживела и била је дистрибуисана у више продавница широм Енглеске и континента.
За играње је потребно имати човечуљка и додекаедар. Свако теме додекаедра представља по један град. Човечуљак се иницијално налази у неком граду и има за задатак да, путујући по ивицама тела, обиђе све градове тако да у сваки сврати само по једанпут, и да се потом врати у место из ког је кренуо.
Сличне занимације су у неком облику постојале и много пре Хамилтона. Забележено је да је још у деветом веку индијски песник Рудрата састављао строфе такве да се њихови стихови могу читати на два начина: уобичајено, с лева на десно, или тако што се, полазећи од почетка, до сваке наредне речи стиже скакањем по строфи попут скакача у шаху. Скакачева путања занимала је многе писце, па ако убрзамо до двадесетог века, наићи ћемо нпр. на роман Жоржа Перека, Живот упутство за употребу, писан по овом шаблону. Али, њиме су се њиме занимали и математичари. Први је био Леонард Ојлер, али је коначно решење поставио немачки математичар Х.Ц. фон Варнсдорф.
Но, Икозијанска игра је, више него по својој тадашњој популарности, остала упамћена као пример једног од најпознатијих рачунарских проблема данашњице, и једног од оних који су се највише проучавали – проблема трговачког путника. Њега је формално дефинисао бечки математичар Карл Менгер, тридесетих година прошлог века, гостујући на Харварду, коначно подстичући интерес научне заједнице за његово решавање.
Похлепна метода
Проблем је постављен слично Икозијанској игри, али са једним додатком: потребно је, међу свим могућим решењима, пронаћи најкраћу путању такву да се обиђу сви градови. Дакле, трговац пред собом има одређен број градова који мора да обиђе и да се потом врати у онај из ког је кренуо – како да испланира посете тако да уштеди трошкове пута што је више могуће?
Задатак не звучи тешко. Уобичајен поступак је да се коришћењем исцрпне претраге преброје све могуће путање, и да се потом одабере најоптималнија. Ово је метода која готово тривијалним путем доводи до решења ако је у игри мањи број градова.
Друга метода која се често користи је похлепна метода. Идеја ове методе је да се крене од произвољног града и да се за наредни бира увек онај који је најближи. Овај алгоритам често даје добро решење, али како не узима у обзир све податке, није сасвим поуздан. Такође се користе и генетски алгоритми, засновани на еволуционим механизмима. Њихова предност је што у разумном времену углавном дају решење које је свега два или три одсто лошије од оптималног.
Но, ниједна од њих не представља универзално решење које ће гарантовати најбољи резултат у сваком случају. Разлог неуспеху је временска сложеност алгоритама, која је факторијелна. То значи да повећањем броја градова укупан број путања расте огромном брзином и рачунарима би практично било потребно бесконачно много времена да дођу до решења.
Тако, на пример, уколико трговац на својој турнеји мора да обиђе двадесет један град, он би требало да бира најбољу од укупно 20! путања, што је заправо број 2432902008176640000. Зато се овај задатак сврстава у такорећи нерешиве, барем у општем смислу, односно у задатке такозване NP класе.
Симболом P означава се класа проблема за чије се решавање може пронаћи алгоритам који има полиномијалну временску сложеност. Ово у највећем броју случајева значи да рачунар за релативно кратко време може доћи до резултата. С друге стране, када је реч о припадницима NP класе, ефикасан алгоритам за њихово решење вероватно не постоји. Поставља се питање да ли је могуће NP проблеме свести на P? Већина математичара је сагласна да то вероватно није случај, али доказ и даље није пронађен.
Но, често је довољно зауставити се на довољно добрим решењима, уместо настављати потрагу за најоптималнијим решењем. Тако разни проблеми који имају велике практичне примене имају у пракси задовољавајућа решења, а алгоритми који служе налажењу ових задовољавајућих решења зову се хеуристике.
Награда од милион долара
Међутим, задатак P=NP, као најпознатији нерешен проблем у рачунарству, налази се међу „Миленијумским проблемима“ за чије решење амерички институт Клеј нуди награду од милион долара.
Након што је Григориј Перелман пре петнаестак година затворио поглавље о доказу Поенкареове хипотезе, на листи Миленијумских математичких проблема остало је њих шест који и данас чекају на решење. И сваки је вредан по милион долара.
Задатак П=НП има трагове још у педесетим годинама прошлог века, и о њему су тада писали Џон Неш, Курт Гедел и Џон фон Нојман, међутим званично је дефинисан 1971. године, у раду Стивена Кука.
Ради се, дакле, о дилеми: ако рачунар може довољно брзо да утврди да ли неки проблем има решење, може ли такође брзо, пронаћи то решење? Како због своје свакодневне примене, тако избог миленијумске награде, тек, путујући трговац је тема која редовно привлачи и научнике и мејнстрим медије.
Бумбарева напредна логика
Мали пчелињи мозгови победили су рачунаре. Тако је гласио наслов у Гардијану, октобра 2010. Повод за текст било је истраживање које су недуго пре тога спровели биолози са два лондонска колеџа. Они су, наиме, уочили да се бумбари у свом лету са цвета на цвет, користе напредном логиком како би процес учинили што ефикаснијим.
У почетку, око бумбара су били постављени цветови тако да је сваки од њих садржао исту количину нектара. Бумбари су врло брзо, путем покушаја и погрешака, научили да одреде путању којом ће утрошити најмање времена и енергије. Али затим су научници пред њих поставили тежи задатак: променили су количине нектара тако да је сваки цвет имао различиту количину. Тиме су натерали бумбаре да одлуче хоће ли и даље пратити најкраћу руту или ће најпре посетити цвет са највише нектара.
Бумбари су и овде дошли до закључка повољног по себе. Уколико би проценили да ће се дужина лета тек незнатно променити уколико прво посете цвет са највише нектара, одлучивали би да тако промене своју путању. У супротном, уколико би се укупна дужина значајније повећавала, држали би се најкраће руте коју су смислили на почетку.
Сличан таленат за оптимизацију поседују и мрави. Истраживач у области вештачке интелигенције, Марко Дориго, описао је 1993. године хеуристичку методу „добрих решења“ проблема путујућег трговца користећи модел мравље колоније.
Дориго је користио чињеницу да је код мрава изражен феномен колективне интелигенције. Испуштајући феромон при кретању, и пратећи која путања има највише феромона, чланови колоније међусобно размењују информације о окружењу.
Сваки мрав, са одређеном вероватноћом, бира наредно место које ће посетити на основу удаљености до тог места и количине испуштеног феромона. Мрав који је одабрао најкраћи пут оставља највише феромона, јер су дужина пута и количина феромона обрнуто пропорционалне. Тако остали мрави све више прате овај траг и како временом феромон испарава, путеви које мрави ређе користе остају без њега, и тиме убудуће не привлаче никога из групе.
УПС
Поред велике примене са основном поставком задатка, многи проблеми се могу свести на проблем трговачког путника, као што су проблеми у рендгенској анализи структуре кристала, проблем ефикасног паковања путне торбе, спајање компоненти матичне плоче рачунара и слично.
Принцип мравље алгоритма је, рецимо, једну од главних нашао у решавању проблема рутирања возила. Овај проблем се јавио педесетих година као централни проблем компанија које се, на пример, баве доставом пошиљки. Овде је потребно одредити минималан број возила који је потребан за извршавање задатака, као и руту која ће обезбедити највећу уштеду.
Компанија УПС, водећа светска компанија за доставу пошиљки, која свакодневно испоручује око четрнаест милиона пакета, од 2000. године ради на пројекту ORION (On-Road Integrated Optimization and Navigation). Њихов тим математичара свакодневно ради на проналажењу најефикаснијих возачких рута. Систем је први пут тестиран 2008. године, а како тврде, то им на годишњем нивоу доноси уштеду од преко 35 милиона долара.