NP-полная задача

Дана электрическая сеть, представляющая из себя множество электрогенераторов, между которыми протянуты провода. Провод имеет ток, если работает хотя бы один генератор на одном из концов провода. Найти минимальное по размеру множество генераторов, которые потребуется включить, чтобы обеспечить током всю сеть. Для решения задачи из варианта требуется разработать два алгоритма: алгоритм, решающий задачу методом полного перебора/комбинаторного поиска и гарантированно находящий оптимальное решение задачи. С большой вероятностью обладает экспоненциальной временной сложностью алгоритм, находящий субоптимальное (приближенное) решение задачи, но обладающий полиномиальной временной сложностью. Для поиска конкретного алгоритма требуется изучить наработки по соответствующей NP-полной задаче. Классы алгоритмов для поиска субоптимального решения: жадные алгоритмы, рандомизированные алгоритмы, эвристические алгоритмы и т.д.