2011-gre-cs-practice-book.pdf/Q12
Задача зарезервирована: Urmat A 16:29, 18 декабря 2024 (UTC)
Вопрос: Q12-08c765
Два классических алгоритма для поиска минимального остовного дерева в графе — это алгоритм Краскала(Крускала) и алгоритм Прима. Какие из следующих парадигм используются этими алгоритмами?
Ответы
Алгоритм Краскала - Алгоритм Прима
- Правильный ответ: Жадный метод - Жадный метод
- Жадный метод - Динамическое программирование
- Динамическое программирование - Жадный метод
- Динамическое программирование - Разделяй и властвуй
- Разделяй и властвуй - Динамическое программирование
Объяснение
Исходники — вопрос 12 на 20 странице книги «2011-gre-cs-practice-book.pdf»
Достаточно взглянуть на суть этих алгоритмов. Условно, в алгоритме Крускала сортируются рёбра по возрастанию и жадно выбирается каждое следующее ребро, начиная от самого малого по весу, с условием, что не образуется цикл. Алгоритм Прима можно начинать из любой точки, но он также жадно выбирает на каждом шаге ребро с минимальным весом. При этом рассматривается любое ребро, которое инцидентно любой вершине дерева, но ещё не вошло в дерево, и которое не образует цикл.
Решено: Urmat A 16:29, 18 декабря 2024 (UTC)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.