1. Describir la Metodología de resolución de problemas “Algoritmos Voraces o Devoradores”.
1.1 Aplicación y alcance.
1.2 Elementos característicos.
1.2 Esbozo del coste computacional.
2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleve a cabo mediante esta metodología. Aplicarla.
2.1 Identificación de los elementos característicos.
2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.
2.3 Implementación en C y ejemplos ilustrativos.
2.4 Coste computacional aproximado.
1. Describir la Metodología de resolución de problemas “Algoritmos Voraces o Devoradores”.
Un algoritmo voraz (también conocido como devorador) es aquel que, para resolver un determinado problema, sigue un método que consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.
Si bien, es cierto que se pueden encontrar varias soluciones óptimas. Pero en alguna ocasiones no se logra encontrar ninguna solución que sea optima, pero en estos casos se permite encontrar una solución aproximada con un coste computacional bajo.
1.1 Aplicación y alcance.
Los algoritmos voraces se aplican normalmente a problemas de optimización, en la búsqueda del valor óptimo ( máximo o mínimo ) de una cierta función, la cual es el objetivo a conseguir.
En estos algoritmos las soluciones se pueden representar como una secuencia de decisiones, las cuales se realizarán de forma irreversible.
Con respecto al alcance de este tipo de algoritmos, una aproximación voraz consiste en que cada elemento a considerar se evalúa una única vez, siendo descartado o seleccionado, de tal forma que si es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma.
El término voraz se deriva de la forma en que los datos de entrada se van tratando, realizando la elección de desechar o seleccionar un determinado elemento una sola vez.
Al contrario que con otros métodos algorítmicos, no siempre es posible dar una solución a un problema empleando un algoritmo voraz. No todos los problemas son resolubles con algoritmos voraces, en estos casos se determina que el problema a solucionar, está fuera del alcance del algoritmo y se tendrán que emplear otros métodos.
1.2 Elementos característicos.
- El conjunto C de candidatos, entradas del problema.
- Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución (no importa si es óptima o no lo es).
- Función de selección. Informa de cuál es el elemento más prometedor para completar la solución. Éste no puede haber sido escogido con anterioridad. Cada elemento es considerado una sola vez. Luego, puede ser rechazado o aceptado.
- Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.
- Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.
1.3 Esbozo del coste computacional.
Los algoritmos voraces tienden a ser bastante eficientes y pueden implementarse de forma relativamente sencilla. Su eficiencia se deriva de la forma en que trata los datos, llegando a alcanzar muchas veces una complejidad de orden lineal. Sin embargo, la mayoría de los intentos de crear un algoritmo voraz correcto fallan a menos que exista previamente una prueba precisa que demuestre que el algoritmo es correcto. Por todo lo anterior el coste de estos algoritmo depende de dos factores:
1. Del número de iteraciones, que a su vez depende del tamaño de la solución construida y del tamaño del conjunto de candidatos.
2. del coste de las funciones selección y factible ya que el resto de las operaciones del interior del bucle tienen coste constante. la función factible, en la mayoría de los casos, sólo necesita tiempo constante, pero la función selección ha de explorar el conjunto de candidatos y obtener el mejor en ese momento.
por eso depende del tamaño del conjunto de candidatos. Normalmente se prepara ( preprocesa ) el conjunto de candidatos antes de entrar en el bucle para rebajar el coste de la función de selección y conseguir que éste sea lo más cercano posible a constante. Precisamente, debido a su bajo coste.
2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleve a cabo mediante esta metodología. Aplicarla.
En la ciudad de Albacete, de la que conocemos completamente su mapa, es decir, conocemos todas las intersecciones de las calles y todas sus longitudes. Supongamos que en cada intersección de calles existe una plaza.
La concejalía de festejos ha decidido engalanar las calles para la celebración de las Ferias y fiestas 2011. Sin embargo, como el presupuesto es reducido ha decidió engalanar aquellos tramos de calle de tal forma que todas las plazas cercanas al recinto ferial queden unidas por tramos de calle engalanadas. Para ello se determinará que tramos de calle son necesarios engalanar para resolver el problema con un coste mínimo.
2.1 Identificación de los elementos característicos.
Para identificar los elementos característicos, primeramente se establece un TAD, para representar todos aquellos conjuntos disjuntos.
Se supondrá que el mapa de calles cercanas al recinto ferial se representará mediante un Grafo, donde cada Calle estará determinada por una Arista, donde se establecerá la longitud de la calle y cada plaza se representa con un Nodo.
Posteriormente usaremos voraz, con la siguiente información:
Candidatos a la solución: Calles a engalanar.
Ordenación: Ordenaremos las calles de menor a mayor longitud.
Función de selección: No existe.
Función de factibilidad:
Selecciono la calle con menor longitud, ya que será la de menor coste.
Si no existe ningún ciclo entre la calle seleccionada y las ya establecidas en la solución, y sus nodos pertenecen a dos componentes conexas, entonces: Acepto la calle.
Else : descartamos la calle.
Función solución: Se realizará la función de factibilidad mientras que no tengamos un número de aristas igual al número de nodos menos uno, ( n-1 ). Cuando esto deje de ocurrir, se devuelve la solución, devolviendo la matriz de adyacencia del grafo.
2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.
Supondremos para la resolución del problema, que Las calles son Aristas y las plazas, nodos. De esta forma establecemos un Grafo en el que tendremos todos los nodos unidos mediante sus correspondientes aristas., y con esto establecemos en que intersecciones se unen unas determinadas calles.
Además, suponemos que todas las calles tiene el mismo coste de engalanamiento por unidad de longitud, que se determinará como “g”.
El problema que se nos plantea con este planteamiento es obtener el árbol de recubrimiento mínimo del Grafo formado por todas las calles ( aristas ) y plazas ( Nodos ) , próximas al recinto ferial de Albacete.
Como anteriormente se determinaba, los algoritmos voraces son aquellos que con lo que ya ha resuelto, y con lo que tiene actualmente puede llegar a la resolución del problema. En nuestro caso demostraremos que el problema se puede resolver con un método usado en este tipo de algoritmos, el denominado método de Kruskal.
Este método aplicado a nuestro problema en pseudocódigo, será el siguiente
/* Inicialización*/
Ordenamos el cjto de calles por longitudes creciente.
n = numero de vértices del grafo.
Creamos una matriz bidimensional, vacía y cuadrada, de tamaño n, que denominaremos T.
Creamos una partición de “n” conjuntos y ponemos cada vértice del grafo en el conjunto, mediante otra matriz.
Recibimos en una matriz de adyacencia el grafo con las calles y las plazas, donde el valor será la longitud
Creamos una matriz, vacía T de aristas ( Array[][]), la cual será la matriz de adyacencia de la solución.
/*Voraz*/
Repetir
e = La calle con menor longitud, aún no usada.
Sean “U” y “V” los vértices que unen “e” (índices del array) y “X” e “Y” el nuevo conjunto a añadir, que contienen a “U” y “V”.
Si “U” ≠ “V” entonces
Unimos “X” e “Y”;
Añadimos “e” a la lista T;
Fin_si
Hasta que la partición tenga 1 solo conjunto (es como decir, que lleguemos a n-1 aristas).
Devolver T (Que es la solución).
Lo más complejo que encontramos en la resolución, es como saber si una calle, dada por ejemplo por los nodos (v,w) provocará un ciclo. Para ello, usamos la definición que determina, que una calle forma un ciclo si v y w están en la misma componente conexa.
Con lo cual, queda demostrado, que la obtención de la solución es mediante métodos voraces.
2.3 Implementación en C y ejemplos ilustrativos.
Para la realización del código en C se han seguido aproximadamente los pasos realizados en el pseudocódigo anteriormente mostrado. En primer lugar vamos a mostrar el código realizado con el ejemplo de un grafo de 7 vértices, dicho grafo es el que se nos muestra en la wikipedia.
#include#include #include //Esta función es la encargada de construir la matriz //de adyacencia recibiendo como parámetro el número de nodos //además nos imprime por pantalla la matriz de adyacencia. void AdjacencyMatriz(int a[][100], int n){ int i,j; /* Ejemplo 1, grafo de wikipedia */ /*int mia[7][7] = {{0, 7, 0, 5, 0, 0, 0}, {7, 0, 8, 9, 7, 0, 0}, {0, 8, 0, 0, 5, 0, 0}, {5, 9, 0, 0, 15, 6, 0}, {0, 7, 5, 15, 0, 8, 9}, {0, 0, 0, 6, 8, 0, 11}, {0, 0, 0, 0, 9, 11, 0}}; */ /*Ejemplo 2, grafo inventado 5 nodos*/ int mia[5][5]={{0,3,6,2,7}, {3,0,0,0,0}, {6,0,0,5,2}, {2,0,5,0,9}, {7,0,2,9,0}}; /* Pinto el array*/ for(i = 0;i < n; i++) { for(j = 0;j < n; j++) { a[i][j] = a[j][i]= mia[i][j]; printf("%d\t",a[i][j]); } printf("\n"); a[i][i] = 0; } } //Esta función comienza buscando la arista int comienzo(int v,int p[]){ while( p[v] != v ) v = p[v]; return v; } //Esta función solo nos une los nodos con un orden //lógico en el vector solución void union_ij(int i,int j,int p[]){ if(j > i) p[j] = i; else p[i] = j; } //Esta es la función correspondiente al algoritmo de Kruskal void kruskal(int a[][100],int n){ //int i, p[10], min, j, u, v, k, t[7][7], sum; int i, p[10], min, j, u, v, k, t[5][5], sum; k = sum = 0; for(i = 0; i < n; i++) p[i] = i; while(k < n-1){ min = 999;//establecemos un mímino principal lo suficientemente grande for(i = 0; i < n; i++){ for(j = 0;j < n-1; j++){ if(a[i][j] < min && a[i][j] != 0){ min = a[i][j]; u = i; v = j; } } }// Fin del for if(min != 999){ i = comienzo(u, p); j = comienzo(v, p); if (i != j){ t[k][0] = u; t[k][1] = v; k++; sum += min; union_ij(i,j,p); }// fin if a[u][v] = a[v][u] = 0; }// fin if }// Fin_while if(k != n-1){ printf("No existe el arbol\n"); } if(k == n-1){ printf("Arbol para engalanar todas las calles:\n"); for(k = 0; k < n-1 ; k++){ printf(" %i -> %i ",t[k][0]+1,t[k][1]+1); } printf("\nCoste de engalanar = %d \n",sum); } } //La función principal nos pedirá el número de nodos del grafo //y construirá la matriz de adyacencia y llamará al algoritmo //de kruskal int main() { int a[100][100],n; printf("Introduce numero de vertices.\n"); scanf("%d",&n); AdjacencyMatriz(a,n); kruskal(a,n); //Esta dos líneas es para que no se cierre la consola //al ejecutar el código system("pause"); return EXIT_SUCCESS; }
2.4 Coste computacional aproximado.
El coste total del problema vendrá acotado por el coste más grande de las funciones, que como podemos observar corresponde con la función kruskal que da un total de n3 vueltas debido al while y al doble bucle for, que dan los 3 n vueltas.
Por último comentar que la solución que hemos implementado en nuestro trabajo no es la más adecuada como observamos en el coste computacional del problema ya que se puede conseguir una complejidad mejor:
m=Aristas, n=Nodos
• primero se ordenan las aristas por su peso usando una ordenación por comparación con una complejidad del orden de O(m log m).
• Lo siguiente es usar una estructura de datos sobre conjuntos disjuntos para controlar qué vértices están en qué componentes. Es necesario hacer orden de O(m) operaciones ya que por cada arista hay dos operaciones de búsqueda y posiblemente una unión de conjuntos. Incluso una estructura de datos sobre conjuntos disjuntos simple con uniones por rangos puede ejecutar las operaciones mencionadas en O(m log n). Por tanto, la complejidad total es del orden de O(m log m) = O(m log n).
1 comentarios:
ME AYUDO BASTANTE
Publicar un comentario