Page 55 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Si un problema no se puede resolver de forma matemática, es posible introducir una heurística para,
por medio de la experiencia, intentar llegar a un espacio que se acerque a la solución. Apoyándose
en la heurística, es posible formular un algoritmo que permita, en forma más sencilla, manejar la ex-
pertiz del individuo y conseguir un espacio cercano a la solución.

La palabra heurística proviene del griego euriskein, que significa ‘encontrar’. Este vocablo se volvió
muy popular gracias al libro Cómo resolverlo (How to solve it) de George Pólya publicado por la
Universidad de Princeton en 1945, en el cual se proponen muchas recetas para tratar de encontrar
solución a problemas complejos.

En optimización, la palabra heurística se utiliza para caracterizar a las técnicas por las cuales se
encuentra o se mejora la solución de un problema intratable. Los algoritmos heurísticos permiten ob-
tener “buenas soluciones” (soluciones subóptimas o cercanas al óptimo global) de problemas cuyos
algoritmos exactos de solución no son factibles en tiempo polinomial.
En computación es fundamental encontrar algoritmos con buen tiempo de ejecución y que propor-
cionen “buenas soluciones”; una heurística, por tanto, es un algoritmo que trata de satisfacer al me-
nos uno de estos requerimientos, cuando no ambos. Muchos algoritmos de inteligencia artificial son
heurísticos por naturaleza o usan reglas heurísticas (De los Cobos Silva, Goddard, Gutiérrez Andrade
y Martínez Licona, 2010).

Un ejemplo de esto se puede observar en el problema del agente viajero, del cual se explica en el
apartado 4.2 una solución matemática exacta por medio de la estrategia “programación dinámica”
(este problema es de naturaleza intratable), mientras que en el apartado 7.4 se muestra un algoritmo
heurístico para resolver el mismo problema por medio de la estrategia de ramificación y acotamiento.
Los problemas computacionales se pueden clasificar de forma general del siguiente modo:

1. Problemas de ordenación.

2. Problemas de búsqueda.
3. Problemas de optimización.

4. Problemas de decisión.
5. Problemas de clasificación.

En esta sección se estudiarán las estrategias clásicas para la resolución de la mayoría de los pro-
blemas en forma determinística, donde se encuentra la solución al problema dado. La mayoría
de los problemas clasificados de la categoría uno a la cuatro se puede resolver con alguna de estas
estrategias.

Existen problemas que tienen una solución en las estrategias conocidas como máquinas de aprendi-
zaje (heurísticas) o machine learning y generalmente sirven para encontrar un espacio factible cerca-

49