2011-gre-cs-practice-book.pdf/Q12 — различия между версиями
Urmat A (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q12-08c765 == | == Вопрос: Q12-08c765 == | ||
| − | Два классических алгоритма для поиска минимального остовного дерева в | + | Два классических алгоритма для поиска минимального остовного дерева в графе — это [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D0%BB%D0%B0 алгоритм Краскала] (Крускала) и [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0 алгоритм Прима]. |
| + | |||
| + | Какие из следующих парадигм используются этими алгоритмами? | ||
| + | Варианты задаются парами «для алгоритма Краскала» — «для алгоритма Прима». | ||
=== Ответы === | === Ответы === | ||
| − | + | ||
| − | + | * Правильный ответ: Жадный метод — Жадный метод | |
| − | + | * Жадный метод — Динамическое программирование | |
| − | + | * Динамическое программирование — Жадный метод | |
| − | + | * Динамическое программирование — Разделяй и властвуй | |
| − | + | * Разделяй и властвуй — Динамическое программирование | |
=== Объяснение === | === Объяснение === | ||
| Строка 17: | Строка 19: | ||
Достаточно взглянуть на суть этих алгоритмов. Условно, в алгоритме Крускала сортируются рёбра по возрастанию и жадно выбирается каждое следующее ребро, начиная от самого малого по весу, с условием, что не образуется цикл. Алгоритм Прима можно начинать из любой точки, но он также жадно выбирает на каждом шаге ребро с минимальным весом. При этом рассматривается любое ребро, которое инцидентно любой вершине дерева, но ещё не вошло в дерево, и которое не образует цикл. | Достаточно взглянуть на суть этих алгоритмов. Условно, в алгоритме Крускала сортируются рёбра по возрастанию и жадно выбирается каждое следующее ребро, начиная от самого малого по весу, с условием, что не образуется цикл. Алгоритм Прима можно начинать из любой точки, но он также жадно выбирает на каждом шаге ребро с минимальным весом. При этом рассматривается любое ребро, которое инцидентно любой вершине дерева, но ещё не вошло в дерево, и которое не образует цикл. | ||
| − | {{question-ok|}} | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 20:52, 18 декабря 2024 (UTC)}} |
| − | + | [[Категория:Алгоритмы на графах]] | |
Текущая версия на 20:52, 18 декабря 2024
Вопрос: Q12-08c765
Два классических алгоритма для поиска минимального остовного дерева в графе — это алгоритм Краскала (Крускала) и алгоритм Прима.
Какие из следующих парадигм используются этими алгоритмами? Варианты задаются парами «для алгоритма Краскала» — «для алгоритма Прима».
Ответы
- Правильный ответ: Жадный метод — Жадный метод
- Жадный метод — Динамическое программирование
- Динамическое программирование — Жадный метод
- Динамическое программирование — Разделяй и властвуй
- Разделяй и властвуй — Динамическое программирование
Объяснение
Исходники — вопрос 12 на 20 странице книги «2011-gre-cs-practice-book.pdf»
Достаточно взглянуть на суть этих алгоритмов. Условно, в алгоритме Крускала сортируются рёбра по возрастанию и жадно выбирается каждое следующее ребро, начиная от самого малого по весу, с условием, что не образуется цикл. Алгоритм Прима можно начинать из любой точки, но он также жадно выбирает на каждом шаге ребро с минимальным весом. При этом рассматривается любое ребро, которое инцидентно любой вершине дерева, но ещё не вошло в дерево, и которое не образует цикл.