Todo sobre Búsqueda Informada en Inteligencia Artificial

La búsqueda informada es un tipo de algoritmo de búsqueda que utiliza conocimientos específicos del dominio para guiar su búsqueda a través de un espacio problemático. Desde los sistemas de navegación hasta los juegos, el procesamiento del lenguaje natural hasta la gestión de la cadena de suministro y la búsqueda más informada en inteligencia artificial ha reducido significativamente la cantidad de tiempo y recursos computacionales necesarios para resolver diferentes problemas.

Mediante el uso de conocimientos específicos del dominio para guiar la búsqueda, los algoritmos de búsqueda informados pueden eliminar rápidamente las rutas irrelevantes o menos prometedoras, lo que permite que la búsqueda se centre en las opciones más prometedoras. Para ello, este tipo de algoritmos de búsqueda en IA utilizan heurísticas para mejorar la eficiencia y la velocidad de la búsqueda.

Inscríbase en el curso de aprendizaje automático de las mejores universidades del mundo. Obtenga programas Master, Executive PGP o Advanced Certificate para acelerar su carrera.

Este artículo discutirá el concepto de búsqueda informada en inteligencia artificial, sus funciones heurísticas, ejemplos de algoritmos y sus ventajas y desventajas.

Función heurística

En términos simples, una función heurística es un enfoque de resolución de problemas que utiliza una regla empírica o una "mejor suposición" para estimar la distancia o el costo hasta un estado objetivo en un problema de búsqueda. La función heurística estima qué tan lejos está el estado del objetivo del estado actual, lo que se puede usar para guiar un algoritmo de búsqueda hacia el objetivo.

Los algoritmos de búsqueda informados utilizan estas funciones como una fuente adicional de información para tomar decisiones informadas sobre qué camino tomar. Por esta razón, las funciones heurísticas son esenciales en los algoritmos de búsqueda informada.

Ejemplos de la vida real de la función heurística

Para comprender mejor las funciones heurísticas, aquí hay algunos ejemplos de la vida real:

• En el clásico juego de "rompecabezas de mosaicos deslizantes", una función heurística simple podría ser contar el número de mosaicos fuera de lugar en la configuración actual en comparación con la configuración del objetivo. Cuantas más fichas estén fuera de lugar, más lejos estará el estado actual del estado objetivo.
• En el ajedrez, una función heurística podría ser asignar un valor a cada pieza del tablero en función de su fuerza y ​​posición relativas y usar la suma de esos valores para estimar la ventaja o desventaja del jugador actual. Esta función heurística se puede usar para guiar un algoritmo de búsqueda hacia movimientos que probablemente resulten en una mejor posición.

Con eso resuelto, avancemos y comprendamos algunos de los ejemplos más utilizados de algoritmos de búsqueda informada en inteligencia artificial.

Ejemplos de algoritmos de búsqueda informados

Dos de los algoritmos de búsqueda informados más utilizados incluyen la mejor primera búsqueda y la búsqueda A*. Comprendamos estos dos algoritmos junto con algunos ejemplos, ventajas, desventajas y su implementación en Python:

1. Mejor primera búsqueda

La mejor primera búsqueda es un algoritmo de búsqueda que expande primero el nodo más prometedor, de acuerdo con una función heurística. El algoritmo comienza en el nodo inicial y examina todos sus nodos secundarios, eligiendo al secundario con el valor heurístico más bajo como el siguiente nodo a explorar. Este proceso continúa hasta que se encuentra el nodo objetivo o se exploran todos los nodos.

Mejor primera búsqueda: un ejemplo ilustrado

Aquí hay un ejemplo simple para ilustrar la mejor primera búsqueda:

Suponga que está tratando de encontrar la ruta más corta desde su casa hasta una tienda de comestibles cercana. Conoce la distancia a la tienda de comestibles desde algunos lugares cercanos, pero no sabe la ruta exacta que debe tomar. Para resolver este problema utilizando la búsqueda de mejor primero, podría:

