Temas acerca de Inteligencia Artificial
Foto de Usuario
SandroCastillo

Ranking Troomes
Mensajes: 7
Registrado: 20 Abr 2020, 17:42

Aplicaciones de Inteligencia Artificial basadas en algoritmos de búsqueda

Mensaje por SandroCastillo » 10 May 2021, 11:26

En el presente tema se abordará aplicaciones de Inteligencia Artificial que utilicen algoritmos de búsqueda. En este caso se comentará dos investigaciones que utilizan estos. La primera utiliza el algoritmo de busqueda de ruta más corta, mientras que la segunda utiliza el algoritmo de búsqueda de árboles binarios.

[1] Study of the Application of A* Shortest Path Search Algorithm in Dynamic

El problema presentado en este paper es encontrar la ruta más rápida para llegar de un punto a otro bajo las condiciones de tráfico urbano.

El algoritmo utilizado es el algoritmo de busqueda de ruta más corta A*. Este algoritmo utiliza una función de costo en cada estado el cual se representa como la suma del costo actual, g, y el costo estimado de la ruta más corta en el nodo n, h. En resumen, se entiende como f(n) = g(n) + h(n).

En el caso presentado, el cual refiere a la ruta más corta en tráfico urbano, la variable g(n) representará el tiempo de viaje realizado desde un nodo inicial y la variable h(n) representará el tiempo estimado desde el nodo n hasta el nodo destino.

Cabe resaltar que dado el dinamismo del tráfico se requerirá recalcular la ruta más corta cada cierto número de minutos. En el trabajo comentado se menciona que se realiza cada 5 minutos. Así mismo para la estimación de h(n) se utilizará data histórica de los recorridos en el lugar, considerando el tiempo en ruta libre, la demora por intersecciones y la demora por tráfico.

En los resultados se muestra una simulación en que el algoritmo utilizado encuentra la ruta más rápida en una red de 2500 nodos y así mismo, marca los límites con los datos obtenidos. Cabe considerar que en la investigación no se detalla qué herramientas se utilizaron para realizar esta simulación.

[2] Implementing binary search tree concept for image criptography

El problema presentado en este paper es reducir el consumo de recursos y de tiempo en la realización de encriptación de imágenes modificando los algoritmos más usados como AES y DES.

El algoritmo utilizado es de árbol de búsqueda binaria. Este algoritmo clasifica y ordena datos en un árbol en base a reglas como puede ser las de comparación.

En el caso presentado lo que se busca es crear llaves públicas y privadas generadas por un árbol de búsqueda binaria para encriptación de imágenes. A partir de una llave pública o privada se genera un árbol binario que reordenara está clave de manera secuencial de tal forma que se genere una nueva clave. Luego, realizando operaciones de sustitución y transposición se obtienen las imágenes encriptadas.

El algoritmo se probó con 3 imágenes y los resultados se compararon con los de otros algoritmos como AES y DES. Los resultados indicaron que el algoritmo de árbol de búsqueda binaria tuvo resultados similares a AES y DES en error absoluto y en valores pico de ruido; sin embargo, se encontró una gran mejora en el tiempo de encriptación del algoritmo propuesto, pudiendo reducir este a menos del 50%. Cabe considerar que en la investigación no se detalla qué herramientas se utilizaron para realizar estas pruebas.

Conclusiones:

De estos dos trabajos se concluye que los algoritmos de búsqueda pueden ser aplicados tanto a problemas reales como encontrar la ruta más rápida en tráfico urbano como en problemas de rendimiento de algoritmos como encontrar uno que mejore el tiempo de encriptación.

Referencias:

1. Yue, H. & Shao, C. (2007). Study of the Application of A* Shortest Path Search Algorithm in Dynamic. Thrid International Conference on Natural Computation.

2. Al-Husainy, M. & Al-Sewadi, H. (2019). Implementing binary search tree concept for image criptography. International Journal of Advanced Science and Technology. Vol. 130, pp. 21-32.


Sandro Sebastián Castillo Alarcón
Estudiante de Ingeniería de Sistemas
Universidad Nacional de Ingeniería
Responder