Laberinto de búsqueda primero en amplitud en C++

1. Algoritmo de búsqueda primero en amplitud
2. Pasos para hacer un laberinto de búsqueda primero en anchura en C++

Una búsqueda primero en amplitud es un algoritmo para atravesar o buscar estructuras de datos de árboles o gráficos. En cada nodo, el algoritmo visita a los hijos antes de visitar al padre.

En otras palabras, se expande hacia afuera desde su posición actual en cada nivel del árbol en lugar de moverse hacia arriba al padre y hacia abajo a sus hijos.

La búsqueda primero en amplitud se utiliza para encontrar los caminos más cortos en los gráficos. Se ha utilizado para encontrar soluciones en muchos campos, como la inteligencia artificial, la informática, las matemáticas y las ciencias sociales.

Algoritmo de búsqueda primero en amplitud

La búsqueda primero en anchura es un algoritmo de búsqueda que atraviesa el árbol en sentido ancho, expandiendo los nodos de una manera primero en anchura.

El algoritmo comienza en un nodo arbitrario y expande todos sus hijos. Luego, procede a hacer lo mismo para cada uno de sus hijos, y así sucesivamente.

El proceso termina cuando llega a un nodo hoja o encuentra un estado objetivo.

Para encontrar el camino más corto de un nodo a otro, necesitamos saber su distancia desde ese nodo. Esto se puede calcular sumando las longitudes de los bordes entre dos nodos en el gráfico.

Pasos para hacer un laberinto de búsqueda primero en anchura en C++

Los pasos para hacer el laberinto de búsqueda primero en anchura en C++ son los siguientes:

Cuando la cola deja de estar vacía, tomamos un elemento de ella y recursivamente llamamos al algoritmo de búsqueda en amplitud hasta llegar a un nodo inexplorado.

Por último, cuando la cola se vacía, llegamos a un extremo del laberinto y dejamos de buscar nodos inexplorados en esa dirección.

Ejemplo del laberinto de búsqueda primero en anchura en C++

Este es un ejemplo de un laberinto de búsqueda en amplitud en C++. El código implementa el algoritmo para encontrar la ruta más corta desde un nodo de inicio dado a todos los demás nodos en un gráfico.

#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point {
  int a;
  int b;
};
struct queueNode {
  Point de;
  int sam;
};
bool isValid(int hori, int vert) {
  return (hori >= 0) && (hori < HORI) && (vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello) {
  if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b]) return -1;
  bool visited[HORI][VERT];
  memset(visited, false, sizeof visited);
  visited[ace.a][ace.b] = true;
  queue<queueNode> e;
  queueNode s = {ace, 0};
  e.push(s);
  while (!e.empty()) {
    queueNode curr = e.front();
    Point de = curr.de;
    if (de.a == hello.a && de.b == hello.b) return curr.sam;
    e.pop();
    for (int i = 0; i < 4; i++) {
      int hori = de.a + horiNum[i];
      int vert = de.b + vertNum[i];
      if (isValid(hori, vert) && lk[hori][vert] && !visited[hori][vert]) {
        visited[hori][vert] = true;
        queueNode Adjcell = {{hori, vert}, curr.sam + 1};
        e.push(Adjcell);
      }
    }
  }
  return -1;
}
int main() {
  int lk[HORI][VERT] = {{3, 9, 2}, {4, 5, 3}, {0, 3, 0}};
  Point source = {0, 0};
  Point hello = {1, 1};
  int sam = BFS(lk, source, hello);
  if (sam != 1)
    cout << "Shortest Path:" << sam;
  else
    cout << "Failed!!!";
  return 0;
}

Haga clic aquí para verificar el funcionamiento del código como se mencionó anteriormente.