집합덮개문제와 시설 결정 문제

유치원에서는 특정 선생님이 다수의 학생을 커버한다. 4명의 선생이 있고 40명의 학생이 있으면 대충 10명씩 4반으로 찢어질 것이다. 하지만 10명의 학생이 한명의 선생에게 보살핌 받는 것은 불안감을 유발할 수 있다. 때문에 한명당 1명 이상의 선생을 배정하는 방식이 사용될 수 있다. 이것을 집합 덮개 문제 (set covering problem)이라고 한다. 오늘은 이에 대해 알아보자. 집합 덮개 문제 집합 덮개 문제는 실제 상황에서 한정된 자원이 있고, 자원을 요구하는 위치가 많이 존재하기 때문이다. 각 위치(station, center)는 각각의 다른 고정비용이 존재하며, 자원을 운송하는 비용도 존재할 것이다. 이 때 자원을 보내는 곳을 집합 A, 받는 곳을 집합 B라고 하자. 전자는 유치원 선생, 후자는 유치원 아이들이 될 것이다. 집합 덮개 문제는 집합 B는 각각 적절한 집합 A에 의해 덮어져야한다. 목표값은 일반적으로 집합 A의 최소화이다. 또한 커버(cover)는 덮는다...

원문링크 : 집합덮개문제와 시설 결정 문제