En este documento, exploraremos cómo integrar varias técnicas de búsqueda de caminos. Las técnicas que abordaremos incluyen:
- Búsqueda en amplitud (BFS)
- Búsqueda en profundidad (DFS)
- Búsqueda de menor costo (Dijkstra)
- Búsqueda A* (A Star)
1. Búsqueda en Amplitud (BFS)
La búsqueda en amplitud explora todos los nodos a una distancia dada antes de avanzar a la siguiente. Es útil para encontrar el camino más corto en un grafo no ponderado.
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>
using namespace std;
struct Node {
int id;
vector<int> neighbors;
};
void bfs(vector<Node>& graph, int start) {
queue<int> q;
unordered_set<int> visited;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << "Visitando nodo: " << node << endl;
for (int neighbor : graph[node].neighbors) {
if (visited.find(neighbor) == visited.end()) {
q.push(neighbor);
visited.insert(neighbor);
}
}
}
}
int main() {
// Crear un grafo ejemplo
vector<Node> graph(5);
graph[0].neighbors = {1, 2};
graph[1].neighbors = {0, 3, 4};
graph[2].neighbors = {0};
graph[3].neighbors = {1};
graph[4].neighbors = {1};
bfs(graph, 0);
return 0;
}
2. Búsqueda en Profundidad (DFS)
La búsqueda en profundidad explora tan lejos como sea posible a lo largo de cada rama antes de retroceder. Es adecuada para encontrar componentes conexos y ciclos en un grafo.
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
struct Node {
int id;
vector<int> neighbors;
};
void dfs(vector<Node>& graph, int node, unordered_set<int>& visited) {
if (visited.find(node) != visited.end()) return;
cout << "Visitando nodo: " << node << endl;
visited.insert(node);
for (int neighbor : graph[node].neighbors) {
dfs(graph, neighbor, visited);
}
}
int main() {
// Crear un grafo ejemplo
vector<Node> graph(5);
graph[0].neighbors = {1, 2};
graph[1].neighbors = {0, 3, 4};
graph[2].neighbors = {0};
graph[3].neighbors = {1};
graph[4].neighbors = {1};
unordered_set<int> visited;
dfs(graph, 0, visited);
return 0;
}
3. Búsqueda de Menor Costo (Dijkstra)
Dijkstra es un algoritmo eficiente para encontrar el camino más corto desde un nodo de origen a todos los demás nodos en un grafo ponderado.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <limits>
using namespace std;
struct Edge {
int target;
int weight;
};
using Graph = vector<vector<Edge>>;
vector<int> dijkstra(const Graph& graph, int start) {
int n = graph.size();
vector<int> dist(n, numeric_limits<int>::max());
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int d, node;
tie(d, node) = pq.top();
pq.pop();
if (d > dist[node]) continue;
for (const auto& edge : graph[node]) {
int next_dist = d + edge.weight;
if (next_dist < dist[edge.target]) {
dist[edge.target] = next_dist;
pq.push({next_dist, edge.target});
}
}
}
return dist;
}
int main() {
Graph graph(5);
graph[0].push_back({1, 1});
graph[0].push_back({2, 4});
graph[1].push_back({2, 2});
graph[1].push_back({3, 5});
graph[2].push_back({3, 1});
graph[3].push_back({4, 3});
vector<int> distances = dijkstra(graph, 0);
for (int i = 0; i < distances.size(); ++i) {
cout << "Distancia desde el nodo 0 al nodo " << i << " es " << distances[i] << endl;
}
return 0;
}
4. Búsqueda A* (A Star)
A* combina la búsqueda en amplitud y la heurística para encontrar el camino más corto de manera eficiente.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
#include <unordered_map>
using namespace std;
struct Edge {
int target;
int weight;
};
using Graph = vector<vector<Edge>>;
struct Node {
int id;
int g_cost; // Costo desde el nodo de inicio
int h_cost; // Costo heurístico al nodo final
int f_cost() const { return g_cost + h_cost; }
bool operator>(const Node& other) const { return f_cost() > other.f_cost(); }
};
vector<int> a_star(const Graph& graph, int start, int goal, const vector<int>& heuristic) {
int n = graph.size();
priority_queue<Node, vector<Node>, greater<>> pq;
unordered_map<int, int> came_from;
vector<int> g_cost(n, numeric_limits<int>::max());
pq.push({start, 0, heuristic[start]});
g_cost[start] = 0;
while (!pq.empty()) {
int current = pq.top().id;
pq.pop();
if (current == goal) break;
for (const auto& edge : graph[current]) {
int next = edge.target;
int new_g_cost = g_cost[current] + edge.weight;
if (new_g_cost < g_cost[next]) {
g_cost[next] = new_g_cost;
pq.push({next, new_g_cost, new_g_cost + heuristic[next]});
came_from[next] = current;
}
}
}
vector<int> path;
for (int at = goal; at != start; at = came_from[at]) {
path.push_back(at);
}
path.push_back(start);
reverse(path.begin(), path.end());
return path;
}
int main() {
Graph graph(5);
graph[0].push_back({1, 1});
graph[0].push_back({2, 4});
graph[1].push_back({2, 2});
graph[1].push_back({3, 5});
graph[2].push_back({3, 1});
graph[3].push_back({4, 3});
vector<int> heuristic = {7, 6, 2, 1, 0}; // Heurísticas estimadas hacia el nodo objetivo
vector<int> path = a_star(graph, 0, 4, heuristic);
cout << "Camino encontrado por A*: ";
for (int node : path) {
cout << node << " ";
}
cout << endl;
return 0;
}
Conclusión
Hemos cubierto las técnicas básicas de búsqueda de caminos en grafos: BFS, DFS, Dijkstra y A*. Cada técnica tiene sus propias ventajas y casos de uso específicos. La implementación en C++ muestra cómo se pueden integrar estas técnicas para resolver problemas de búsqueda de caminos de manera eficiente.
Espero que este documento te sea útil para entender y aplicar estas técnicas en tus proyectos.