1. Comience en la ubicación de su hogar y calcule el valor heurístico para cada ubicación cercana en función de su distancia a la tienda de comestibles.
2. Elija la ubicación cercana con el valor heurístico más bajo como el siguiente nodo para explorar.
3. Calcule el valor heurístico para cada una de las ubicaciones de sus hijos desde esa ubicación cercana y elija la que tenga el valor heurístico más bajo como el siguiente nodo para explorar.
4. Repita este proceso hasta llegar a la tienda de comestibles.

Mejor primera búsqueda: implementación de Python

Así es como puede implementar el mejor algoritmo de primera búsqueda en Python:

montón de importaciónq

def mejor_primera_búsqueda(estado_inicio, estado_objetivo, función_heurística, función_acciones, función_costo):

# inicializar la frontera y el conjunto explorado

frontera = [(función_heurística(estado_inicial, estado_objetivo), estado_inicial)]

explorado = establecer ()

# inicializar la ruta y el costo

camino = {}

costo = {}

ruta[start_state] = Ninguno

costo[start_state] = 0

mientras que la frontera:

# obtener el nodo con el valor heurístico más bajo de la frontera

(h, estado_actual) = heapq.heappop(frontera)

if estado_actual == estado_objetivo:

# devolver la ruta si se alcanza el estado objetivo

vía de retorno

explorado.add(estado_actual)

# generar posibles acciones a partir del estado actual

para acción en actions_func(current_state):

siguiente_estado = acción(estado_actual)

# calcular el costo de la nueva ruta

nuevo_costo = costo[estado_actual] + función_costo(estado_actual, acción, siguiente_estado)

si next_state no está explorado y next_state no está en [estado para (h, estado) en la frontera]:

# agregar el nuevo estado a la frontera

heapq.heappush(frontera, (función_heurística(siguiente_estado, estado_objetivo), siguiente_estado))

ruta[siguiente_estado] = estado_actual

costo[siguiente_estado] = nuevo_costo

# devuelve Ninguno si el estado objetivo no es alcanzable

volver Ninguno

Como puede ver, necesitará definir las siguientes funciones:

• heuristic_func(current_state, goal_state): esta función toma el estado actual y el estado objetivo como entradas y devuelve una estimación del costo de alcanzar el estado objetivo desde el estado actual.
• actions_func(current_state): esta función toma el estado actual como entrada y devuelve una lista de acciones que se pueden realizar desde el estado actual.
• cost_func(current_state, action, next_state): esta función toma el estado actual, una acción y el siguiente estado como entradas y devuelve el costo de realizar una acción desde el estado actual al siguiente estado.

Ejemplo de mejor primera búsqueda

estado_inicial = (0, 0)

estado_objetivo = (4, 4)

def heuristic_func(estado_actual, estado_objetivo):

return abs(estado_actual[0] – estado_objetivo[0]) + abs(estado_actual[1] – estado_objetivo[1])

def acciones_func(estado_actual):

acciones = []

si estado_actual[0] > 0:

acciones.append(estado lambda: (estado[0]-1, estado[1]))

si estado_actual[0] < 4:

acciones.append(estado lambda: (estado[0]+1, estado[1]))

si estado_actual[1] > 0:

acciones.append(estado lambda: (estado[0], estado[1]-1))

si estado_actual[1] < 4:

acciones.append(estado lambda: (estado[0], estado[1]+1))

acciones de retorno

def cost_func(estado_actual, acción, siguiente_estado):

volver 1

ruta = mejor_primera_búsqueda(estado_inicial, estado_objetivo, función_heurística, función_acciones, función_costo)

si camino:

# construir la ruta desde el estado inicial hasta el estado objetivo

estado_actual = estado_objetivo

while estado_actual != estado_inicio:

imprimir (estado_actual)

estado_actual = ruta[estado_actual]

