busqueda A* y error heuristico

[silvestre]

Hola:

Estoy haciendo un estudio de la relacion entre el error de las funciones heuristicas admisibles y la complejidad temporal de la búsqueda.

Ya tengo todo el material teorico, pero me piden tb algún aporte de alguna investigacion sobre esto a lo largo del tiempo.

¿Alguien sabe de donde puedo sacar algo o controla algo de este tema?

Graciñas

[TrOnTxU]

Hola:

Estoy haciendo un estudio de la relacion entre el error de las funciones heuristicas admisibles y la complejidad temporal de la búsqueda.

Ya tengo todo el material teorico, pero me piden tb algún aporte de alguna investigacion sobre esto a lo largo del tiempo.

¿Alguien sabe de donde puedo sacar algo o controla algo de este tema?

Graciñas

¿Estás haciendo un proyecto de final de carrera?
¿Sabes realmente que te están pidiendo?

Creo que deberias conocer que tipo de problema vas a tratar, ya que las funciones heurísticas varian dependiendo del problema.
Si estamos hablando del típico problema de PathFinding creo que encontrarás bastante información en GameDev.net.
También pueces mirarte (si sabes donde encontrarlos, o estás dispuesto a gastarte la pasta) en los libros "AI Game Programming Wisdom", y la sección de IA de los "Game Programming Gems".

De todas formas, y si es un proyecto de final de carrera o algo parecido, puede que sea interesante (o que de hecho sea una de las partes que te están pidiendo) que te hagas un programita que te haga de "benchmarck" para saber cual es el coste temporal (tiempo y/o nodos explorados) y espacial (memoria que necesita el algoritmo) de cada una de las heurísticas que quieras probar.
Yo hicé uno para una práctica hace algún tiempo con un problema de puzzle-slide (típico de mover el hueco) en el que calculaba los costes para "X" problemas aleatorios, y/o para una lista de problemas defindos por el usuario. Yo, personalmente, resolvia cada problema con todas las heurísticas que queria probar y guardaba sus costes. Puedes hacer estudios, más tarde, con el "gnuplot", por ejemplo, si guardas correctamente los datos en un archivo de texto.