2011-gre-cs-practice-book.pdf/Q61 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
== Вопрос: Q61-08c765 == | == Вопрос: Q61-08c765 == | ||
| − | Какие из следующих задач известны как решаемые за время <m>O(n^3)</m>? | + | Какие из следующих задач известны как решаемые за время <m>O(n^3)</m>? |
| − | + | ;I: Найти кратчайший путь от заданной начальной вершины до заданной конечной вершины в направленном графе с ''n'' вершинами и неотрицательными целочисленными весами на рёбрах. | |
| − | + | ;II: Найти самый длинный простой путь от заданной начальной вершины до заданной конечной вершины в направленном графе с ''n'' вершинами и неотрицательными целочисленными весами на рёбрах. | |
| − | + | ;III: Найти самый длинный путь от заданной начальной вершины до заданной конечной вершины в ациклическом направленном графе (DAG) с ''n'' вершинами и неотрицательными целочисленными весами на рёбрах. | |
=== Ответы === | === Ответы === | ||
| − | * Только I | + | * Только I |
| − | * I и II | + | * I и II |
| − | * Правильный ответ: I и III | + | * Правильный ответ: I и III |
| − | * II и III | + | * II и III |
| − | * I, II и III | + | * I, II и III |
| Строка 20: | Строка 20: | ||
Разберём каждое из утверждений: | Разберём каждое из утверждений: | ||
| − | + | ;I: (кратчайший путь): Можно решить за <m>O(n^3)</m> с помощью алгоритма Флойда-Уоршелла. | |
| − | + | ;II: (длиннейший простой путь): Задача NP-полная и не решается за полиномиальное время в общем случае. | |
| − | + | ;III: (длиннейший путь в DAG): Можно решить за <m>O(n^3)</m> с помощью динамического программирования или топологической сортировки. | |
Только I и III укладываются в <m>O(n^3)</m>. | Только I и III укладываются в <m>O(n^3)</m>. | ||
| − | {{question-ok | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 21:45, 11 января 2025 (UTC)}} |
| − | + | ||
| + | [[Категория:Алгоритмы на графах]] | ||
Текущая версия на 21:45, 11 января 2025
Вопрос: Q61-08c765
Какие из следующих задач известны как решаемые за время ?
- I
- Найти кратчайший путь от заданной начальной вершины до заданной конечной вершины в направленном графе с n вершинами и неотрицательными целочисленными весами на рёбрах.
- II
- Найти самый длинный простой путь от заданной начальной вершины до заданной конечной вершины в направленном графе с n вершинами и неотрицательными целочисленными весами на рёбрах.
- III
- Найти самый длинный путь от заданной начальной вершины до заданной конечной вершины в ациклическом направленном графе (DAG) с n вершинами и неотрицательными целочисленными весами на рёбрах.
Ответы
- Только I
- I и II
- Правильный ответ: I и III
- II и III
- I, II и III
Объяснение
Исходники — вопрос 61 на 43 странице книги «2011-gre-cs-practice-book.pdf»
Разберём каждое из утверждений:
- I
- (кратчайший путь): Можно решить за с помощью алгоритма Флойда-Уоршелла.
- II
- (длиннейший простой путь): Задача NP-полная и не решается за полиномиальное время в общем случае.
- III
- (длиннейший путь в DAG): Можно решить за с помощью динамического программирования или топологической сортировки.
Только I и III укладываются в .