Минимальное количество камер, необходимое для покрытия всех узлов на графике

Question

Я столкнулся с проблемой в leetcode под названием "Binary Tree Camera".

Мне было интересно, как решить эту похожую проблему: -

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

Answer 1

Эта задача называется минимальным Доминирующим множеством и является NP-сложной для общего случая графа. Существуют алгоритмы, которые подходят к этой проблеме путем аппроксимации, параметризации или ограничения класса графов. См. Ссылку на Википедию.

Answer 2

Это проблема покрытия множества , для которой существует много известных алгоритмов. Чтобы смоделировать это как пример проблемы набора покрытия, сопоставьте каждый узел с набором узлов, которые будет покрывать камера в этом узле. Первоначальная проблема выбора наименьшего количества узлов эквивалентна выбору наименьшего количества этих наборов.

В общем, это проблема «NP Hard», то есть не существует известного алгоритма, который всегда дает минимумпокрытие, а также хорошо масштабируется для крупных случаев проблемы. Поскольку проблема требует минимума, эвристический алгоритм не подходит, поэтому вам нужно выполнить что-то вроде обратного поиска .