Algoritmos de Búsqueda en Inteligencia Artificial: Implementaciones en Java
Clasificado en Informática
Escrito el en 
español con un tamaño de 6,37 KB
Algoritmos de Búsqueda en Inteligencia Artificial: Implementaciones en Java
Este documento presenta implementaciones en Java de tres algoritmos fundamentales de búsqueda en inteligencia artificial: búsqueda en anchura, búsqueda en profundidad y búsqueda en profundidad iterativa. Además, se incluye una función para el control de estados repetidos en búsquedas con heurísticas.
Búsqueda en Anchura
La búsqueda en anchura explora el espacio de estados de forma sistemática, visitando primero todos los nodos a una profundidad dada antes de pasar a la siguiente. Esto garantiza que se encuentre la solución más cercana al nodo inicial, si existe.
private static Estado busquedaAnchura(Estado inicial) { HashSet<Estado> repetidos = new HashSet<>(); LinkedList<Estado> abiertos = new LinkedList<>(); abiertos.add(inicial); while (!abiertos.isEmpty()) { Estado estado = abiertos.removeFirst(); nodosExplorados++; if (estado.esObjetivo()) return estado; for (Operador o : operadores) { // Esta es la parte compleja Estado sucesor = o.run(estado); if (sucesor != null && repetidos.add(sucesor)) { abiertos.add(sucesor); } } return null; // throw new UnsupportedOperationException("Falta implementar");}Búsqueda en Profundidad
La búsqueda en profundidad explora el espacio de estados siguiendo una rama hasta el final antes de retroceder y explorar otras ramas. Es más eficiente en términos de memoria que la búsqueda en anchura, pero no garantiza encontrar la solución más cercana.
private static Estado busquedaProfundidad(Estado inicial, int limite) { XHashSet<Estado> repetidos = new XHashSet<>(); LinkedList<Estado> abiertos = new LinkedList<>(); abiertos.add(inicial); while (!abiertos.isEmpty()) { Estado estado = abiertos.removeFirst(); nodosExplorados++; if (estado.esObjetivo()) return estado; if (estado.getProfundidad() < limite) { for (Operador o : operadores) { Estado sucesor = o.run(estado); if (sucesor != null) { Estado r = repetidos.get(sucesor); if (r == null || r.getProfundidad() > sucesor.getProfundidad()) { if (r != null) { repetidos.remove(r); } abiertos.push(sucesor); repetidos.add(sucesor); } } } } } return null;}Búsqueda en Profundidad Iterativa
La búsqueda en profundidad iterativa combina las ventajas de la búsqueda en anchura y en profundidad. Realiza búsquedas en profundidad sucesivas con un límite de profundidad creciente, lo que le permite encontrar la solución más cercana con una eficiencia de memoria similar a la búsqueda en profundidad.
private static Estado busquedaProfundidadIterativa(Estado inicial, int limite) { for (int p = 0; p <= limite; p++) { Estado e = busquedaProfundidad(inicial, p); if (e != null) return e; } return null;}Control de Estados Repetidos con Heurísticas
Esta función se utiliza para controlar los estados repetidos en algoritmos de búsqueda que utilizan heurísticas. Permite actualizar la lista de nodos abiertos y repetidos en función del valor de la heurística, mejorando la eficiencia de la búsqueda.
private static void controlarRepetidos(XPriorityQueue<Estado> abiertos, XHashSet<Estado> repetidos, Heuristica f, Estado sucesor) { if (abiertos.contains(sucesor) && repetidos.get(sucesor) == null) { Estado p = abiertos.get(sucesor); if (f.compare(sucesor, p) < 0) { abiertos.remove(p); abiertos.add(sucesor); } } else if (repetidos.get(sucesor) != null) { Estado c = repetidos.get(sucesor); if (f.compare(sucesor, c) < 0) { repetidos.remove(c); abiertos.add(sucesor); } else { repetidos.remove(c); abiertos.add(c); } } else { abiertos.add(sucesor); }}