2011-gre-cs-practice-book.pdf/Q61 — различия между версиями
Материал из DISCOPAL
| Строка 27: | Строка 27: | ||
{{question-ok|}} | {{question-ok|}} | ||
| − | {{ | + | {{checkme|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:56, 11 января 2025 (UTC)}} |
Версия 20:56, 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 укладываются в .
Решено: Nikitashapovalov 20:56, 11 января 2025 (UTC)