Набор ударов и обложка набора
Формально пусть H = (V, E) — гиперграф с множеством вершин V, множеством гиперребер E и некоторым количеством подмножеств Ci ⊆ V; i=1..n, то множество S ⊆ V называется множеством попаданий, если для всех Ci имеем Ci ∩ S = ∅. И мы называем это S a (минимальный набор попаданий), если он был наименьшим, насколько это возможно, то есть имел наименьший возможный размер |S| (количество узлов).
Алгоритм
Невзвешенный алгоритм
Un-weighted MHS (U all nodes, S all subsets)NHS <- Collection of sets that haven’t been hit yet (equals S) Sol <- Collection of nodes chosen as a solution while NHS not empty Then x <- choose node from {U/Sol} that hits maximum count of s ∈ NHS add x to Sol remove Sx (as defined earlier) from NHS Next Measure solution |Sol|
Взвешенный алгоритм
Weighted MHS (U all nodes, S all subsets)NHS <- Collection of sets that haven’t been hit yet (equals S) Sol <- Collection of nodes chosen as a solution while NHS not empty Then x <- choose node from {U/Sol} that has minimum cost = weight(x) / |Sx| add x to Sol remove Sx (as defined earlier) from NHS Next Measure solution |Sol| with cost Σ 𝑤𝑒𝑖𝑔ℎ𝑡(𝑥)∶𝑥∈𝑆𝑜𝑙
Вы можете найти реализацию java для проблемы здесь:
