Участник:StasFomin/A — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
showtotal=yes | showtotal=yes | ||
namespace=Main | namespace=Main | ||
| − | limit= | + | limit=139 |
order=creation desc | order=creation desc | ||
output=template | output=template | ||
Версия 20:39, 2 ноября 2021
Открытые задачи на «Dynamic Programming»
Всего страниц найдено: 1.
----
Вопрос: Q37-4c9f66
Какая из следующих задач может быть решена с помощью стандартного жадного алгоритма?
- Нахождение минимального остовного дерева в неориентированном графе с целыми положительными весами ребер.
- Нахождение максимальной клики в неориентированном графе.
- Нахождение максимального потока от узла-источника к узлу-приемнику в ориентированном графе с целыми положительными значениями пропускной способности ребер.
Ответы
- Правильный ответ: Только 1
- Только 2
- Только 3
- 1 и 2
- 1, 2, 3
Объяснение
- MST ищется жадно, да.
- клика — NPC
- максимальный поток — полиномиальна, форд=фалкерсон (жадных эвристик неизвестно, интересный вопрос — как доказать, что их не может быть? Класс
NC_0 ?).
Исходники — вопрос 37 на 28 странице книги «2004-gre-cs-practice-book.pdf»