Shrinking Blob Computes Traveling Salesman Solutions

Ceļojošā pārdevēja problēma ir viens no slavenākajiem matemātikas izaicinājumiem. Tā ir problēma, kā atrast īsāko maršrutu, lai vienu reizi apmeklētu vairākas pilsētas un pēc tam atgrieztos izcelsmes vietā.

Protams, ir vienkārši atrast maršrutus, kas šādā veidā apmeklē katru pilsētu. Lielais izaicinājums ir atrast īsāko.

Ir viens bezatteices veids, kā to izdarīt — ar tīru brutālu spēku. Tas nozīmē, ka ir jāizmēra katras ekskursijas garums un jāizlemj, kura ir īsākā. Problēma ir tā, ka šis uzdevums kļūst arvien garāks, jo palielinās pilsētu skaits. Patiešām, lielam skaitam pilsētu tas ir skaitļošanas ziņā neiespējams.

Ir viegli iedomāties, ka varētu būt kāds gudrs matemātisks īsceļš, kas atrisina šo problēmu. Ne tā. Faktiski matemātiķi mēdz piekrist, ka vispārējs īsceļš nekad netiks atrasts (šīs ir tā sauktās P=NP debates).

Tā vietā viņiem ir jāpaļaujas uz optimizācijas procesiem, kas meklē īsus risinājumus, bet nespēj pierādīt, ka tie patiešām ir īsākie.

Tāpēc visu praktisko mērķu uzdevums ir atrast algoritmus, kas dod labus rezultātus un ir skaitļošanas ziņā efektīvi.

Šodien Džefs Džonss un Endrjū Adamackis Rietumanglijas Universitātē Apvienotajā Karalistē atklāj neparastu pieeju. Šie puiši saka, ka saprātīgu risinājumu var atrast, attēlojot pilsētas kā punktu virkni virtuālajā Petri trauciņā, iegremdējot punktus virtuālā slānī un pēc tam samazinot lāsumu.

Vienkāršoti izsakoties, lāse pielīp pie punktiem, kad tas sarūk, savienojot tos ar minimālu virsmu, gluži kā ziepju burbuļa virsmu. Viņi saka, ka lāsei sarūkot, tā morfoloģiski pielāgojas pilsētu konfigurācijai.

Kad visi punkti atrodas uz lāses virsmas, iegūtā virsma ir risinājums ceļojošā pārdevēja problēmai, kas kopumā ir diezgan labs.

Maģiskā sastāvdaļa visā šajā ir īpašais goo. Tas sastāv no daudzām daļiņām, kuras katra pārvietojas saskaņā ar vienkāršu noteikumu kopumu, piemēram, autonomiem aģentiem. Tie atrodas ķīmisko atraktantu jūrā, virtuālā smaržā, kas piesaista daļiņas. Katrā aprēķina posmā katra daļiņa sajūt apkārt esošo ķīmisko atraktantu un pēc tam virzās uz augstākās koncentrācijas reģionu. Kustoties, tas atstāj aiz sevis savas ķīmiskās vielas pēdas, lai tās varētu sekot citām daļiņām.

Rezultāts ir sava veida inteliģents lāse, kas parāda uzvedību, piemēram, spēju samazināt tā virsmas laukumu.

Džonss un Adamackis ir izmēģinājuši šo inteliģento prātu, liekot viņam zaudēt ceļojošo pārdevēju problēmas, kas sastāv no 20 pilsētām, kas nejauši sadalītas virtuālajā Petri trauciņā. Viņi ir ievietojuši saraušanās procesa video šeit .

Rezultāti ir labi, bet ne ideāli. Tika izveidoti 20 dažādi scenāriji no 20 pilsētām un katrā tika veikti lāse 6 reizes. Pēc tam viņi salīdzināja lāses īsāko ceļu ar patieso īsāko ceļu, kas tika atrasts ar brutālu spēku. Džounss un Adamackis saka, ka, ja šī īsākā maršruta garums ir 1, viedā lāse atrada maršrutus, kuru vidējais labākais maršruta garums ir 1,04, vidējais maršruta garums ir 1,07 un sliktākais maršruta garums ir 1,09.

Tas nav slikti. Taču patiesā priekšrocība ir pieejas vienkāršība, kas būtībā ir jauna un neietver īpašus optimizācijas procesus. Tā beigās arī izveido maršruta karti (lai gan, lai to saprastu, ir nepieciešama cilvēka interpretācija).

Ir mīnusi, protams. Ir dažas pilsētu konfigurācijas, ar kurām lāse nevar tikt galā. Tie rodas, ja īsākais ceļš veido sava veida šaurumu starp divām pilsētām, nevis savienojumu, piemēram, Gibraltāra šaurums starp Atlantijas okeānu un Vidusjūru. Tā vietā lāse mēdz tos savienot.

Tomēr tas ir interesants netradicionālas skaitļošanas veids, kas rada aizraujošu alternatīvu parastajiem ceļojošo pārdevēju algoritmiem. Tai ir vistuvākā līdzība ar gumijas joslu pieejām, kas apņem pilsētas ar gumijas joslu un pēc tam pakāpeniski mēģina stiept joslu, lai savienotu pilsētas. Lielā atšķirība ir tā, ka lāses materiāla īpašības ir radušās, nevis iepriekš ieprogrammētas.

Džonss un Adamackis saka, ka nākamais solis būtu izveidot šīs sistēmas fizisku modeli, kurā darbu veic īsts lāse, iespējams, izmantojot viskoelastīgo brīvās enerģijas samazināšanu. Tomēr šāda materiāla projektēšana var būt sarežģīta.

Vēl viena pieeja, kurai varētu būt plašāks pielietojums, būtu šī netradicionālā skaitļošanas īpašību destilēšana klasiskā algoritmā.

Pats labākais ir iespēja, ka loģistikas vadītāji plāno piegādes maršrutus, iegremdējot ceļu tīkla modeļus inteliģentās tvertnēs. Tāpēc mēs ar nepacietību gaidīsim šo jauno zinātni par ceļojošo pārdevēju alķīmiju.

Atsauce: arxiv.org/abs/1303.4969 : ceļojošā pārdevēja problēmas aprēķins, izmantojot sarūkoša lāse

paslēpties