Comparando ILBFS y RBFS en Algoritmos de Búsqueda

Los algoritmos de búsqueda son métodos utilizados para encontrar soluciones a problemas, a menudo representados como Caminos a través de un espacio de posibles estados. Entre los muchos algoritmos de búsqueda, hay dos tipos destacados: la Búsqueda Recursiva de Mejor Primero (RBFS) y la Búsqueda Iterativa de Mejor Primero Lineal (ILBFS). Ambos algoritmos buscan ser eficientes en términos de uso de memoria, lo cual es importante, especialmente cuando se trata de problemas grandes.

#Entendiendo RBFS

RBFS es un tipo de algoritmo de búsqueda heurística. Esto significa que utiliza una estrategia para priorizar ciertos caminos basándose en una estimación de su potencial efectividad. RBFS está diseñado para usar menos memoria en comparación con métodos tradicionales, como el algoritmo A*, que suele ser más pesado y requiere más recursos.

La estructura de RBFS le permite almacenar solo los mejores caminos posibles de forma compacta. Lo hace bajando por un camino hasta llegar a un punto final, luego puede retroceder y explorar otros caminos sin mantener toda la información en memoria a la vez. Aunque este método tiene ventajas, puede ser complejo y difícil de aprender o implementar para muchas personas, lo que ha limitado su uso.

#ILBFS como Solución

Para facilitar las cosas, se desarrolló ILBFS como una alternativa más simple y amigable para el usuario a RBFS. Siendo igual de eficiente en cuanto a memoria que RBFS, ILBFS intenta hacer que el algoritmo sea más fácil de enseñar y entender. Logra esto utilizando mecanismos específicos para gestionar la memoria, lo que ayuda a evitar algunas de las complejidades vistas en RBFS.

ILBFS funciona eliminando temporalmente partes innecesarias del espacio de búsqueda de la memoria y luego restaurándolas cuando se necesitan de nuevo. Esto ayuda a mantener bajo el uso de memoria mientras hace el algoritmo más intuitivo de seguir.

#Características Clave de ILBFS

En nuestro trabajo, nos enfocamos en implementar ILBFS y validar sus afirmaciones sobre el uso de memoria y cómo expande Nodos en comparación con RBFS. Hay varias características importantes de ILBFS que ayudan a que funcione de manera efectiva. Estas incluyen la gestión de empates entre caminos y la manera en que se eliminan nodos de la lista de búsqueda.

#Importancia de Gestionar Empates

En los algoritmos de búsqueda, manejar empates es crucial. Un empate ocurre cuando dos o más caminos tienen el mismo puntaje estimado. En ILBFS, el método utilizado para resolver estos empates puede afectar la eficiencia de la búsqueda. Una buena estrategia para romper empates evita que el algoritmo se quede atascado en bucles donde cambia continuamente entre dos caminos sin avanzar.

Para abordar esto, usamos una estrategia que permite al algoritmo favorecer el camino que llegó primero cuando los puntajes están empatados. Esto ayuda a evitar movimientos innecesarios entre caminos y asegura que el algoritmo pueda avanzar sin problemas.

#Gestión de la Eliminación de Nodos de la Lista Abierta

ILBFS requiere un manejo cuidadoso de los nodos que se están considerando para expansión. Cuando se eliminan nodos de la lista de caminos seguidos, debe hacerse de una manera que mantenga la lista organizada y eficiente. Esto es diferente de RBFS, que gestiona naturalmente los nodos a través de un método recursivo.

Para ILBFS, tenemos dos métodos para gestionar la eliminación de nodos: el método de heapificación y el método de bajar.

#Método de Heapificación

El método de heapificación implica simplemente eliminar elementos de la lista abierta cuando se colapsa un subárbol. Después de las eliminaciones, reorganizamos la lista para mantener su estructura. Aunque esto es fácil de configurar, puede ser lento para listas más grandes, ya que necesita reordenar todo cada vez que se eliminan nodos.

#Método de Bajar

El método de bajar es un enfoque más eficiente. Reemplaza el nodo eliminado con el último elemento de la lista y luego organiza solo esa parte de la lista en lugar de toda. Este método suele ser más rápido porque solo aborda la ruta específica que se vio afectada por la eliminación.

Ambos métodos tienen sus fortalezas y debilidades, pero el método de bajar es generalmente preferido para conjuntos de datos más grandes, ya que requiere menos ajustes generales para mantener la lista precisa.

#Resultados y Rendimiento

En nuestro análisis, observamos qué tan bien funcionan los algoritmos RBFS e ILBFS al resolver un problema designado, específicamente el rompecabezas de 8 fichas. Este rompecabezas es un problema clásico en el que debes organizar fichas en un orden específico deslizándolas.

Creamos varios ejemplos diferentes del rompecabezas, variando en dificultad. Al ejecutar tanto RBFS como ILBFS en estos rompecabezas, recopilamos datos sobre cuánto tiempo tomó cada algoritmo encontrar una solución y cuánto usarón de memoria.

#Observaciones de Tiempo de Ejecución

Los resultados mostraron que ILBFS tomó más tiempo que RBFS para ejecutarse, principalmente debido al trabajo extra necesario para gestionar la lista de caminos. Sin embargo, la diferencia en el tiempo que tomaron los métodos de ILBFS no fue tan grande como se podría esperar, especialmente entre los dos métodos para manejar eliminaciones.

#Comparación de Uso de Memoria

Ambos algoritmos demostraron la capacidad de resolver el rompecabezas utilizando memoria lineal, lo que significa que utilizaron de manera eficiente solo una cantidad proporcional de memoria en relación con el tamaño del problema. ILBFS tuvo ligeras diferencias en el consumo de memoria porque manejó su lista abierta y la estructura de datos del árbol de una manera más explícita. Por otro lado, RBFS se basó en la pila de llamadas de su estrategia recursiva.

En general, ambos algoritmos demostraron ser efectivos en la gestión de memoria, cada uno con sus propias ventajas y desventajas.

#Conclusión

En resumen, ILBFS sirve como una alternativa útil a RBFS al proporcionar una forma más accesible de entender y enseñar los principios detrás de los algoritmos de búsqueda. Aunque puede funcionar más lento que RBFS, su naturaleza directa y funcionamiento claro lo hacen una herramienta valiosa para quienes buscan aprender sobre métodos de búsqueda eficientes.

Tanto RBFS como ILBFS logran abordar problemas de búsqueda utilizando memoria lineal y muestran patrones similares en cómo expanden nodos. Esto significa que, incluso si uno es preferido por velocidad, el otro ofrece una sólida experiencia de aprendizaje para cualquier persona interesada en los algoritmos de búsqueda. Al entender e implementar ILBFS, investigadores y practicantes pueden obtener una visión sobre estrategias de búsqueda eficientes en memoria sin perder los beneficios que vienen con el uso de un enfoque más complejo como RBFS.