DA - Algoritmos Voraces

En un algoritmo voraz la función solución devuelve verdadero cuando: Se obtiene la mejor solución. Se obtiene una solución posible. Se obtienen todas las soluciones posibles.

Para el grafo de la siguiente figura, el orden de selección de las aristas (descartando las que no cumplen las condiciones del problema) para el algoritmo de PRIM es, utilizando el nodo 1 como nodo de partida será: (1,3), (3,7), (7,2), (2,6), (6,5), (6,4). (1,3), (3,7), (7,2), (4,7), (4,6), (5,6). (1,3), (2,7), (4,6), (7,4), (5,6), (3,7).

Durante la ejecución del algoritmo de Kruskal. Se crea poco a poco una componente que acabará siendo la solución. Pueden aparecer varias componentes conexas, que acabarán uniéndose para formar la solución. El algoritmo de Kruskal no es óptimo para el problema de obtener un Árbol Generador Minimal.

Un algoritmo voraz: Comprueba todas las posibles combinaciones hasta dar con una válida. Construye la solución mediante la selección del mejor candidato. Puede aplicarse a problemas NP-completos.

Los vectores mindist y mascerca son usados en la resolución del: Algoritmo de Kruskal. Algoritmo de Prim. Algoritmo de Dijkstra. Problema de viajante de comercio.

Si necesitamos calcular el árbol generador minimal de un grafo muy denso: Debemos usar el algoritmo de Kruskal. Debemos usar el algoritmo de Prim. Es indiferente cuál de ellos usar. En grafos densos no son aplicables estos algoritmos.

El problema del viajante de comercio, al igual que el de AGM: Permite la formación de estrellas. Evita la generación de estrellas no permitiendo la selección de una tercera arista incidente al mismo nodo. Puede contener ciclos intermedios.

Un algoritmo voraz que solucione el problema de colorear un grafo: Siempre da la misma solución, independientemente de la selección de los nodos. Dará una solución, en caso de existir, dependiente del orden de selección de los nodos. No se puede aplicar un algoritmo voraz a este problema.

Los algoritmos de Kruskal y Prim: Pueden dar una solución que no sea óptima. Siempre dan la solución óptima. Kruskal puede no dar la solución óptima, pero Prim siempre la dará. Prim puede no dar la solución óptima, pero Kruskal siempre la dará.

El problema del cambio de monedas resulto mediante un algoritmo voraz: Si existe, dará la solución óptima. No puede aplicarse un algoritmo voraz a este problema. Puede no encontrar la solución, aunque exista. Selecciona una moneda aleatoria del conjunto de pendientes.

Las heurísticas voraces: Nunca pueden dar la solución óptima. Siempre dan una solución, ya sea óptima, parcial, o errónea. No pueden aplicarse a problemas NP-completos debido a su mala eficiencia.

En el algoritmo de Dijkstra: La eficiencia nunca varía, independientemente de la estructura usada. Siempre es más eficiente representar el grafo como un array bidimensional. Siempre es más eficiente representar el grafo como una matriz dispersa, mediante un array de listas. La estructura a usar depende de la densidad del grafo.

El problema de la mochila resuelto mediante un algoritmo voraz en el que se permite tomar fracciones de un objeto: La función de selección no altera el resultado final. No puede aplicarse un algoritmo voraz a este problema. La solución siempre será óptima, independientemente del orden de selección de los objetos. La función de selección determinará la optimalidad de la solución.

El problema del viajante de comercio implementado mediante un algoritmo voraz que eliga la arista más corta (con las restricciones vistas en teoría): Puede generar ciclos intermedios y estrellas en la solución. Sólo requiere de un vector para alcanzar la solución. Siempre da una solución óptima. Da una solución, no necesariamente óptima, en un tiempo razonable.

En un algoritmo voraz: Al descartar un candidato, nunca más se vuelve a considerar. Si un candidato es parte de la solución, puede descartarse si no se encuentra la solución. La función de selección devuelve el mejor candidato, independientemente de si ya ha sido considerado o no.

Al aplicar Dijkstra al siguiente grafo, los caminos mínimos para cada nodo serán: En ("x","y"), "x" indica el nodo e "y" la longitud del camino. (2,3), (3,6), (4,7), (5,9). (2,3), (3,6), (4,13), (5,12). (2,3), (3,6), (4,13), (5,15). No puede aplicarse el algoritmo al grafo dado.