Heuristica y el problema del agente viajero.

Heuristica

Procedimiento o método para solucionar problemas que no asegura la resolución, pero funciona bien.

Así definieron Bartholdi y Platzman (en 1988) lo que es heurística para ellos: 

“Una heurística puede verse como un procesador de información que, deliberadamente, peor juiciosamente, ignora cierta información. Ignorando información, una heurística se libra de gran parte del esfuerzo que debió haberse requerido para leer los datos y hacer cálculos con ellos. Por otra parte, la solución producida por tal heurística, es independiente de la información ignorada, y de este modo no se ve afectada por cambios en tal información. Idealmente, se busca ignorar información que resulta muy caro colectar y mantener, esto es, computacionalmente caro de explotar y mantener, y que contribuye en poco a la precisión de la solución.” 

El problema del agente viajero.

Un vendedor tiene una lista de ciudades cada una de las cuales debe visitar solamente una vez; existen carreteras directas entre cada par de ciudades de la lista. Se debe encontrar la ruta que el vendedor debería seguir para que, siguiendo el camino más corto posible, visitara todas las ciudades, comenzando por cualquiera de ellas y volviendo a la misma. Un ejemplo de éste tipo de problemas para seis ciudades se plantea en la figura 2.6. 

La heurística del vecino más próximo es un ejemplo de una buena heurística de propósito general válida para varios problemas combinatorios. Consiste en seleccionar en cada paso la alternativa localmente mejor.

Al aplicarse al problema del viajante de comercio, surge el siguiente proceso: 

1) Seleccionar arbitrariamente una ciudad de comienzo. 

2) Para seleccionar la siguiente ciudad, fijarse en las ciudades que todavía no se han visitado y 

seleccionar aquella que sea más cercana. Ir a esa ciudad. 

3) Repetir 2 hasta que todas las ciudades hayan sido visitadas. 

Este procedimiento se ejecuta en un tiempo proporcional al cuadrado de N, lo cual es una mejora significativa frente a N!. Lo que sucede es que, dependiendo de las características de cada problema en particular (sobre todo en lo referente a qué tan uniforme es la distribución de las ciudades en el plano), la solución puede estar más o menos cerca de la óptima.

REFERENCIAS
(1)https://sites.google.com/site/proyectointeligenciaartificial/indice/heurstica
(2)http://www.iiia.csic.es/~pedro/busqueda1-introduccion.pdf
(3)http://www.reocities.com/fuentesr_99/Ia.pdf
(4)http://catarina.udlap.mx/u_dl_a/tales/documentos/lii/martinez_g_ag/capitulo2.pdf
(5)http://materias.fi.uba.ar/7114/Docs/ApunteHeuristicas.pdf