Heurísticas

[Matías Delbono]

Buen día profes,

¿Cómo están?

Quería hacerles una consulta. Cómo debería razonar la elección de la mejor heurística para un determinado enunciado? Qué debería tener en cuenta?

Desde ya muchas gracias y saludos!

[fisa]

Buenas!

Depende mucho del enunciado. Pero las tres cosas que diría que siempre importan, son:

- Tiene que ser admisible. Nunca sobreestimar, porque eso rompe la optimalidad de A*.

- Tiene que intentar acercarse lo mejor que pueda al costo real, estimarlo de alguna forma. Por ejemplo, "return 0" es siempre admisible pero completamente inútil y no realmente una "heurística", porque no estima de ninguna forma el costo. Una heurística es mejor cuanto más se acerque al costo real. Y SOLO entre heurísticas que son admisibles, es fácil elegir cuando una siempre da un número igual o mayor que otra: la primera siempre va a estar más cerca del costo real que la segunda (esto NO aplica si no son admisibles).

- Tiene que ser relativamente rápida de calcular. La heurística se calcula para el estado de cada nodo que se agrega a la frontera, así que si es un proceso super complejo que toma mucho tiempo de cómputo, puede terminar siendo contraproducente (puede costar más calcular y usar la heurística, que directamente resolver el problema usando otra heurística menos precisa pero más rápida de calcular).

Saludos!

--
You received this message because you are subscribed to the Google Groups "UCSE IA" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ucse-ia+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/ucse-ia/e554bbfe-bacd-4f54-9215-204bed2aa543n%40googlegroups.com.

--

fisa  -  Juan Pedro Fisanotti

[Santi Andermatten]

Profe aprovecho a preguntar, una heurística que es admisible puede también ser consistente, pero una heurística consistente debe siempre ser admisible?

To view this discussion visit https://groups.google.com/d/msgid/ucse-ia/CAN7o839r63ooToJGLS%3DHy5ecNuMUUZbQMYBS2Yiu-DjzTFm%2BcA%40mail.gmail.com.

[Matías Delbono]

Muchas gracias Fisa! En caso de presentarse con simbología, como en los parciales/recuperatorios, cuál sería una manera rápida de realizar los cálculos relativos, por ejemplo, a la admisibilidad?

De nuevo gracias!

Saludos!

To view this discussion visit https://groups.google.com/d/msgid/ucse-ia/CAN7o839r63ooToJGLS%3DHy5ecNuMUUZbQMYBS2Yiu-DjzTFm%2BcA%40mail.gmail.com.

[fisa]

Buenas!

Santiago:

Es demostrable que si una heurística es consistente, entonces también es admisible. O sea, no puede ser solo consistente. O es nada, o es solo admisible, o es admisible y consistente.

Matías:

No hay una manera rápida más allá de entender qué está midiendo la heurística dada, y analizar si eso puede o no pasarse del costo real, y entre las que no se pasan, ver cuáles dan valores más altos. Para la admisibilidad, siempre ayuda mucho pensar ejemplos y situaciones del problema donde esa heurística te pueda estar haciendo pensar que vas a tener que hacer más cosas de las que realmente hacen falta para llegar a la solución (ej: hacer más  viajes de los necesarios, mover más piezas de las que hacen falta, realizar más acciones de lo que se necesita, etc).

Saludos!

To view this discussion visit https://groups.google.com/d/msgid/ucse-ia/CABcg4ZiABYaizt09r1ayObxjsyRtYXHQgO2ALtHhPbpkw5Ws_g%40mail.gmail.com.

[Matías Delbono]

Muchas gracias Fisa!

To view this discussion visit https://groups.google.com/d/msgid/ucse-ia/CAN7o83-5ziT%2BriKA6PCDrV1dQE1MN_4VTtLKGmi50gH%2Btvmg9Q%40mail.gmail.com.