Une el siguiente
List-I
A. Prim’s algorithm for minimum spanning tree
B. Floyd-Warshall algorithm for all pairs shortest paths
C. Mergesort
D. Hamiltonian circuit
List-II
1. Backtracking
2. Greed method
3. Dynamic programming
4. Divide and conquer
Codes:
A B C D
(a) 3 2 4 1
(b) 1 2 4 3
(c) 2 3 4 1
(d) 2 1 3 4
(A) a
(B) b
(C) c
(D) d
Respuesta: (C)
Explicación: el algoritmo de Prim es un algoritmo codicioso en el que la elección codiciosa es elegir el borde de peso mínimo del corte que divide los vértices ya seleccionados y los vértices que aún no se escogido.
El algoritmo de Floyd-Warshall para todos los pares de rutas más cortas es un algoritmo de programación dinámica en el que seguimos actualizando la array de distancia de forma ascendente.
Merge Sort es claramente divide y vencerás, que sigue todos los pasos de divide y vencerás. Primero divide la array en dos mitades, luego conquista las dos mitades y finalmente combina los resultados conquistados.
El circuito hamiltoniano es un problema completo NP, que se puede resolver usando
el cuestionario de retroceso de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA