2004-gre-cs-practice-book.pdf/Q37

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

Вопрос: Q37-4c9f66

Какая из следующих задач может быть решена с помощью стандартного жадного алгоритма?

1. Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер.
2. Нахождение максимальной клики в неориентированном графе.
3. Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер.

Ответы

• Правильный ответ: Только 1
• Только 2
• Только 3
• 1 и 2
• 1, 2, 3

Объяснение

• MST ищется жадно, да.
• клика — NPC
• максимальный поток — полиномиальна, форд=фалкерсон (жадных эвристик неизвестно, интересный вопрос — как доказать, что их не может быть? Класс ?).

Исходники — вопрос 37 на 28 странице книги «2004-gre-cs-practice-book.pdf»

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

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

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