En el problema del viajante de comercio (TSP) tenemos un conjunto de nodos, donde un nodo es el nodo inicial. La tarea es encontrar el recorrido más corto comenzando en el nodo de inicio visitando cada nodo exactamente una vez. Una variante del TSP más general es el TSP euclidiano , donde la distancia entre dos ciudades es la distancia euclidiana habitual. También se pueden considerar diferentes métricas, como la métrica de bloque de ciudad .
Con base en datos experimentales en [1], los autores afirman que las instancias TSP euclidianas son fáciles para los humanos. También recopilaron datos sobre el caso en que la métrica utilizada es la métrica de manzana. Señalan que "... las personas son casi óptimas para estos problemas en ambas métricas".
[1] Walwyn, AL y Navarro, DJ (2010). Caminos Mínimos en la Manzana: Desempeño Humano en Problemas Euclidianos y No Euclidianos de Vendedores Ambulantes. Diario de resolución de problemas, 3(1), 5.
Rápidamente busqué esto en Google Scholar y encontré la siguiente referencia interesante:
Este documento afirma que "la complejidad de los TSP es una función del número de puntos no fronterizos, no del número total de puntos". Definen un punto no límite como un punto dentro del casco convexo que abarca todos los puntos del problema. Este documento también hace algunas observaciones interesantes sobre el espacio de percepción para los humanos en esta tarea, afirmando que el problema parece ser resuelto por humanos en un espacio de problema 2D que coincide con el espacio de percepción 2D. Finalmente, las referencias citadas en este documento indican que al menos algunas investigaciones han abordado la cuestión del desempeño humano en el TSP desde fines de la década de 1960.
Parece que también puede obtener algunos consejos útiles siguiendo el gráfico de citas de este artículo en el tiempo: http://scholar.google.com/scholar?cites=9195299723226128892
Wuschelbeutel Kartoffelhuhn