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.
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.
- 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.
- 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:
- Separar lo dado de lo buscado.
- Confeccionar figuras de análisis: esquemas,
tablas, mapas, etc.
- Representar magnitudes dadas y buscadas
con variables.
- Determinar si se tienen fórmulas
adecuadas.
- Utilizar números (estructuras más
simples) en lugar de datos.
- Reformular el problema.
- 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:
- El trabajo hacia adelante: se parte de lo dado para realizar las
reflexiones que han de conducir a la solución del problema.
- 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
