Algoritmo IDA* y su Relación con el Algoritmo Primero en Profundidad con Longitud Limitada
- Algoritmo Primero en Profundidad con Longitud Limitada (DFS-Limited)
- Algoritmo IDA*
- Ejemplo en TypeScript
- Conclusión
Algoritmo Primero en Profundidad con Longitud Limitada (DFS-Limited)
Antes de entender el algoritmo IDA*, es importante comprender el algoritmo de búsqueda primero en profundidad con longitud limitada (DFS-Limited).
Conceptos Básicos de DFS-Limited
- Búsqueda Primero en Profundidad (DFS): Es un algoritmo de búsqueda que explora cada rama del árbol de manera exhaustiva antes de retroceder.
- Longitud Limitada: En DFS-Limited, se impone un límite de profundidad, lo que evita que el algoritmo se quede atrapado en bucles infinitos en grafos cíclicos.
Pseudocódigo de DFS-Limited
function DFS_Limited(node, goal, limit) {
if (node == goal) {
return true;
} else if (limit == 0) {
return false;
} else {
for (let child of node.children) {
if (DFS_Limited(child, goal, limit - 1)) {
return true;
}
}
}
return false;
}Algoritmo IDA*
El algoritmo IDA* mejora el algoritmo DFS-Limited incorporando una heurística para guiar la búsqueda hacia la meta de manera más eficiente. La heurística debe ser una función de estimación del costo restante para alcanzar el objetivo.
Conceptos Básicos de IDA*
- Costo Total (f(n)): Suma del costo acumulado para llegar al nodo (g(n)) y el costo estimado restante (h(n)).
- Límite Iterativo: IDA* realiza iteraciones de DFS-Limited con límites de costo incrementales.
Pseudocódigo de IDA*
function IDA_Star(root, goal, heuristic) {
let threshold = heuristic(root);
while (true) {
const temp = DFS_Limited(root, goal, 0, threshold, heuristic);
if (temp === true) {
return true; // Goal found
}
if (temp === Infinity) {
return false; // Goal not found and no more nodes to explore
}
threshold = temp;
}
}
function DFS_Limited(node, goal, g, threshold, heuristic) {
const f = g + heuristic(node);
if (f > threshold) {
return f;
}
if (node == goal) {
return true;
}
let min = Infinity;
for (let child of node.children) {
const temp = DFS_Limited(child, goal, g + cost(node, child), threshold, heuristic);
if (temp === true) {
return true; // Goal found
}
if (temp < min) {
min = temp;
}
}
return min;
}Ejemplo en TypeScript
Consideremos un problema de búsqueda en un grafo donde queremos encontrar el camino más corto desde el nodo de inicio hasta el nodo objetivo. Usaremos una heurística simple como la distancia en línea recta al objetivo.
type Node = {
id: string;
children: Node[];
cost: number;
};
function heuristic(node: Node, goal: Node): number {
// Implementar una función heurística apropiada
// Por ejemplo, la distancia en línea recta si es aplicable
return Math.abs(node.id.charCodeAt(0) - goal.id.charCodeAt(0));
}
function cost(node: Node, child: Node): number {
// Implementar el costo real para moverse de un nodo a otro
return child.cost;
}
function IDA_Star(root: Node, goal: Node): boolean {
let threshold = heuristic(root, goal);
while (true) {
const temp = DFS_Limited(root, goal, 0, threshold, heuristic);
if (temp === true) {
return true; // Objetivo encontrado
}
if (temp === Infinity) {
return false; // Objetivo no encontrado y no hay más nodos por explorar
}
threshold = temp;
}
}
function DFS_Limited(node: Node, goal: Node, g: number, threshold: number, heuristic: (n: Node, g: Node) => number): number | boolean {
const f = g + heuristic(node, goal);
if (f > threshold) {
return f;
}
if (node.id === goal.id) {
return true;
}
let min = Infinity;
for (let child of node.children) {
const temp = DFS_Limited(child, goal, g + cost(node, child), threshold, heuristic);
if (temp === true) {
return true; // Objetivo encontrado
}
if (typeof temp === "number" && temp < min) {
min = temp;
}
}
return min;
}
// Ejemplo de uso
const startNode: Node = { id: 'A', children: [], cost: 0 };
const goalNode: Node = { id: 'G', children: [], cost: 0 };
// Agregar nodos y relaciones (grafo)...
const found = IDA_Star(startNode, goalNode);
console.log(found ? "Objetivo encontrado" : "Objetivo no encontrado");Conclusión
El algoritmo IDA* es una técnica poderosa para la búsqueda en grafos que combina la eficiencia de la búsqueda primero en profundidad con la guía de una heurística informada, permitiendo una exploración más eficiente del espacio de estados en comparación con DFS-Limited. Este enfoque es especialmente útil en escenarios donde la memoria es una limitación importante.
Jorge García
Fullstack developer