Жадность, из-за отсутствия лучшего слова, это хорошо. Одной из первых алгоритмических парадигм, изучаемых в курсе вводных алгоритмов, является жадный подход . Жадный подход приводит к простым и интуитивно понятным алгоритмам для многих задач в P. Более интересно, что для некоторых NP-трудных задач...
ОК, это может показаться домашним заданием, и в некотором смысле это так. В качестве домашнего задания в классе алгоритмов для студентов я дал следующую классику: Для заданного неориентированного графа приведем алгоритм, который находит разрез такой, что , где - количество ребер, пересекающих...
Исходя из учебника Введение в алгоритмы , корректность жадного алгоритма требует, чтобы задача имела два свойства: жадный выбор собственности оптимальная подструктура Легко придумать контрпримеры, для которых жадное решение не удается из-за отсутствия свойства жадного выбора, например, проблема...
Недавно я узнал о гипотезе Жадности о самой короткой проблеме суперструн . В этой задаче нам дан набор строк и мы хотим найти самую короткую суперструну то есть такую, чтобы каждая как подстрока .s1,…,sns1,…,sns_1,\dots, s_n ssssisis_isss Эта задача является NP-трудной, и после длинной серии работ...
Хорошо известно , что для каждого матроидов и любой весовой функции , то выходит в алгоритм , которая возвращает максимальный вес основы . Итак, верно ли обратное направление? То есть, если есть какой-то жадный алгоритм, то должна быть и некоторая структура матроида.MMMвесwwGreedyBasis (M, ш...
Жадность - это неформальный термин, но может быть (не уверен, поэтому я и спрашиваю), что для определенных задач можно сформулировать жадность математически и, таким образом, доказать, что не существует оптимального алгоритма жадности. Это...