Algoritmo A*
El algoritmo A* es un algoritmo de búsqueda en grafos utilizado para encontrar la ruta más corta
entre dos nodos.
Utiliza una combinación de las siguientes funciones:
- g(n): el coste del camino desde el nodo inicial hasta el nodo n.
- h(n): una heurística que estima el coste desde n hasta el nodo objetivo.
El objetivo es minimizar la función f(n) = g(n) + h(n).
Pseudocódigo del Algoritmo A*
function A*(start, goal)
crear un conjunto abierto (openSet)
crear un conjunto cerrado (closedSet)
añadir start a openSet
while openSet no está vacío:
nodo actual = nodo en openSet con el valor f más bajo
if actual es el nodo objetivo:
return reconstruir_camino(actual)
mover actual de openSet a closedSet
para cada vecino de actual:
if vecino está en closedSet:
continue
costeTentativo = g(actual) + coste(entre actual y vecino)
if vecino no está en openSet:
añadir vecino a openSet
else if costeTentativo >= g(vecino):
continue
[Link] = actual
g(vecino) = costeTentativo
f(vecino) = g(vecino) + h(vecino)
return fallo
Código del Algoritmo A* en Java
import [Link].*;
class Node {
public String name;
public List<Edge> adjacenciesList;
public Node parent;
public double gCost;
public double hCost;
public double fCost;
public Node(String name, double hCost) {
[Link] = name;
[Link] = hCost;
[Link] = new ArrayList<>();
public void addNeighbor(Node targetNode, double weight) {
[Link](new Edge(targetNode, weight));
@Override
public String toString() {
return [Link];
class Edge {
public Node targetNode;
public double weight;
public Edge(Node targetNode, double weight) {
[Link] = targetNode;
[Link] = weight;
class AStar {
public void aStarSearch(Node startNode, Node goalNode) {
PriorityQueue<Node> openSet = new PriorityQueue<>([Link](n ->
[Link]));
Set<Node> closedSet = new HashSet<>();
[Link] = 0;
[Link] = [Link] + [Link];
[Link](startNode);
while (![Link]()) {
Node currentNode = [Link]();
if ([Link](goalNode)) {
reconstructPath(currentNode);
return;
[Link](currentNode);
for (Edge edge : [Link]) {
Node neighbor = [Link];
if ([Link](neighbor)) continue;
double tentativeGCost = [Link] + [Link];
if ( || tentativeGCost < [Link]) {
[Link] = currentNode;
[Link] = tentativeGCost;
[Link] = [Link] + [Link];
if () {
[Link](neighbor);
[Link]("No se encontró un camino.");
private void reconstructPath(Node currentNode) {
List<Node> path = new ArrayList<>();
while (currentNode != null) {
[Link](currentNode);
currentNode = [Link];
[Link](path);
[Link]("Camino encontrado: " + path);
}
public class AStarExample {
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Ingrese la cantidad de nodos:");
int numNodos = [Link]();
Node[] nodes = new Node[numNodos];
for (int i = 0; i < numNodos; i++) {
[Link]("Ingrese el nombre del nodo " + (i + 1) + " y su valor heurístico:");
String name = [Link]();
double heuristic = [Link]();
nodes[i] = new Node(name, heuristic);
[Link]("Ingrese la cantidad de aristas:");
int numAristas = [Link]();
for (int i = 0; i < numAristas; i++) {
[Link]("Ingrese los nombres de los nodos conectados y el peso de la arista:");
String from = [Link]();
String to = [Link]();
double weight = [Link]();
Node fromNode = findNodeByName(nodes, from);
Node toNode = findNodeByName(nodes, to);
if (fromNode != null && toNode != null) {
[Link](toNode, weight);
} else {
[Link]("Error: Nodos no válidos.");
[Link]("Ingrese el nodo inicial:");
String startName = [Link]();
[Link]("Ingrese el nodo final:");
String goalName = [Link]();
Node startNode = findNodeByName(nodes, startName);
Node goalNode = findNodeByName(nodes, goalName);
if (startNode != null && goalNode != null) {
AStar aStar = new AStar();
[Link](startNode, goalNode);
} else {
[Link]("Error: Nodos inicial o final no válidos.");
[Link]();
private static Node findNodeByName(Node[] nodes, String name) {
for (Node node : nodes) {
if ([Link](name)) {
return node;
return null;