Glossari

Seleccioneu una de les paraules clau de l’esquerra ...

Gràfics i xarxesEl problema del venedor ambulant

Temps de lectura: ~20 min
Aquesta pàgina ha estat traduïda automàticament i pot contenir errors. Poseu-vos en contacte si voleu ajudar-nos a revisar les traduccions.

Pensem, una vegada més, en xarxes i mapes. Imagineu que un servei de lliurament ha de visitar ${tsn} diferents ciutats per distribuir paquets. Podem pensar en aquestes ciutats com els vèrtexs en un gràfic. Si totes les ciutats estan connectades per carreteres, aquest és el , per tant n'hi ha ${tsn} × ( ${tsn} - 1)2 = ${tsn*(tsn-1)/2} vores en total.

El camió de lliurament ha de visitar totes les ciutats, en qualsevol ordre. En el problema dels ponts de Königsberg volíem trobar camins que transitessin per cada vora exactament. Ara volem trobar camins que visiten tots els vèrtexs exactament una vegada. Aquests camins s’anomenen cicles hamiltonians .

Hi ha infinites possibilitats de cicles hamiltonians en gràfics complets. De fet, podem escollir qualsevol vèrtex com a vèrtex inicial i, a continuació, escollir qualsevol de les ciutats restants en qualsevol ordre:

Diagram coming soon…

Diagram Coming Soon…

En un gràfic amb ${tsn1} ciutats, tots els cicles hamiltonians també han de contenir ${tsn1} ciutats. Ara,

    Això vol dir que, en total, n’hi ha ${tsnPaths(tsn1)} possibles camins. Una drecera per a aquest producte és ${tsn1} ! o ${tsn1} Factorial .

    Us podríeu imaginar que potser no es podria viatjar directament entre dues ciutats, sense passar per una altra ciutat. En aquest cas, ja no tenim un gràfic complet, i és molt més difícil trobar el nombre de cicles hamiltonians.

    Fins ara, hem ignorat el fet que algunes ciutats podrien estar més enllà de les altres. En la vida real, però, aquesta és una consideració molt important: no només volem trobar cap camí, sinó que en volem trobar el més curt. Això s’anomena el problema del venedor ambulant . S'ha de resoldre no només en transport i logística, sinó també quan es posicionen transistors en microxips, per fer ordinadors més ràpids o en analitzar l'estructura de l' ADN .

    Un mètode senzill seria provar tots els camins possibles, trobant la longitud de cadascun i, a continuació, escollir el més curt. Tot i això acabem de demostrar-ho, fins i tot amb just ${tsn2} ciutats hi ha ${tsn2} ! = ${factorial(tsn2)} possibles camins. Un cop tingueu centenars o milers de vèrtexs, intentar tots els camins possibles es fa impossible, fins i tot amb ordinadors potents.

    Malauradament, no hi ha cap algorisme més eficient per resoldre el problema del venedor viatger. En canvi, els matemàtics i informàtics han desenvolupat diversos algoritmes que troben bones solucions, fins i tot si no poden ser els millors. Aquests algoritmes, que només donen solucions aproximades, s’anomenen heurístiques .

    Proveu de reordenar les ciutats en aquest mapa i observeu com canvia el camí més curt entre elles. Podeu eliminar les ciutats tocant-les i podeu afegir ciutats fent clic a qualsevol lloc del mapa (fins a 8):

    El Greedy Algorithm (o l' algoritme més proper del barri) és molt senzill: comenceu en una ciutat a l'atzar i consecutivament aneu a la ciutat més propera que no heu visitat abans. Un cop hagueu visitat totes les ciutats, us atureu.

    L’animació en breu…

    Podeu demostrar que, de mitjana, les rutes que es troben amb l’algoritme greedy són un 25% més llargues que la ruta més curta possible.

    L’ algoritme de dues opcions comença amb una ruta aleatòria possible. A continuació, trieu repetidament dos vores i els canvieu si això reduiria la longitud del camí. Atureu-vos quan no podeu reduir la longitud encara més canviant cap parell d'arcs.

    L’animació en breu…

    Resulta que, molt abans que fins i tot existissin els ordinadors, la natura havia trobat una manera hàbil de trobar rutes òptimes entre diferents ubicacions: a les colònies de formigues.

    Les formigues volen trobar les rutes més curtes possibles entre el seu niu i les possibles fonts d'aliments. Es poden comunicar entre ells a través de productes químics que deixen al llarg del seu rastre i que poden seguir altres formigues.

    • La colònia de formigues envia molts exploradors que inicialment viatgen en indicacions aleatòries. Un cop troben menjar, tornen, deixant enrere un rastre de feromona. * Altres formigues acostumen a seguir un rastre quan en troben una, que les porta a menjar. Al seu viatge de tornada dipositen més feromones, reforçant així la pista. * Amb el temps, la feromona s’evapora. Com més llarg és el camí, més temps triga les formigues a recórrer-lo, de manera que la feromona té més temps per evaporar-se. Els camins curts, en canvi, es poden reforçar més ràpidament, de manera que la seva força augmenta més ràpidament.

    Diagrama que ve aviat ...

    Els algorismes ACS (Ant Colony System) de formiga intenten replicar aquest comportament als ordinadors, utilitzant moltes formigues "virtuals". Ràpidament poden trobar solucions molt bones per al problema del venedor en viatge.

    Una propietat particularment útil dels algorismes ACS és que poden funcionar contínuament i adaptar-se en temps real als canvis del gràfic. Aquests canvis es poden produir per accidents i tancaments de carreteres a les xarxes de carrers o per pics de trànsit als servidors web de les xarxes d’ordinadors.

    El problema del viatger venedor és NP , el que significa que és molt difícil resoldre’l per ordinadors (almenys per a un gran nombre de ciutats).

    Trobar un algoritme ràpid i exacte tindria serioses implicacions en el camp de la informàtica: significaria que hi ha algoritmes ràpids per a tots els problemes durs amb NP. A més, inutilitzaria la major part de la seguretat d’Internet, que es basa en el fet que alguns ordinadors creuen que són molt difícils per als ordinadors.

    Trobar un algorisme ràpid per resoldre el problema del venedor de viatges també solucionaria un dels problemes oberts més famosos en matemàtiques i informàtica, el problema P vs NP . És un dels set problemes del premi del Mil·lenni , cadascun d'ells amb un premi d'1 milió de dòlars.