나는 학부모 - 교사 면담 일정 계획 프로그램을 작성했습니다. 교장은 학부모가 영국 과 수학 교사를 동시에 방문 할 수있는 3 가지 날짜 시간을 선택하기를 원합니다.이 최적의 스케줄 작업 NPC입니까?
모든 학부모가 3 회의 datetimes를 선택하면 가장 많은 학부모가 교사와 만날 수 있도록 학부모 - 교사 면담 일정을 짜는 최적의 방법을 찾아야합니다.
(시간 갈등과 회의에서 할 수없는 수학 선생님이있는 경우, 부모는 영어 선생님과 만날 예정)
나는, NP 형 문제에 대해 잘 모르지만 때 나는 "최적"과 "일정"을 함께 듣고, 나는 궁금해하기 시작했다 ...
나는 이미 교장에게 그렇게 할 수는 없지만 그것이 NP 완성인지를 알고 싶었다. 그것이 경우에, 가정이 있습니다 :
에서 선택하는
글쎄, 나는 다른 시나리오를 시도 할 수있는 질문과 시뮬레이션에 대한 부분적인 대답을 가지고있다. 여기 내 작업 (그러나 가변) 가정은 다음과 같습니다
내 2 차 최적화도 모든 부모의 첫 번째 선택은 하나 개의 세션에서 11 부모의 최대 수용 할 수 첫 번째 패스로 걷어하지 않았다. 이 결과는 평균 부모 그룹이 ~ 3 인 시간대의 약 절반에 참석해야하는 교사에게 적합하지 않았다.
표현 된 관심사를 감안할 때 약 125 줄이므로 코드를 사용할 수 있습니다.
그럼 NP인지 아닌지 찾았습니까? 그리고 시간이 있다면 코드를 어딘가에 게시하십시오. 나는 그것을보고 싶다! – Matt
그것은 O (n)이었고 0.3 초가 지나면 해결되지 않는 시나리오를 만드는 데 소비되었습니다. 상황을 더 잘 모델링하기 위해 어떤 가정 (예 : 12 세 세션 참석 교사, 영어에서 수학 교사로의 단일 매핑)을 완화해야하는지 알려주세요. "재미있는"코드를 게시하는 것을 선호합니다. 이제는 다소 지루합니다. – msw
수학 교사에게 영어를 1 : 1로 매핑하는 것이 가장 비현실적입니다. ~ 12 세션에 참석하는 교사가 허용됩니다. – Matt
사용할 수있는 제한된 시간 (25)을 감안할 때, 각 datetime에 가능한 교사의 조합을 2^20으로 조율해야만하는 경우에도 특히 문제가 될 필요는 없습니다. 최적의 솔루션을 얻는 것은 나에게 NP로 보일 수 있습니다. 그러나 이것은 몇 년이 아니라 몇 분 안에 계산 될 수 있습니다. –
내 직감은 이것이 NP 하드이지만 합리적인 시간에 계산할 수 있다는 것입니다. 이것은 일대일 회의가 아니라고 가정 할 경우 분명히 해결책이 없습니다. 이것은 재미있는 퍼즐입니다. 내가 그걸 가지고 바이올린을 치기 시작했을 가능성이 더 큽니다. – msw
세션에 참석하는 학부모의 수 (시간차)가 공간 제약이있는 것은 아니며 현실 세계에서는 그렇지 않을 수 있습니다. 나는 또한 내가 기대하는 선호 세션의 매우 비 균일 한 선택을 기대하고있다. – msw