imprimir (start_state)

demás:

print(“No se puede alcanzar el estado del objetivo.”)

Ventajas de la mejor primera búsqueda

• En comparación con la búsqueda primero en amplitud, la complejidad temporal de la búsqueda primero en el mejor es menor.
• La mejor primera búsqueda obtiene e implementa las ventajas de los algoritmos BFS y DFS

Desventajas de la mejor primera búsqueda

• En ocasiones puede cubrir más distancia de la considerada.
• Las posibilidades de quedar atrapado en un bucle son muy probables.

Una búsqueda

Una búsqueda* es un algoritmo de búsqueda que utiliza tanto el costo de llegar a un nodo desde el nodo inicial como una estimación del costo restante para llegar al nodo de destino para guiar su búsqueda. El algoritmo comienza en el nodo inicial y examina todos sus nodos secundarios, eligiendo al secundario con el costo combinado más bajo y el costo restante estimado como el siguiente nodo a explorar. Este proceso continúa hasta que se encuentra el nodo objetivo o se exploran todos los nodos.

Búsqueda A*: un ejemplo ilustrado

Volvamos a ver el ejemplo anterior de usted tratando de encontrar la ruta más corta desde su casa hasta una tienda de comestibles cercana. Ahora, podrías:

1. Comience en la ubicación de su casa y calcule el costo total para llegar a cada ubicación cercana como la suma de la distancia desde su casa hasta esa ubicación y el costo restante estimado para llegar a la tienda de comestibles desde esa ubicación.
2. Elija la ubicación cercana con el costo total más bajo como el siguiente nodo para explorar.
3. Desde esa ubicación cercana, calcule el costo total para cada una de sus ubicaciones secundarias como la suma de la distancia desde esa ubicación hasta la ubicación secundaria, el costo para llegar a esa ubicación desde el nodo de inicio y el costo restante estimado para llegar a la tienda de comestibles. desde esa ubicación infantil. Elija la ubicación secundaria con el costo total más bajo como el siguiente nodo para explorar.
4. Repita este proceso hasta llegar a la tienda de comestibles.

Una cosa importante a tener en cuenta aquí es que A* Search es un algoritmo de búsqueda óptimo que garantiza encontrar el camino más corto hacia el estado objetivo. Es eficiente en problemas con un gran espacio de búsqueda y se usa mucho en videojuegos, robótica y planificación de rutas. Sin embargo, requiere una función heurística bien definida para ser efectivo. Por esta razón, el algoritmo puede consumir mucha memoria y ralentizarse en problemas complejos con muchos nodos.

Búsqueda A*: implementación de Python

Así es como puede implementar el algoritmo de búsqueda A* utilizando la programación de Python:

montón de importaciónq

def astar_search(start_state, target_state, heuristic_func, actions_func, cost_func):

# inicializar la frontera y el conjunto explorado

frontera = [(función_heurística(estado_inicial, estado_objetivo), estado_inicial)]

explorado = establecer ()

# inicializar la ruta y el costo

camino = {}

costo = {}

ruta[start_state] = Ninguno

costo[start_state] = 0

mientras que la frontera:

# obtener el nodo con el valor f más bajo de la frontera

(f, estado_actual) = heapq.heappop(frontera)

if estado_actual == estado_objetivo:

# devolver la ruta si se alcanza el estado objetivo

vía de retorno

explorado.add(estado_actual)

# generar posibles acciones a partir del estado actual

para acción en actions_func(current_state):

siguiente_estado = acción(estado_actual)

# calcular el costo de la nueva ruta

nuevo_costo = costo[estado_actual] + función_costo(estado_actual, acción, siguiente_estado)

si next_state no está explorado y next_state no está en [estado para (f, estado) en la frontera]:

# agregar el nuevo estado a la frontera

heapq.heappush(frontera, (nuevo_costo + función_heurística(siguiente_estado, estado_objetivo), siguiente_estado))

