Sin embargo, entre las técnicas de búsqueda informadas y no informadas, la búsqueda informada es más eficiente y rentable.
Gráfica comparativa
| Bases para la comparación | Búsqueda informada | Búsqueda no informada |
|---|---|---|
| BASIC | Utiliza el conocimiento para encontrar los pasos a seguir para la solución. | Sin uso del conocimiento. |
| Eficiencia | Altamente eficiente ya que consume menos tiempo y costo. | La eficiencia es mediadora. |
| Costo | Bajo | Comparativamente alto |
| Actuación | Encuentra la solución más rápidamente | La velocidad es más lenta que la búsqueda informada |
| Algoritmos | Búsqueda en profundidad, búsqueda en amplitud y búsqueda en el menor costo | Profundidad heurística primera y amplitud primera búsqueda, y A * búsqueda |
Definición de búsqueda informada
La técnica de búsqueda informada utiliza el conocimiento específico del problema para dar una pista de la solución del problema. Este tipo de estrategia de búsqueda en realidad evita que los algoritmos tropiecen sobre el objetivo y la dirección hacia la solución. La búsqueda informada puede ser ventajosa en términos del costo donde la optimización se logra a costos de búsqueda más bajos.
Para buscar un costo de ruta óptimo en un gráfico implementando una estrategia de búsqueda informada, los nodos más prometedores n se insertan en la función heurística h (n). Luego, la función devuelve un número real no negativo que es un costo de ruta aproximado calculado desde el nodo n al nodo de destino.
Aquí, la parte más importante de la técnica informada es la función heurística que facilita la impartición del conocimiento adicional del problema al algoritmo. Como resultado, ayuda a encontrar el camino hacia la meta a través de los distintos nodos vecinos. Hay varios algoritmos basados en la búsqueda informada, como la búsqueda heurística de profundidad, la búsqueda heurística de primera, la búsqueda A *, etc. Entendamos ahora la búsqueda heurística en profundidad.
Profundidad heurística Primera búsqueda
Al igual que en el método de búsqueda de profundidad primero que se da a continuación, la búsqueda heurística de la primera búsqueda elige un camino pero atraviesa todos los caminos desde el camino seleccionado antes de elegir otro camino. Sin embargo, elige el mejor camino a nivel local. En los casos donde el valor heurístico más pequeño es la prioridad para la frontera, entonces se conoce como la mejor primera búsqueda.
Otro algoritmo de búsqueda informado es la búsqueda A *, que combina el concepto de las primeras y mejores primeras búsquedas de menor costo. Este método considera tanto el costo de la ruta como la información heurística en el proceso de búsqueda y selección de la ruta a expandir. Un costo total estimado de la ruta utilizado para cada ruta que reside en la frontera desde el inicio hasta el nodo de destino. Por lo tanto, utiliza dos funciones al mismo tiempo: el costo (p) es el costo de la ruta descubierta y h (p) es el valor estimado del costo de la ruta desde el nodo inicial hasta el nodo objetivo.
Definición de búsqueda no informada
La búsqueda no informada es diferente de la búsqueda informada en la forma en que solo proporciona la definición del problema pero no es un paso más para encontrar la solución al problema. El objetivo principal de la búsqueda no informada es diferenciar entre el estado objetivo y el estado no objetivo, e ignora totalmente el destino hacia el que se dirige en el camino hasta que descubre el objetivo e informa al sucesor. Esta estrategia también se conoce como una búsqueda a ciegas.
Hay varios algoritmos de búsqueda en esta categoría, como la búsqueda en profundidad, la búsqueda de costos uniformes, la búsqueda en la amplitud inicial, etc. Entendamos ahora el concepto detrás de la búsqueda no informada con la ayuda de la búsqueda en profundidad primero.
Primera búsqueda de profundidad
En la primera búsqueda en profundidad, se usa una pila de Último en primero en salir para agregar y eliminar los nodos. Solo se agrega o elimina un nodo a la vez y el primer elemento eliminado de la frontera de la pila sería el último elemento agregado a la pila. Al emplear la pila en los resultados de la frontera en la búsqueda de caminos se procedió en profundidad de primera manera. Cuando se realiza una búsqueda en la ruta más corta y óptima utilizando la búsqueda en profundidad, la ruta creada por los nodos adyacentes se completa primero, incluso si no es la deseada. Entonces, la ruta alternativa se busca a través de backtracking.
En otras palabras, el algoritmo elige la primera alternativa en cada nodo y luego retrocede a otra alternativa hasta que haya recorrido todas las rutas desde la primera selección. Esto también plantea un problema en el que la búsqueda puede dejar de detenerse debido a infinitos bucles (ciclos) presentes en el gráfico.
Diferencias clave entre la búsqueda informada y no informada
- La primera técnica de búsqueda informada utiliza el conocimiento para encontrar la solución. Por otro lado, la última técnica de búsqueda no informada no utiliza el conocimiento. En términos más simples, no se proporciona más información sobre la solución.
- La eficiencia de la búsqueda informada es mejor que la búsqueda no informada.
- La búsqueda no informada consume más tiempo y costo, ya que no tiene ni idea de la solución en comparación con la búsqueda informada.
- La búsqueda en profundidad, la búsqueda en amplitud y la búsqueda en primer costo más bajo son los algoritmos que entran en la categoría de la búsqueda no informada. Por el contrario, la búsqueda informada cubre los algoritmos, como la búsqueda heurística primero en profundidad, la búsqueda heurística en primer lugar y la búsqueda A *.
Conclusión
La búsqueda informada proporciona la dirección con respecto a la solución mientras que en la búsqueda no informada no se da ninguna sugerencia con respecto a la solución. Esto hace que la búsqueda no informada sea más larga cuando se implementa el algoritmo.
