D’andre Wolbrom Highfield – Estudiante de la carrera de Ingeniería en Informática

En el mundo actual, hay diferentes teorías que aportan al desarrollo de procesos y funciones que nos benefician y facilitan la forma en que vivimos, una de las teorías más implementadas y usadas en la actualidad es la teoría de grafos. El término “grafo” proviene de una palabra griega, que traducido al español significa dibujo o imagen. Un grafo es una composición entre un conjunto de objetos conocidos como nodos, y estos están relacionados por medio de un conjunto de conexiones (o líneas) llamadas aristas. Como lo estipula Graph Everywhere, una empresa que utiliza grafos para ordenar y conectar datos de otras empresas, “podemos representar diversas situaciones o elementos con grafos. Estos son extraordinariamente útiles en situaciones complejas, es por esto que es común conseguir la implementación de análisis de grafos en estudios de ciencias exactas, ciencias sociales y en aplicaciones informáticas.” (Graph Everywhere, s.f).

Existen tres tipos de grafos: los dirigidos (la relación entre los nodos es unidireccionales), los no dirigidos (se relacionan los nodos sin una dirección específica) y los grafos etiquetados (relaciones donde las aristas tienen peso, que representa la informacion adicional que porta). (Graph Everywhere, s.f). Dado que los grafos son utilizados para representar y modelar una infinidad de problemas que pueden ser representados computacionalmente, podemos saber que se implementan en bases de datos, movilidad de personas, Inteligencia Artificial, computación distribuida, redes sociales y mapas. Cada uno de los sectores anteriores tiene su propia especificación de objeto y relación (nodo-arista).

Hoy en día la tecnología es parte de nuestras vidas, la humanidad pasa en una constante movilidad o desplazamiento que conocemos como transporte. Sin embargo, muchas veces no tenemos el conocimiento de las rutas, calles y situaciones que se dan en lugares conocidos o desconocidos, y por eso utilizamos una aplicación llamada Waze, que utiliza tecnología de geolocalización tipo GPS y WPS. Esta aplicación es muy efectiva y beneficiosa, y un aspecto interesante es que está relacionado y basado con grafos (Chacón, 2017).

Lo que relaciona los grafos con Waze es un algoritmo en que el grafo se fundamenta y en el que se basa Waze, el Algoritmo de Dijkstra. Este algoritmo se utiliza para la determinación del camino más corto desde un vértice(nodo) de origen, y utiliza el peso de las aristas para relacionarse con los otros vértices. El algoritmo se detiene al analizar todos los pesos de las aristas y encuentra el camino más corto desde el vértice origen. El algoritmo se aplica en redes de computadores (donde los routers son los nodos y las aristas las conexiones entre ellos), transporte aéreo (tienen acceso a una base de datos que contiene toda la información sobre aviones circulando alrededor de ellos, y de la misma manera se evitan accidentes), y también es utilizado para la actualización de mapas digitales, como lo hace el funcionamiento de la aplicación de Waze. (Villegas, 2014).

La funcionalidad de Waze es la siguiente: la aplicación requiere de internet (Wifi) para poder conectarse con el servidor de Waze, de esta manera sabrá la localización del cliente y comenzará a ejecutarse el algoritmo de especulación. Este algoritmo especula y observa la información que recibe del personal de Waze y la tecnología de geolocalización, al solicitar el cliente una ruta el Waze muestra el resultado del algoritmo. El cliente también puede modificar las características de la ruta, por ejemplo, si quiere la ruta más corta, acceso a caminos de tierra, utilizar la ruta con la menor cantidad de giros, evitar autopistas, o seleccionar rutas tranquilas, entre otros.

Entre más clientes utilicen la aplicación de Waze, esta guardará la data y funcionará de manera más rápida, ya que muchos clientes viajan a las mismas localizaciones. Si un cliente ya viajó desde el punto C al punto D, y otro cliente quiere viajar de punto A al punto D, la aplicación comienza el algoritmo y devuelve la mejor ruta calculada de A al B, luego calcula la ruta del B al C, y continúa con el resultado que ya ha sido realizado por la aplicación. Si el conductor que está utilizando Waze se desvía, el mismo algoritmo comienza a trabajar para localizar la mejor ruta alterna para poder disponer de un resultado satisfactorio y beneficiario.

La información sobre las calles y leyes de tránsito de cada área es brindada a la aplicación y esta indica dónde es posible o no realizar acciones. Otra funcionalidad de la aplicación es que los clientes pueden reportar situaciones en las calles cuando suceden, como un choque, o la presencia de oficiales de tránsito. Estos datos son procesados por Waze, y luego son mostrados a los otros clientes para brindar más información sobre las calles. (Waze, 2015).

Para concluir el tema, los grafos son una representación de problemas actuales que pueden ser interpretados de forma gráfica o computacional, son una de las estructuras bases para las funciones que le facilitan la vida a la humanidad, ya que todo hoy en día es digital, y utilizamos mucho el internet, sus bases de datos y aplicaciones. Waze es una de las aplicaciones más usadas y está basada en la teoría de grafos, pues el usuario está en un punto específico (nodo) y utiliza las calles (aristas) para poder llegar a la ubicación que desea (otro nodo); ambos utilizan algoritmos para poder tener mejor función y un mejor resultado. La teoría de grafos y Waze nos facilitan la forma en la que nos trasladamos terrestremente, uno de los avances aplicativos más útiles e interesantes en la actualidad.

 

MOXIE es el Canal de ULACIT (www.ulacit.ac.cr), producido por y para los estudiantes universitarios, en alianza con el medio periodístico independiente Delfino.cr, con el propósito de brindarles un espacio para generar y difundir sus ideas.  Se llama Moxie - que en inglés urbano significa tener la capacidad de enfrentar las dificultades con inteligencia, audacia y valentía - en honor a nuestros alumnos, cuyo “moxie” los caracteriza.

Referencias bibliográficas:
• Graph Everywhere. (s.f.). Qué son los grafos. Recuperado de https://www.grapheverywhere.com/que-son-los-grafos/
• Chacón, C. (7 de octubre de 2017). ¿Cuál es la importancia de la teoría de grafos en las ciencias de la computación? Recuperado https://es.quora.com/Cu%C3%A1l-es-la-importancia-de-la-teor%C3%ADa-de-grafos-en-las-ciencias-de-la-computaci%C3%B3n
• Villegas, L. (2014). Algoritmo Dijkstra - Análisis de Algoritmos. Recuperado de https://prezi.com/f_yo-auccydf/algoritmo-dijkstra-analisis-de-algoritmos/
• Waze. (2015). Cómo calcula Waze las rutas. Recuperado de https://wiki.waze.com/wiki/Como_calcula_waze_las_rutas