Diseño de Algoritmos

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 Kruscal. Debemos usar el algoritmo de Prim. Es indiferente cuál de ellos usar. En grafos densos no son aplicables estos algoritmos.

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).

En algoritmos voraces, la función solución determina si la solución encontrada es óptima. V. F.

En algoritmos voraces, la función objetivo determina si la solución encontrada es óptima. V. F.

En algoritmos voraces, la función solución determina si un conjunto de datos es solución (pero no necesariamente la óptima). V. F.

En algoritmos voraces, la función objetivo determina si un conjunto de datos es solución (pero no necesariamente la óptima). V. F.

Durante la ejecución del algoritmo de Kruskal se pueden tener varias componentes conexas, hasta que el algoritmo para, que sólo queda una, la solución. V. F.

Una arista “toca” un conjunto de nodos cuando uno de sus extremos o los dos están en dicho conjunto de nodos. V. F.

En el problema del viajante del comercio, al igual que en el problema del árbol de recubrimiento mínimo, no se permiten la formación de estrellas ni ciclos. V. F.

En el problema del viajante del comercio, al igual que en el problema del árbol de recubrimiento mínimo, no se permiten la formación de estrellas. V. F.

En el problema del viajante del comercio, al igual que en el problema del árbol de recubrimiento mínimo, se permiten la formación de estrellas. V. F.

Dependiendo del orden en el que se vayan seleccionado los nodos, el algoritmo voraz que soluciona el problema del Coloreado de un Grafo puede devolver distintas soluciones. V. F.

En todo Algoritmo Voraz existe una función solución que es la que se desea optimizar. V. F.

En todo Algoritmo Voraz existe una función objetivo que es la que se desea optimizar. V. F.

Una función que, en un primer paso, escoge n nodos de un grafo como conjunto de viables para posteriormente, en un segundo paso, poder designar un elegido para la solución, puede ser considerada función de selección. V. F.

Una función que, en un primer paso, escoge n nodos de un grafo como conjunto de viables para posteriormente, en un segundo paso, poder designar un elegido para la solución, puede ser considerada función de solución. V. F.

El algoritmo de Dijkstra devuelve los caminos mínimos entre todas las parejas de nodos del grafo. V. F.

El algoritmo del cambio de monedas diseñado mediante un algoritmo voraz siempre devuelve la solución óptima para el problema. V. F.

En el problema del viajante del comercio, al igual que en el problema del árbol de recubrimiento mínimo, se permiten la formación de estrellas. V. F.

Durante la ejecución del algoritmo de Kruskal, en todo momento hay una sola componente conexa. V. F.

Durante la ejecución del algoritmo de Prim en todo momento hay una sola componente conexa. V. F.

La función selección de un algoritmo voraz siempre elige el mejor candidato potencial del momento sin preocuparse del futuro. V. F.

La función solución de un algoritmo voraz siempre elige el mejor candidato potencial del momento sin preocuparse del futuro. V. F.

En un algoritmo voraz la función solución devuelve verdadero cuando se obtiene la mejor solución. V. F.

Un algoritmo heurístico es un procedimiento que siempre produce la solución óptima para un problema determinado y para el que no es necesario demostrar su corrección. V. F.

En un grafo con todas las aristas distintas el árbol generador minimal obtenido por el algoritmo de Kruskal es idéntico al obtenido por el algoritmo de Prim. V. F.

En todo Algoritmo Voraz existe una función solución que es la que se desea optimizar. V. F.

El uso de heaps en el algoritmo de Dijkstra mejora el orden eficiencia. V. F.