Manizales, oct. 25 de 2013 - Agencia de Noticias UN – Con base en el juego Batalla Naval, estudiantes diseñaron dos algoritmos que optimizan el método para destruir barcos del contrincante; igualmente, pueden emplearse para reducir la complejidad de ciertos programas.

Con el fin de desarrollar códigos de programación más eficaces, estudiantes de Administración de Sistemas Informáticos, de la Universidad Nacional de Colombia en Manizales, se apoyaron en el juego Batalla Naval, pero no en su versión tradicional entre dos jugadores sino con la participación del computador; de este modo, elaboraron dos algoritmos que posibilitan optimizar la búsqueda y destrucción del objetivo.

El primer desarrollo es un algoritmo que permite ubicar los barcos en una matriz de 10 x 10 para encontrarlos de la manera más rápida y destruirlos.

“El algoritmo contó con una técnica de programación inspirada en la idea de ‘divide y vencerás’, que consiste en tomar la matriz y hacer el primer impacto en el centro, si este es fallido, se divide en cuadrantes y se realiza otro tiro en alguno de estos puntos, y así sucesivamente en los demás hasta dar con la ubicación de los barcos”, afirmó Jhon Elkin Romero, estudiante del pregrado en Administración de Sistemas Informáticos de la Sede Manizales.

Una vez encontrados, se utilizó la técnica de regresión o back tracking, que se basa en revisar las áreas aledañas a la posición del impacto para destruir el barco en su totalidad; si a la derecha hay rastros continua en esa dirección, si no, se devuelve por el camino recorrido y revisa a la izquierda hasta encontrar el punto que permita destruirlo por completo.

Igualmente, el estudiante Edward Morales Osorio desarrolló otro algoritmo para resolver el mismo juego. En este caso, el usuario es el que le indica a la máquina si el impacto fue exitoso.

La técnica implementada consiste en hacer un disparo al azar en cualquier parte de la matriz, hasta que el usuario anuncie un impacto positivo, a partir de ahí se sigue un patrón en cruz (primero a la derecha, luego a la izquierda, continua abajo y termina arriba) para hallar la orientación de los demás barcos y destruirlos siguiendo dicho patrón.

Estas técnicas también pueden implementarse para reducir el tiempo de ejecución de problemas computacionales y obtener soluciones óptimas para disminuir la complejidad de programas que consumen mucha memoria y congestionan la máquina; por ejemplo, para hallar las mejores rutas que conectan redes y para el proceso de búsqueda de una base de datos, entre otros.

(Por:Fin/AMEJ/CAPG/jcrf)