Recomendado, 2024

La Elección Del Editor

Diferencia entre la búsqueda informada y no informada

La búsqueda es un proceso de encontrar una secuencia de pasos necesarios para resolver cualquier problema. La diferencia previa entre la búsqueda informada y la no informada es que la búsqueda informada proporciona una guía sobre dónde y cómo encontrar la solución. A la inversa, la búsqueda no informada no proporciona información adicional sobre el problema, excepto su especificación.

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ónBúsqueda informadaBú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.
CostoBajoComparativamente alto
ActuaciónEncuentra la solución más rápidamenteLa 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 costoProfundidad 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

  1. 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.
  2. La eficiencia de la búsqueda informada es mejor que la búsqueda no informada.
  3. 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.
  4. 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.

Top