Skip to content

A* ​

aStar(graph, start, end, heuristic) busca una ruta más corta usando un valor heurístico i32 por vértice. Una heurística admisible conserva la optimalidad.

FirmaDevuelveComplejidad
aStar(adj: [usize, i32][][], start: usize, end: usize, heuristic: i32[])[usize[], i32]?O((V + E) log V)
tyrus
import { aStar } from "tyrus:algorithm";

const result: [usize[], i32]? = aStar([[[1, 4], [2, 2]], [[3, 5]], [[3, 1]], []], 0, 3, [3, 1, 1, 0]);
if (result) { print(result[1]); } // 3

Resultado de estudio ​

aStarInfo expone distancias, predecesores, relajaciones, evaluaciones de la heurística, vértices abiertos y cerrados y el costo final cuando se alcanza el destino.

tyrus
interface AStarInfo {
    distances: i32[];
    predecessors: usize?[];
    relaxationCount: usize;
    processedVertexCount: usize;
    examinedEdgeCount: usize;
    heuristicEvaluationCount: usize;
    openedVertexCount: usize;
    closedVertexCount: usize;
    finalCost: i32?;
}
tyrus
import { AStarInfo, ShortestPathInfo, aStarInfo } from "tyrus:algorithm";

const info: AStarInfo = aStarInfo([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []], 0, 3, [3, 1, 2, 0]);
print(info.distances); // [0, 3, 1, 4]
print(info.predecessors[3] ?? 99); // 1
print(info.relaxationCount); // 5
print(info.processedVertexCount); // 4
print(info.examinedEdgeCount); // 5
print(info.heuristicEvaluationCount); // 6
print(info.openedVertexCount); // 4
print(info.closedVertexCount); // 4
print(info.finalCost ?? -1); // 4