이 문제는 현실 세계에서 생겼지 만 좀 더 일반적인 "교과서 같은"형식으로 번역했습니다. 나는 이것이 NP인지 의심 스럽지만, 특히 이름을 가지고 있는지 잘 알기에 관심이 있습니다. 처음 만날 수는 없기 때문에 잘 알려져 있습니다. ;-)이 문제는 NP이며 이름이 있습니까?
N 명의 손님이있는 potluck 파티가 있다고 상상해보십시오. 각 손님은 그/그녀의 "서명 요리"를 파티에 가져 오거나 가져올 수 없습니다. 각 손님은 다른 손님이 가져올지도 모르는 각각의 요리를 좋아하거나 싫어합니다. (그리고 그들은 옛 친구이기 때문에 미리 알고 있습니다!) 그러나 그들은 모두 자신의 요리를 좋아합니다.
모든 손님이 원하는대로 적어도 하나의 접시를 찾을 수 있다는 제약 조건을 만족시키는 최소 세트의 요리를 찾기 위해 기하 급수적 인 시간을 소비하지 않는 결정 론적 알고리즘이 있습니까? 나는 "가장 작다"고 말하지만 실제로는 여러 가지 해결책이있을 수 있습니다. 가능하다면 그것들을 모두 알고 싶습니다.
또는보다 추상적 인 방법으로 모든 요소가 0 또는 1이고 모든 대각선 요소가 1 인 정사각형 행렬을 상상해보십시오. 행의 최소 집합은 다음과 같습니다. 각 집합의 행에는 0이 없습니다. (행은 접시가되고, 열은 손님이 될 것이고, 1은 손님이 접시를 좋아한다는 것을 의미 할 것이고, 대각선 요소는 모두가 자신의 접시를 좋아하기 때문에 1이다.)
이것은 비 정사각형으로 일반화 될 수있다. 행렬 또는 대각선 = 1 규칙을 제거함으로써 (비록 후자가 항상 적어도 하나의 해가 있음을 보장하지만). 하지만 지금은 그런 경우는 신경 쓰지 않아요 ...
철저한 검색을 통해 해결할 수있는 프로그램이 이미 있으며 N 약 20 분 정도면 충분하지만 기하 급수적 인 시간이 필요합니다. 나는 신속한 답변을 위해, 나는 N.
추가
와우의 큰 값에 대해 좋은만큼 해결책을 찾기 위해 확률 적 알고리즘에 재발 할 수도 있습니다 덕분에 생각하고 있어요! "표지 설정", 내가 찾고 있던 이름입니다. :)
위대한 질문, 훌륭한 답변. –