Вариант 369818314.
Какова точность, гарантируемая жадным алгоритмом в задаче о покрытии?
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке полиномиальность в среднем доказана для следующего распределения входных данных:
Цикл, проходящий через все ребра графа по одному разу, называется
С какой точностью работает «чисто» жадный алгоритм для задачи о рюкзаке («хватать предметы по убыванию удельной стоимости, пока не кончится место в рюкзаке»)?
Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:
Формулировка (в виде ЦП) какой задачи приведена ниже:
Как называется задача оптимизации со следующей формулировкой:
Для чего применяется «метод условных вероятностей»:
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм…
Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется: