Blog de la Biblioteca de Matemàtiques i Informàtica

Una competició per resoldre el Problema del viatjant

Deixa un comentari

Solució al problema del viatjant

Imatge de Xypron, de domini públic

El Problema del viatjant és un clàssic de les Matemàtiques i de la teoria de la computació, un mètode d’optimització de trajectòries que intenta resoldre el següent enunciat (Viquipèdia):

Donat un conjunt de nodes, es tracta de trobar l’ordre de visites a seguir per tal de definir una trajectòria que passi un sol cop per cada node i de manera que la distància total recorreguda sigui la més curta possible.

S’usa sovint en el disseny de xarxes de transport i de serveis i en la planificació logística. Naturalment, com més nodes hi ha, s’incrementa la dificultat i es necessita més temps de càlcul per optimitzar la ruta.

Quatre membres del Game Intelligence Group de la Facultat de Ciències de la Computació i Electrònica de la Universitat d’Essex —Diego Pérez, Philipp Rohlfshagen, David Robles i Simón Lucas— han organitzat un concurs, The Physical Travelling Salesman Problem Competition (PTSP), basat en el problema i amb la particularitat que hi poden participar éssers humans i bots.

L’objectiu del PTSP és fer passar la nau per tots els punts vermells sense repetir-ne cap i amb el menor temps possible. El vídeo mostra un exemple d’execució del joc amb un jugador humà.

Hi ha classificacions per a humans i per a bots, però també per a humans contra bots. Com a curiositat, entre els 5 primers classificats hi ha 4 jugadors humans i un bot, aquest en segona posició.

Font: Microsiervos

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out / Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out / Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out / Canvia )

Google+ photo

Esteu comentant fent servir el compte Google+. Log Out / Canvia )

Connecting to %s