2004-gre-cs-practice-book.pdf/Q37 — различия между версиями

Текущая версия на 21:52, 14 декабря 2024

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

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

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

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

Версия 21:51, 14 декабря 2024 (просмотреть исходный код) StasFomin (обсуждение \| вклад) ← Предыдущая правка		Текущая версия на 21:52, 14 декабря 2024 (просмотреть исходный код) StasFomin (обсуждение \| вклад)
Строка 22:		Строка 22:

	{{question-ok\|[[Участник:StasFomin\|StasFomin]] 21:51, 14 декабря 2024 (UTC)}}		{{question-ok\|[[Участник:StasFomin\|StasFomin]] 21:51, 14 декабря 2024 (UTC)}}
		+
		+	[[Категория:Greedy]]