Descripción técnica
Dijkstra, A * y la búsqueda de amplitud requieren que la frontera de búsqueda se almacene en la memoria. Para gráficos grandes, esto no es factible. Además, nos gustaría hacer un seguimiento de los nodos ya atravesados y sus distancias desde el nodo de inicio para asegurarnos de que no estamos haciendo un trabajo adicional, que también requiere un montón de memoria.
IDA * intenta reducir la huella de memoria de A * mientras conserva su naturaleza de búsqueda informada. Esto se logra al realizar recorridos iterativos de profundidad primero del espacio de búsqueda: durante cada recorrido, se establece un límite de distancia: solo atravesamos nodos cuya suma de la distancia hasta el momento y la distancia estimada al objetivo no excede el límite. Este límite se establece inicialmente en h (inicio), o la distancia estimada desde el inicio hasta el objetivo. Si el recorrido posterior no logra encontrar el estado del objetivo, aumentamos el límite de distancia y repetimos el recorrido. Esto reduce la huella de memoria a O (número máximo de nodos en una ruta de distancia <= ruta más corta), a costa de atravesar un grupo de nodos varias veces.
- ¿Cómo se pueden usar los bucles para procesar matrices?
- ¿Cuál es la mejor estrategia para obtener una solución óptima para cualquier problema de codificación solicitado en la entrevista de codificación?
- ¿Cuál es la diferencia entre usar <y <= en la búsqueda binaria?
- ¿Cómo puedo usar el algoritmo de Baum-Welch para agregar observaciones perdidas?
- ¿Cuáles son las buenas implementaciones de búfer circular sin bloqueo en Java?
Ejemplo intuitivo
Aprovecharé la excelente respuesta de Igor a ¿Qué es una explicación intuitiva de la búsqueda A *? En ese escenario, asumimos que la persona tiene una memoria perfecta. En cambio, imagine que la persona tiene muy poca memoria, aunque todavía no quiere tropezar ciegamente por la ciudad en busca de su destino. Entonces se le ocurre el siguiente plan:
Día 1: Creo que la distancia entre mi punto de partida y mi destino es de 1 km. Visitaré todos los lugares para los que la longitud del camino hasta ahora más la distancia estimada al destino no sea más de 1 km. Si no encuentro mi edificio, volveré al punto de inicio y dormiré.
Día 2: OK, todavía no he encontrado mi destino. Sin embargo, cuando visité el Edificio D, noté que había viajado 900 my estaba a solo unos 200 m del destino. Ajustaré mi estimación de la distancia total a 1.1 km e intentaré nuevamente.
Día 3: etc.
