Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 24

Алгоритм Флойда-Варшалла для вычисления кратчайших путей во всех парах основан на:

(A) Жадная парадигма.
(B) Парадигма «разделяй и властвуй».
(C) Парадигма динамического программирования.
(D) ни Жадная, ни «разделяй и властвуй», ни парадигма динамического программирования.

Ответ: (с)
Пояснение: Алгоритм Флойда Варшалла — это алгоритм, основанный на динамическом программировании .

Он находит все пары кратчайших путей, используя следующую рекурсивную природу проблемы.

Для каждой пары (i, j) исходных и конечных вершин соответственно существует два возможных случая.
1) k не является промежуточной вершиной кратчайшего пути из i в j. Мы сохраняем значение dist [i] [j] как есть.
2) k — промежуточная вершина кратчайшего пути из i в j. Мы обновляем значение dist [i] [j] как dist [i] [k] + dist [k] [j].

Следующий рисунок взят из книги Кормена. Это показывает указанное выше оптимальное свойство субструктуры в задаче кратчайшего пути всех пар.

Поскольку в рекурсии есть перекрывающиеся подзадачи , используется динамическое программирование.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 24

0.00 (0%) 0 votes