Traveling Salesdog Problem: cum un câine a rezolvat problema comis-voiajorului mai repede decât CI-ul tău

În timp ce noi ne chinuim cu probleme NP-complete și scriem biciclete pentru TSP, cercetătorii s-au gândit să vadă cum se descurcă câinii. Spoiler: ne-au bătut.

Cercetătorii de la Universitatea Western Wyoming au făcut un experiment: un câine trebuia să adune mingi împrăștiate pe câmp și să se întoarcă la stăpân. Rezultatul? Câinele a găsit un traseu aproape optim, fără o linie de cod și fără să se plângă de lipsa documentației.

Algoritm pe patru labe

Se pare că câinii folosesc euristica „cel mai apropiat vecin” – dar ajustată cu mirosul și lenea. În loc să enumere toate variantele (cum facem noi), ei aleargă pur și simplu la cea mai apropiată minge, apoi la următoarea, și așa mai departe. Și funcționează! Abaterea medie de la traseul optim a fost de doar 12% – pentru o problemă NP-dificilă, asta e aproape perfect.

Dezvoltatorii care au scris vreodată propriul rezolvitor de TSP acum se simt un pic prostuți. Mai ales cei care au folosit algoritmi genetici cu 1000 de generații. Câinele face asta într-o secundă, iar tu stai și aștepți să se antreneze rețeaua neuronală.

Dar nu vă grăbiți să concediați echipa de Data Science. Metoda are limitări: câinele nu lucrează cu grafuri de 1000 de orașe și nu știe să țină cont de ambuteiaje. În schimb, știe să dea din coadă și nu necesită code review.

Comentariul studioului METABYTE: Dacă producția ta poate fi optimizată la fel de intuitiv precum câinele adună mingi, poate e timpul să regândești arhitectura? Dar pe bune, și noi suntem pentru soluții elegante fără overengineering.