De visita por los vértices

Question 1

Descripción paso a paso de cómo resolver un problema.

Answer 1

Algoritmo

Question 2

Forma de resolver un problema de optimización, en el que en cada etapa del algoritmo se elige la solución mejor (o más barata).

Answer 2

Algoritmo avaro

Question 3

¿ Los algoritmos avaros siempre llevan a soluciones óptimas?

Answer 3

No siempre

Question 4

Algoritmo desarrollado por Joseph Kruskal (Laboratorios AT&T Bell) que resuelve el problema del árbol generador de coste mínimo eligiendo las aristas en orden de incremento de costes, pero de forma que ninguna arista forme un circuito con las aristas elegidas anteriormente.

Answer 4

Algoritmo de Kruskal

Question 5

¿El algoritmo de Kruskal siempre produce una solución óptima?

Answer 5

Si, se puede probar que la solución encontrada con este algoritmo es siempre la solución óptima.

Question 6

Algoritmo para intentar resolver el PV, en el que las aristas añadidas al circuito que se está construyendo son elegidas en orden de incremento de costes, pero no se añade ningún circuito que impida la formación de un circuito hamiltoniano.

Answer 6

Algoritmo de las aristas clasificadas

Question 7

Algoritmo para intentar resolver el PV que comienza en un vértice «base» y visita a continuación el vértice más cercano aún no visitado que se pueda alcanzar.

Answer 7

Algoritmo del vecino más cercano

Question 8

Método rápido para resolver problemas de optimización, pero que no garantiza una respuesta óptima al problema.

Answer 8

Algoritmo heurístico

Question 9

Grafo conexo sin circuitos.

Answer 9

Árbol

Question 10

Número asignado a una arista de un grafo 1 que puede representar el coste, la distancia o el tiempo asociado con dicha arista.

Answer 10

Peso

Question 11

Subgrafo de un grafo conexo que es un árbol e incluye todos los vértices del grafo original.

Answer 11

Árbol generador

Question 12

Circuito que comienza y termina en un mismo vértice, que utiliza distintas aristas de un grafo y que visita cada vértice una sola vez.

Answer 12

Circuito hamiltoniano

Question 13

¿Un circuito hamiltoniano puede empezar en cualquiera de sus vértices?

Answer 13

Si puede

Question 14

Método que resuelve el problema del viajante (PV) encontrando todos los circuitos hamiltonianos y luego eligiendo el de coste mínimo.

Answer 14

Método de la fuerza bruta

Question 15

Método gráfico para llevar a cabo el principio fundamental de contar.

Answer 15

Método del árbol

Question 16

Método para contar las posibilidades que existen en un proceso de etapas múltiples.

Answer 16

Principio fundamental de contar

Question 17

El problema de encontrar un circuito hamiltoniano de coste mínimo en un grafo completo en el que a cada arista se le ha asignado un coste (o peso).

Answer 17

Problema del viajante (PV)

Question 18

Conjunto de problemas, que incluye el PV, para los que parece ser muy difícil encontrar la solución óptima con rapidez.

Answer 18

Problemas NP-completos