객실/시간 슬롯 일정 최적화

Question

사람들은 25 건의 강의 중 5 개를 미리 선택할 수 있습니다. 이 모든 강의는 5 개의 객실에서 5 개의 시간 슬롯으로 하루에 주어집니다. 청취자가 참석할 수있는 각 강의는 그녀를 조금 더 행복하게 만들고, 그가 선택한 각 강의는 참석할 수 없지만 (또 다른 선호하는 강의는 같은 시간 슬롯이기 때문에) 그를 조금 불행하게 만듭니다. 선호하는 강의 목록은 가중치가 없습니다 (적어도 등록자는 선호도를 주문하라는 지시를받지 않았지만, 더 쉽게 일을하면 첫 번째 선택이 가장 높은 우선 순위를 가지고 있다고 가정 할 수 있습니다. 해당 정보를 사용할 수 있습니다).
가능한 모든 일정을 시도하지 않고 전반적인 행복이나 근사치를 극대화하는 방법이 있습니까? Wikipedia에서 병원/거주자 문제에 대한 빈 스터브를 발견했습니다.

대학 입학 문제라고도하는 병원/거주자 문제는 "여성"이 하나 이상의 "남자"에서 "제안"을 받아 들일 수 있다는 점에서 안정적인 결혼 문제와 다릅니다 (예 : 병원은 여러 거주자를 데려 갈 수 있습니다. 대학은 한 명 이상의 학생 수업을 수업 할 수 있습니다). 병원/거주자 문제를 해결하기위한 알고리즘은 병원 지향적 (여성 최적) 또는 거주 지향적 (남성-최적) 일 수 있습니다.

Answer 1

그것은 당신의 요구 사항에 대해 과잉 일 수 있지만, 당신은 유전자 알고리즘, Mike Swanson 's에 설명 된대로 유전자 알고리즘을 사용한 PDC 2008 컨퍼런스 일정.

그는 32 분의 인터뷰 에서이 기술에 대해 논의합니다 채널 9 자격이 있습니다 알고리즘 및 데이터 구조 : Mike Swanson- 유전자 세션 스케줄러.

Answer 2

나는 당신이 모든 정보를 제공했다고 생각하지 않습니다. 5 개의 시간 슬롯과 5 개의 객실이있는 총 25 개의 강의가있는 경우 (설명되지 않은대로 중복이 없다고 가정) 주어진 참석자가 모든 슬롯에서 항상 4 개의 강의를 놓칠 것입니다. 강의에 대한 용량 제한을 제공하지 않았고 가중치가 무게가 없다고 말하면 참석자 (균등하게 또는 고르지 않게)에 참석하는 동일한 강의에 참석하는 모든 사람들 사이에 총 (또는 개인)의 행복에 차이가 없습니다. 5 개의 동시 강의.

Answer 3

이것은 병원/거주자 문제, 대학 입학 문제 또는 학생 프로젝트 할당 문제 (안정적인 결혼 문제의 모든 하위 집합)와 비슷합니다. 이와 같은 기존 알고리즘이 있습니다 이 하나, 이 두 번째, 이 세 번째. 당신은 또한 볼 수 있습니다 NMRP 알고리즘 노벨상이 우승하는 방법을 위해.