in

Algoritmos de búsqueda informados en IA

informed search algorithms

Hasta ahora hemos hablado de los algoritmos de búsqueda desinformados que buscaban en el espacio de búsqueda todas las posibles soluciones del problema sin tener ningún conocimiento adicional sobre el espacio de búsqueda. Pero el algoritmo de búsqueda informado contiene una serie de conocimientos tales como qué tan lejos estamos del objetivo, costo de la ruta, cómo llegar al nodo objetivo, etc. Este conocimiento ayuda a los agentes a explorar menos en el espacio de búsqueda y encontrar de manera más eficiente el nodo objetivo.

El algoritmo de búsqueda informado es más útil para espacios de búsqueda grandes. El algoritmo de búsqueda informado utiliza la idea de heurística, por lo que también se denomina búsqueda heurística.

Función heurística: La heurística es una función que se utiliza en la búsqueda informada y encuentra la ruta más prometedora. Toma el estado actual del agente como entrada y produce la estimación de qué tan cerca está el agente del objetivo. Sin embargo, es posible que el método heurístico no siempre dé la mejor solución, pero garantiza encontrar una buena solución en un tiempo razonable. La función heurística estima qué tan cerca está un estado de la meta. Está representado por h (n) y calcula el costo de una ruta óptima entre el par de estados. El valor de la función heurística es siempre positivo.

La admisibilidad de la función heurística se da como:

Aquí h (n) es el costo heurístico y h * (n) es el costo estimado. Por lo tanto, el costo heurístico debe ser menor o igual al costo estimado.

Búsqueda heurística pura:

La búsqueda heurística pura es la forma más simple de algoritmos de búsqueda heurística. Expande los nodos en función de su valor heurístico h (n). Mantiene dos listas, lista ABIERTA y CERRADA. En la lista CERRADO, coloca aquellos nodos que ya se han expandido y en la lista ABIERTA, coloca los nodos que aún no se han expandido.

En cada iteración, cada nodo n con el valor heurístico más bajo se expande y genera todos sus sucesores yn se coloca en la lista cerrada. El algoritmo continúa hasta que se encuentra un estado objetivo.

En la búsqueda informada, discutiremos dos algoritmos principales que se dan a continuación:

  • Mejor algoritmo de primera búsqueda (búsqueda codiciosa)
  • Algoritmo de búsqueda A *

1.) Algoritmo de búsqueda del mejor primero (búsqueda codiciosa):

El codicioso algoritmo de búsqueda del mejor primero siempre selecciona la ruta que aparece mejor en ese momento. Es la combinación de algoritmos de búsqueda en profundidad y búsqueda en amplitud. Utiliza la función heurística y la búsqueda. La búsqueda «Best-first» nos permite aprovechar las ventajas de ambos algoritmos. Con la ayuda de la búsqueda del mejor primero, en cada paso, podemos elegir el nodo más prometedor. En el mejor algoritmo de primera búsqueda, expandimos el nodo más cercano al nodo objetivo y el costo más cercano se estima por función heurística, es decir

Fueron, h (n) = costo estimado desde el nodo n hasta la meta.

El primer algoritmo codicioso mejor es implementado por la cola de prioridad.

Mejor algoritmo de primera búsqueda:

  • Paso 1: Coloque el nodo inicial en la lista ABIERTA.
  • Paso 2: Si la lista ABIERTA está vacía, Deténgase y vuelva a fallar.
  • Paso 3: Elimine el nodo n de la lista ABIERTO que tiene el valor más bajo de h (n) y lo coloca en la lista CERRADO.
  • Paso 4: Expanda el nodo n y genere los sucesores del nodo n.
  • Paso 5: Compruebe cada sucesor del nodo n y averigüe si algún nodo es un nodo objetivo o no. Si algún nodo sucesor es el nodo objetivo, devuelva el resultado correcto y finalice la búsqueda; de lo contrario, continúe con el Paso 6.
  • Paso 6: Para cada nodo sucesor, el algoritmo verifica la función de evaluación f (n) y luego verifica si el nodo ha estado en la lista ABIERTO o CERRADO. Si el nodo no ha estado en ambas listas, agréguelo a la lista ABIERTA.
  • Paso 7: Regrese al paso 2.

Ventajas:

  • La mejor primera búsqueda puede cambiar entre BFS y DFS al obtener las ventajas de ambos algoritmos.
  • Este algoritmo es más eficiente que los algoritmos BFS y DFS.

Desventajas:

  • Puede comportarse como una búsqueda en profundidad no guiada en el peor de los casos.
  • Puede atascarse en un bucle como DFS.
  • Este algoritmo no es óptimo.

Ejemplo:

Considere el problema de búsqueda a continuación, y lo atravesaremos utilizando la búsqueda codiciosa del mejor primero. En cada iteración, cada nodo se expande utilizando la función de evaluación f (n) = h (n), que se muestra en la siguiente tabla.

Algoritmos de búsqueda informados

En este ejemplo de búsqueda, estamos usando dos listas que son ABIERTO y CERRADO Liza. A continuación se muestra la iteración para recorrer el ejemplo anterior.

Algoritmos de búsqueda informados

Expanda los nodos de S y colóquelos en la lista CERRADO

Inicialización: Abierto [A, B], Cerrado [S]

Iteración 1: Abierto [A], Cerrado [S, B]

Iteración 2: Abierto [E, F, A], Cerrado [S, B]
: Abierto [E, A], Cerrado [S, B, F]

Iteración 3: Abierto [I, G, E, A], Cerrado [S, B, F]
: Abierto [I, E, A], Cerrado [S, B, F, G]

