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 укладываются в .

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

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

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