Búsqueda informada
Los algoritmos de búsqueda no informada son susceptibles a explorar múltiples caminos que no
conducen a una solución, antes de hallar un estado objetivo en el espacio de estados.
Esto aumenta de forma significativa la complejidad en operaciones del método (por
ende, el tiempo de ejecución).
En problemas de búsqueda, la estrategia debe pasar por la reducción del número de caminos
alternativos por evaluar
Restringir la expansión de vértices del árbol de búsqueda sobre el grafo que representa
el problema.
Diferencias entre búsqueda informada y no informada:
Búsqueda no informada: Se parte de la definición del problema (de búsqueda) para usar una
estrategia que permita llegar a la solución de la forma más eficiente posible a partir del estado
inicial usando solo la exploración mediante la expansión de los nodos.
Búsqueda informada: Además de la definición del problema, se usa conocimiento previo sobre la
naturaleza de la solución.
Franco, I. A. P. (s/f). Búsqueda informada. [Link]. Recuperado el 28 de mayo de
2024, de
[Link]
[Link]
Búsqueda en profundidad
La búsqueda en profundidad (DFS) es un algoritmo de búsqueda que atraviesa los nodos de
un gráfico. Su funcionamiento consiste en expandir recursivamente (de padre a hijo) cada
nodo encontrado. Cuando no hay más nodos disponibles en esta ruta, regresa al nodo anterior
para repetir el mismo proceso con cada uno de los vecinos de ese nodo.
Teniendo en cuenta que, si se encuentra un nodo antes de atravesar todos los nodos, la búsqueda
finaliza. La búsqueda en profundidad se puede utilizar cuando queremos comprobar si
una de varias soluciones posibles cumple ciertos requisitos, ejemplo: el camino que debe tomar un
caballo en un tablero de ajedrez para cruzar las 64 casillas del tablero.
Aplicaciones de Búsqueda en Profundidad:
Encontrar nodos conectados en un grafo
Ordenamiento topológico en un grafo acíclico dirigido
Encontrar puentes en un grafo de nodos
Resolver puzzles con una sola solución, como los laberintos
Encontrar nodos fuertemente conectados
Murillo, J. (2020, mayo 25). Difference between breadth search (BFS) and Deep
Search (DFS). Encora. [Link]
Búsqueda en amplitud
La búsqueda en amplitud (BFS) es un algoritmo de búsqueda que atraviesa los nodos de un gráfico,
comenzando desde la raíz (en el caso de un gráfico, seleccionando el nodo como elemento raíz) y
luego explora todos los nodos adyacentes del gráfico., para cada vecino, explore los vecinos
adyacentes correspondientes, y así sucesivamente, hasta recorrer todo el gráfico. Tenga en cuenta
que, si se encuentra un nodo antes de atravesar todos los nodos, la búsqueda finaliza.
La búsqueda de amplitud se utiliza para algoritmos en los que es fundamental elegir la mejor ruta
posible en cada momento del viaje.
Aplicaciones de Búsqueda en Amplitud:
Encontrar el camino más corto entre 2 nodos, medido por el número de nodos conectados
Probar si un grafo de nodos es bipartito (si se puede dividir en 2 conjuntos)
Encontrar el árbol de expansión mínima en un grafo no ponderado
Hacer un Web Crawler
Sistemas de navegación GPS, para encontrar localizaciones vecinas
Murillo, J. (2020, mayo 25). Difference between breadth search (BFS) and Deep
Search (DFS). Encora. [Link]
