Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S

cs.stackexchange https://cs.stackexchange.com/questions/67634

  •  04-11-2019
  •  | 
  •  

문제

Given a universal set of elements $\mathbf{U} = \{a_1, a_2, .., a_n\}$, a set $\mathbf{R} = \{a_i\} \subset \mathbf{U}$ where $i ϵ \{1, .., n\}$, a set $\mathbf{P} = \{R_1, .., R_m\}$ and a set $\mathbf{C} = \{P_1, P_2, .., P_l\}$, how do I go about finding a set $\mathbf{S} = \{a_1, .., a_n\} \subset \mathbf{U}$ such that at least one set $\mathbf{R}$ from each $\mathbf{P}$ is satisfied and such that the size of $\mathbf{S}$ minimal? I consider the set $\mathbf{R}$ to be satisfied by $\mathbf{S}$ if $\mathbf{R} \subseteq \mathbf{S}$.

This seems similar to set cover problem, but I am not sure how I can approach this.

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top