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