Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 16

Подходим следующее

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 

(А)
(Б) б
(С) с
(D) d

Ответ: (с)
Объяснение: Алгоритм Прима — это жадный алгоритм, в котором жадный выбор состоит в том, чтобы выбирать ребро с минимальным весом из разреза, которое делит уже выбранные вершины и вершины, которые еще предстоит выбрать.

Алгоритм Флойда-Варшалла для всех пар кратчайших путей — это алгоритм динамического программирования, в котором мы продолжаем обновлять матрицу расстояний снизу вверх.


Сортировка слиянием
— это «разделяй и властвуй», которая следует за всеми этапами «разделяй и властвуй». Сначала он делит массив на две половины, затем захватывает две половины и, наконец, объединяет побежденные результаты.

Гамильтонова цепь — это полная проблема NP, которая может быть решена с помощью Backtracking

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 16

0.00 (0%) 0 votes