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