Minimum spanning tree con Delphi (Parte I)
En este artículo os presento mi solución al Minimum spannin tree (Árbol recubridor mínimo) con una pequeña aplicación en Delphi 2009. Para esta aplicación, he implementado el algoritmo del Prim (en la wiki podéis encontrar una buena descripción del algoritmo). Mediante una imagen, con una serie de puntos aleatorios, lo que hago es escanear la imagen pixel a pixel hasta ir encontrando los puntos que hay marcados en la imagen. Una vez reconocidos los puntos, los guardo en una lista de Puntos y a partir de aquí creo la lista de adyacencias, ya que la conexión es n-ária, todos contra todos, y de lo que se trata es de conseguir el árbol recubridor mínimo que engloba todos los puntos. Una vez tengo los puntos, las conexiones y su peso (en pixels), puedo pasar a generar mi solución con el algoritmo del Prim. En esta versión he puesto un límite de 100 nodos, aunque el coste de la operación es bastante bajo (O(n^2)). En mi propuesta, podremos cargar diferentes imágenes e ir viendo su coste:
Como podéis ver, en una primera instancia, tenemos la imagen con los puntos marcados aleatoriamente (lo podemos hacer con el Paint con la medida de 1 Pixel).
Una vez los he marcado i reconocido, los marco con un color Fucsia para indicar que el programa ha reconocido los puntos de la imagen. Si miramos la lista de puntos podemos ver:
1 X: 76 Y: 44 Color: 9718288
2 X: 100 Y: 126 Color: 3581348
3 X: 108 Y: 72 Color: 16149651
4 X: 178 Y: 91 Color: 6455125
5 X: 180 Y: 61 Color: 3485918
6 X: 191 Y: 27 Color: 13378705
7 X: 219 Y: 7 Color: 2409329
8 X: 230 Y: 122 Color: 10836242
Que ha encontrado 8 puntos en las posiciones X y Y i además el color que ha encontrado. Ahora solo tenemos que generar la lista de adyacencias, todos contra todos y encontrar el árbol mínimo.
Podemos ver que en la diagonal de la matriz siempre tienen que aparecer ceros, ya que estamos calculando la distancia de un punto a si mismo, por lo tanto no puede ser diferente de cero.Si ahora pasamos el algoritmo del prim, el programa encontrará el árbol conector mínimo y nos indicara el coste de este árbol en pixels:
Si hacemos click sobre el botón de conectar puntos, nos mostrará el grafo total con las conexiones de todos los puntos:
Si hacemos lo mismo con el ejemplo anterior obtendremos:
Como podéis ver en la última imagen, si generamos una conexión de todos contra todos no se entiende nada, pero esta es la imagen del grafo total. Aquí os dejo la aplicación para que la probéis: ThundaxSpanningTree.exe, y un par de imagenes de prueba para que hagáis vuestras comprobaciones. ejemplo1.bmp, ejemplo2.bmp.- Enlaces de interés:
http://www.algorithm-code.com/wiki/Prim%27s_algorithm
Aquí podemos encontrar diferentes muestras con Applets:
http://students.ceid.upatras.gr/~papagel/project/prim.htm
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml
Comments
Post a Comment