Las heurísticas y el problema del viajante

Índice

Introducción        3

La Heurística        4

Antecedentes        5

Aplicaciones        7

Funcionamiento        7

Heurísticas de construcción y de mejoramiento.        8

Las heurísticas y el problema del viajante.        9

Heurísticas de construcción para el problema del viajante.        10

Heurísticas de mejoramiento para el problema del viajante.        11

Ventajas y desventajas        12

Ventajas        12

Desventajas        12

Conclusión        13

Bibliografía        14

Introducción

Desde el mero inicio de la humanidad, los humanos se han desplazado sobre la historia con el objetivo de alcanzar mejorar sus vidas, esto es haciéndola más sencilla o incluyendo en ella comodidades que antes no existían, pasando de casar con las manos hasta casar con herramientas de piedra en la era de piedra y reformulando estas en la edad de bronce y posterior edad de hierro. La humanidad y sus avances se ha debido a la mera búsqueda por el confort final y es precisamente a esto que surgen métodos como los que abordaremos en este trabajo.

La etimología de heurística es la misma que la de la palabra Eureka. La historia cuenta que Arquímedes pronunció esta palabra tras descubrir que el volumen de agua que asciende es igual al volumen del cuerpo sumergido. Esto le llevó la solución al problema de medir el volumen de cuerpos irregulares y le permitió saber si la corona del rey Hierón II estaba hecha de oro puro al calcular su densidad a partir de la masa ya conocida. Este hallazgo lo habría realizado mientras se encontraba sumergido en la bañera y tal fue su alegría que salió corriendo a las calles de Siracusa desnudo gritando ¡Eureka!

La heurística nace como atajo conveniente a los problemas muy complejos a los que se enfrenta la ciencia, donde abordando el mismo problema con una óptica distinta logra simplificar el problema basándose en la propia experiencia.

La Heurística

La heurística es "el tesoro del análisis o el arte de resolver problemas". También ha sido definido como "los procedimientos de la resolución de problemas que involucra concebir una respuesta hipotética un problema dado".

Los métodos heurísticos son estrategias generales de resolución y reglas de decisión utilizadas por los solucionadores de problemas, basadas en la experiencia previa con problemas similares. Estas estrategias indican las vías o posibles enfoques a seguir para alcanzar una solución.

El método heurístico considera que podemos inferir las conexiones y  las relaciones entre los elementos para identificar y construir caminos alternativos de solución y que  esto es posible debido a nuestros conocimientos y experiencias pasadas sobre la materia, es decir, en nuestras experiencias previas tenemos los referentes que orientan nuestro proceso de resolución de problemas, por lo que el punto de partida para  cada trabajo será precisamente retomar lo que sabes e intuyes sobre la solución de problemas.

Podemos definir una heurística como una técnica que aumenta la eficiencia de un proceso de búsqueda, posiblemente sacrificando demandas de completitud. Las heurísticas son como los guías de turismo: resultan adecuados en el sentido de que generalmente suelen indicar las rutas interesantes; son malos en el sentido de que pueden olvidar puntos de interés para ciertas personas. Al usar buenas heurísticas se pueden expresar buenas (aunque posiblemente no óptimas) soluciones a problemas difíciles, como el del viajante de comercio.

Una función heurística es una correspondencia entre las descripciones de estados del problema hacia alguna medida de deseabilidad, normalmente representada por números. Quiere decir que mensura cada estado del problema (solución) y dice qué tan cerca de la solución óptima está.

El propósito de una función heurística es el de guiar el proceso de búsqueda en la dirección más provechosa sugiriendo qué camino tomar cuando hay más de uno disponible. Cuanto más exactamente estime la función heurística los méritos de cada nodo del árbol (o grafo) que representa al problema, más directo será el proceso de solución.

Antecedentes

Heurística es la capacidad de un sistema para realizar de forma inmediata innovaciones positivas para sus fines. La capacidad heurística es un rasgo característico de los humanos, desde cuyo punto de vista puede describirse como el arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad y el pensamiento lateral o pensamiento divergente.

La palabra heurística procede del término griego εὑρίσκειν, que significa “hallar, inventar” (etimología que comparte con eureka). La palabra “heurística” aparece en más de una categoría gramatical. Cuando se usa como sustantivo, identifica el arte o la ciencia del descubrimiento, una disciplina susceptible de ser investigada formalmente. Cuando aparece como adjetivo, se refiere a cosas más concretas, como estrategias heurísticas, reglas heurísticas o silogismos y conclusiones heurísticas. Claro está que estos dos usos están íntimamente relacionados ya que la heurística usualmente propone estrategias heurísticas que guían el descubrimiento.

La popularización del concepto se debe al matemático George Pólya, con su libro Cómo resolverlo (How to solve it). Habiendo estudiado tantas pruebas matemáticas desde su juventud, quería saber cómo los matemáticos llegan a ellas. El libro contiene la clase de recetas heurísticas que trataba de enseñar a sus alumnos de matemáticas. Cuatro ejemplos extraídos de él ilustran el concepto mejor que ninguna definición:

• Si no consigues entender un problema, dibuja un esquema.
• Si no encuentras la solución, haz como si ya la tuvieras y mira qué puedes deducir de ella (razonando a la inversa).
• Si el problema es abstracto, prueba a examinar un ejemplo concreto.
• Intenta abordar primero un problema más general (es la “paradoja del inventor”: el propósito más ambicioso es el que tiene más posibilidades de éxito).

El estudio de la heurística en la toma de decisiones humanas fue desarrollado en los años 70 y 80 por los psicólogos israelíes Amos Tversky y Daniel Kahneman, aunque el concepto fue presentado originalmente por el premio Nobel Herbert A. Simon. El objetivo primordial de investigación de Simon era la resolución de problemas que mostraba que operamos dentro de lo que él llama racionalidad limitada. Él acuñó el término "satisficing", que denota la situación donde la gente busca soluciones o acepta opciones o juicios que son "suficientemente buenos" para sus propósitos, pero podrían ser optimizados.

...