2011-gre-cs-practice-book.pdf/Q61

Ссылки сюда (1) →

Вопрос: 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)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.