Diferencia entre revisiones de «Manual del estudiante de Ingeniería en Sistemas de UTN/Inteligencia Artificial/Búsqueda»

La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta un '''costo''' de <math>C^*</math> (costo óptimo), es decir, hasta una profundidad de <math> \frac{C^*}{ \epsilon }</math>, siendo <math> \epsilon </math> el costo más pequeño aplicable a una acción. Resolviendo la serie, la complejidad resulta de <math> O \left( b^{ \frac{C^*}{ \epsilon } } \right) </math>. La complejidad espacial será también de <math> O \left( b^{ \frac{C^*}{ \epsilon } } \right) </math>, ya que deben almacenarse al menos todos los nodos de la frontera.

 

== Definición ==

El nodo que más conviene expandir es el nodo a través del cual pasa el camino con menor costo. Sería útil contar con la información del costo total del camino que significaría atravesar cada nodo. La búsqueda de costo fijo estima este valor con el costo parcial de llegar a este nodo. En muchos casos, esto no es suficiente. No se puede contar con el valor exacto, esto implicaría tener el problema resuelto. Lo que puede hacerse es estimar el costo desde el nodo actual hasta el nodo final, de manera de expandir primero el nodo a través del cual se estime que se llegará a la solución con costo óptimo.