Heuristica y el problema del viajero

Heurística

La palabra heurística significa hallar o inventar, en disciplina científica se aplica a cualquier ciencia e incluye la elaboración de cambios auxiliares, principios, reglas, estrategias  y programas que faciliten resolver tareas de cualquier tipo.

Según Horst Müller:

 Los procedimientos heurísticos son formas de trabajo y de pensamiento que apoyan la realización consciente de actividades mentales exigentes.

Los procedimientos heurísticos como método científico pueden dividirse en principios, reglas y estrategias.

1. Principios heurísticos: Constituyen sugerencias para encontrar (directamente) la idea de solución; posibilita determinar, por tanto, a la vez, los medios y la vía de solución. Dentro de estos principios se destacan la analogía y la reducción.

1. Reglas heurísticas: Actúan como impulsos generales dentro del proceso de búsqueda y ayudan a encontrar, especialmente, los medios para resolver los problemas.

Las Reglas heurísticas que más se emplean son:

1. Separar lo dado de lo buscado.
2. Confeccionar figuras de análisis: esquemas, tablas, mapas, etc.
3. Representar magnitudes dadas y buscadas con variables.
4. Determinar si se tienen fórmulas adecuadas.
5. Utilizar números (estructuras más simples) en lugar de datos.
6. Reformular el problema.

1. Estrategias heurísticas: Se comportan como recursos organizativos del proceso de resolución, que contribuyen especialmente a determinar la vía de solución del problema abordado. Existen dos estrategias:
2. El trabajo hacia adelante: se parte de lo dado para realizar las reflexiones que han de conducir a la solución del problema.
3. El trabajo hacia atrás: se examina primeramente lo que se busca y, apoyándose de los conocimientos que se tienen, se analizan posibles resultados intermedios de lo que se puede deducir lo buscado, hasta llegar a los dados.

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas.

Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas tiempo, espacio, etc.

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.

En principio se puede resolver éste problema explorando el árbol de todos los caminos posibles y eligiendo aquél que tenga la longitud mínima; pero, si existen n ciudades, el número de caminos diferentes entre ellas es (n-1)!, esto significa que el tiempo requerido para resolver el problema es proporcional a n!. Por lo tanto, si tenemos once ciudades, (11-1)! = 10*9*8*7*6*5*4*3*2*1 = 3, 628,000 rutas son posibles, es decir, se trata de un problema típico de explosión combinatoria en el que es útil aplicar técnicas heurísticas.

Una técnica heurística de propósito general que es útil para resolver problemas combinatorios es el 'algoritmo del vecino más próximo', que trabaja seleccionando la alternativa más cercana que aún no ha sido visitada y así sucesivamente hasta recorrer todos los nodos y retornar al punto de partida:

1. Seleccionar arbitrariamente una ciudad de partida.

2. Para seleccionar la siguiente ciudad, analizar todas las ciudades que aún no se han visitado y seleccionar aquélla que sea la más cercana a la ciudad actual; ir a ella en el siguiente paso.

3. Repetir el paso dos hasta que se hayan visitado todas las ciudades. éste algoritmo se ejecuta en un tiempo proporcional al cuadrado de n lo que representa una mejora significativa sobre n!.” (Edgar Altamirano Carmona 2014, p.11, 12)

El algoritmo del agente viajero se puede representar de la siguiente manera:

Definir el número de nodos, su posición y el costo por cada arista (i, j) donde i = ciudad 1 y j = ciudad 2

Elegir el nodo inicial i

Hacer

Si el nodo más cercano no se ha visitado

Visitar nodo j

Actualizar lista de nodos visitados

Costo_total = costo_total + costoij

Nodo i = nodo j

Hasta haber visitado todos los nodos

Conclusión:

Por heurística entendemos una estrategia, método, criterio o truco usado para hacer más sencilla la solución de problemas difíciles. El conocimiento heurístico es un tipo especial de conocimiento usado por los humanos para resolver problemas complejos.

En el área de computación su objetivo primordial es encontrar algoritmos con buenos tiempos de ejecución y que de buenas soluciones, preferentemente óptimas.

En el caso del problema del agente viajero se debe encontrar la ruta más corta que sea posible, es ahí donde entra la heurística porque le da la solución más óptima.

Bibliografía:

APUNTES DE INTELIGENCIA ARTIFICIAL

Edgar Altamirano Carmona    

Universisda Autónoma De Guerrero, 2014

ISC. Patricia Horta Rosado

Inteligencia Artificial (n.d.). Evaluando las Fuentes Electrónicas. Consultado el 17 de marzo del 2014. , página web  Instituto Tecnológico de Veracruz. http://ia.comeze.com/subtemas/un1/1.7.html