Busqueta heuristica

*** BUSQUEDA HEURÌSTICA ***
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 nopueda 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 existeuna solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.
A menudo, pueden encontrarse instancias concretas del problema donde la heurística produciráresultados muy malos o se ejecutará muy lentamente. Aún así, estas instancias concretas pueden ser ignoradas porque no deberían ocurrir nunca en la práctica por ser de origen teórico. Por tanto, el uso deheurísticas es muy común en el mundo real.

* Supone la existencia de una función de evaluación que debe medir la distancia estimada al (a un) objetivo (h(n))
* Esta función de evaluación seutiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones más prometedores
* No siempre se garantiza encontrar una solución (de existir ésta)
* Nosiempre se garantiza encontrar la solución más próxima (la que se encuentra a una distancia, número de operaciones menor)
* Existen múltiples algoritmos:

* Branch and Bound, Best First Search* A, A_
* IDA_
* Búsqueda local (Hill climbing, Simulated annealing, Alg. Genéticos)



* BUSQUEDA BRANCH AND BOUND
Trabaja como best-first pero en cuanto se encuentra unasolución sigue expandiendo los nodos de costos menores al encontrado
|

|

* EJEMPLO DEL PROBLEMA DEL VIAJANTE DE COMERCIO
El problema del viajante es un ejemplo que muestra y analiza laproblemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.
La respuesta al problema es...