ruta[siguiente_estado] = estado_actual

costo[siguiente_estado] = nuevo_costo

elif próximo_estado en [estado para (f, estado) en la frontera] y nuevo_costo <costo[próximo_estado]:

# actualizar el costo del estado existente en la frontera

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontera[índice] = (nuevo_costo + función_heurística(siguiente_estado, estado_objetivo), siguiente_estado)

ruta[siguiente_estado] = estado_actual

costo[siguiente_estado] = nuevo_costo

# devuelve Ninguno si el estado objetivo no es alcanzable

volver Ninguno

Los mejores cursos de aprendizaje automático y cursos de inteligencia artificial en línea

Ejemplo de búsqueda A*

Aquí hay un ejemplo de cómo podría usar la función astar_search con estas funciones:

estado_inicial = (0, 0)

estado_objetivo = (4, 4)

def heuristic_func(estado_actual, estado_objetivo):

return abs(estado_actual[0] – estado_objetivo[0]) + abs(estado_actual[1] – estado_objetivo[1])

def acciones_func(estado_actual):

acciones = []

si estado_actual[0] > 0:

acciones.append(estado lambda: (estado[0]-1, estado[1]))

si estado_actual[0] < 4:

acciones.append(estado lambda: (estado[0]+1, estado[1]))

si estado_actual[1] > 0:

acciones.append(estado lambda: (estado[0], estado[1]-1))

si estado_actual[1] < 4:

acciones.append(estado lambda: (estado[0], estado[1]+1))

acciones de retorno

def cost_func(estado_actual, acción, siguiente_estado):

volver 1

ruta = búsqueda_astar(estado_inicial, estado_objetivo, función_heurística, función_acciones, función_coste)

si camino:

# construir la ruta desde el estado inicial hasta el estado objetivo

estado_actual = estado_objetivo

while estado_actual != estado_inicio:

imprimir (estado_actual)

estado_actual = ruta[estado_actual]

imprimir (start_state)

demás:

print(“No se puede alcanzar el estado del objetivo.”)

Ventajas de la búsqueda A*

• Es una de las principales técnicas heurísticas.
• La búsqueda A* se puede aprovechar para resolver problemas de búsqueda complejos

Habilidades de aprendizaje automático de tendencia

Desventajas de la búsqueda A*

• El rendimiento de búsqueda A* depende en gran medida de la precisión de los algoritmos heurísticos.
• Tiene baja eficiencia de búsqueda.

Blogs populares de IA y ML y cursos gratuitos

Llevar

Los algoritmos de búsqueda informados son esenciales en la inteligencia artificial, ya que permiten que la computadora busque un estado objetivo de manera eficiente y efectiva. Estos algoritmos usan funciones heurísticas para estimar el costo de cada movimiento posible y guiar el proceso de búsqueda hacia el estado objetivo. Best First Search y A* Search son ejemplos de algoritmos de búsqueda informados ampliamente utilizados en varios campos. Sin embargo, una función heurística bien definida es fundamental para el éxito de los algoritmos de búsqueda informados.

Si está interesado en obtener más información sobre inteligencia artificial y aprendizaje automático, consulte el programa de Maestría en Aprendizaje Automático e Inteligencia Artificial de upGrad ofrecido por la Universidad John Moores de Liverpool . Este programa cubre varios temas de inteligencia artificial y aprendizaje automático, incluidos algoritmos como la búsqueda informada. Al tomar este programa, puede obtener las habilidades y el conocimiento que necesita para tener éxito en una variedad de carreras relacionadas con la IA.

También puede consultar nuestroscursos gratuitosofrecidos por upGrad en administración, ciencia de datos, aprendizaje automático, marketing digital y tecnología.Todos estos cursos tienen recursos de aprendizaje de primer nivel, conferencias semanales en vivo, asignaciones de la industria y un certificado de finalización del curso, ¡todo sin costo!