2011-gre-cs-practice-book.pdf/Q12

Задача зарезервирована: Urmat A 16:29, 18 декабря 2024 (UTC)

Вопрос: Q12-08c765

Два классических алгоритма для поиска минимального остовного дерева в графе — это алгоритм Краскала(Крускала) и алгоритм Прима. Какие из следующих парадигм используются этими алгоритмами?

Ответы

Алгоритм Краскала - Алгоритм Прима

1. Правильный ответ: Жадный метод - Жадный метод
2. Жадный метод - Динамическое программирование
3. Динамическое программирование - Жадный метод
4. Динамическое программирование - Разделяй и властвуй
5. Разделяй и властвуй - Динамическое программирование

Объяснение

Достаточно взглянуть на суть этих алгоритмов. Условно, в алгоритме Крускала сортируются рёбра по возрастанию и жадно выбирается каждое следующее ребро, начиная от самого малого по весу, с условием, что не образуется цикл. Алгоритм Прима можно начинать из любой точки, но он также жадно выбирает на каждом шаге ребро с минимальным весом. При этом рассматривается любое ребро, которое инцидентно любой вершине дерева, но ещё не вошло в дерево, и которое не образует цикл. Решено: Urmat A 16:29, 18 декабря 2024 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.