Por lo tanto, la ruta de la solución final será: S —-> B —–> F —-> G

Complejidad del tiempo: La complejidad de tiempo en el peor de los casos de la primera búsqueda de Greedy best es O (bmetro).

Complejidad espacial: La complejidad espacial en el peor de los casos de la primera búsqueda de Greedy best es O (bmetro). Donde, m es la profundidad máxima del espacio de búsqueda.

Completo: La búsqueda codiciosa de lo mejor primero también está incompleta, incluso si el espacio de estado dado es finito.

Óptimo: El mejor algoritmo de primera búsqueda codicioso no es óptimo.

2.) Algoritmo de búsqueda A *:

Una * búsqueda es la forma más comúnmente conocida de búsqueda del mejor primero. Utiliza la función heurística h (n) y el costo para alcanzar el nodo n desde el estado inicial g (n). Tiene características combinadas de UCS y búsqueda codiciosa del mejor primero, mediante las cuales resuelve el problema de manera eficiente. Un algoritmo de búsqueda * encuentra la ruta más corta a través del espacio de búsqueda utilizando la función heurística. Este algoritmo de búsqueda expande menos el árbol de búsqueda y proporciona un resultado óptimo más rápido. Un algoritmo * es similar a UCS excepto que usa g (n) + h (n) en lugar de g (n).

En el algoritmo de búsqueda A *, utilizamos la heurística de búsqueda, así como el costo para llegar al nodo. Por lo tanto, podemos combinar ambos costos de la siguiente manera, y esta suma se llama como número de fitness.

Algoritmos de búsqueda informados

En cada punto del espacio de búsqueda, solo se expanden los nodos que tienen el valor más bajo de f (n), y el algoritmo termina cuando se encuentra el nodo objetivo.

Algoritmo de búsqueda A *:

Paso 1: Coloque el nodo inicial en la lista ABIERTA.

Paso 2: Compruebe si la lista ABIERTA está vacía o no, si la lista está vacía, devuelva el error y se detiene.

Paso 3: Seleccione el nodo de la lista ABIERTA que tenga el valor más pequeño de la función de evaluación (g + h), si el nodo n es el nodo objetivo, devuelva el éxito y deténgase, de lo contrario

Paso 4: Expanda el nodo ny genere todos sus sucesores y coloque n en la lista cerrada. Para cada sucesor n ‘, verifique si n’ ya está en la lista ABIERTA o CERRADA, de lo contrario, calcule la función de evaluación para n ‘y colóquela en la lista Abierta.

Paso 5: De lo contrario, si el nodo n ‘ya está ABIERTO y CERRADO, entonces debe adjuntarse al puntero trasero que refleja el valor más bajo de g (n’).

Paso 6: Volver a Paso 2.

Ventajas:

  • Un algoritmo de búsqueda * es el mejor algoritmo que otros algoritmos de búsqueda.
  • Un * algoritmo de búsqueda es óptimo y completo.
  • Este algoritmo puede resolver problemas muy complejos.

Desventajas:

  • No siempre produce el camino más corto, ya que se basa principalmente en heurísticas y aproximaciones.
  • Un algoritmo de búsqueda * tiene algunos problemas de complejidad.
  • El principal inconveniente de A * es el requisito de memoria, ya que mantiene todos los nodos generados en la memoria, por lo que no es práctico para varios problemas a gran escala.

Ejemplo:

En este ejemplo, recorreremos el gráfico dado utilizando el algoritmo A *. El valor heurístico de todos los estados se da en la siguiente tabla, por lo que calcularemos el f (n) de cada estado usando la fórmula f (n) = g (n) + h (n), donde g (n) es el costo para llegar a cualquier nodo desde el estado inicial. Aquí usaremos la lista ABIERTA y CERRADA.
Algoritmos de búsqueda informados

Solución:

Algoritmos de búsqueda informados

Inicialización: {(S, 5)}

Iteración1: {(S -> A, 4), (S -> G, 10)}

Iteración2: {(S -> A -> C, 4), (S -> A -> B, 7), (S -> G, 10)}

Iteración3: {(S -> A -> C —> G, 6), (S -> A -> C —> D, 11), (S -> A -> B, 7), (S -> G, 10)}

Iteración 4 dará el resultado final, como S —> A —> C —> G proporciona la ruta óptima con un costo 6.

Puntos para recordar:

  • Un algoritmo * devuelve la ruta que ocurrió primero y no busca todas las rutas restantes.
  • La eficiencia del algoritmo A * depende de la calidad de la heurística.
  • Un algoritmo * expande todos los nodos que satisfacen la condición f (n)

Completo: Un * algoritmo está completo siempre que:

  • El factor de ramificación es finito.
  • El costo de cada acción es fijo.

Óptimo: Un algoritmo de búsqueda * es óptimo si sigue las siguientes dos condiciones:

  • Admisible: la primera condición requerida para la optimización es que h (n) debe ser una heurística admisible para la búsqueda de árbol A *. Una heurística admisible es de naturaleza optimista.
  • Consistencia: La segunda condición requerida es la coherencia solo para la búsqueda de gráficos A *.

Si la función heurística es admisible, la búsqueda de árbol A * siempre encontrará la ruta de menor costo.

Complejidad del tiempo: La complejidad temporal del algoritmo de búsqueda A * depende de la función heurística, y el número de nodos expandidos es exponencial a la profundidad de la solución d. Entonces, la complejidad del tiempo es O (b ^ d), donde b es el factor de ramificación.

Complejidad espacial: La complejidad espacial del algoritmo de búsqueda A * es O (b ^ d)


Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Tipos de datos de JavaScript

if statement

Secuencia de comandos por lotes: declaración If