계획 도구의 알고리즘

Question

저는 지역 학교를위한 간단한 계획 도구 역할을 해야하는 작은 소프트웨어 응용 프로그램을 작성하고 있습니다. 해결해야 할 '문제'는 상당히 기본적입니다. 즉, 교사는 모든 자녀의 부모와 대화해야합니다. 그러나 일부 어린이들은 물론 다른 그룹의 형제 자매를 가지고 있기 때문에,이 대화는 각자 옆에 예약되어야합니다. 상황을 피하기 위해 오후 6시에 대화를하고 오후 10시에 다른 말을하는 것을 피하십시오. 따라서 간단히 말해서, 모음이 주어졌습니다 N 일부 어린이가 한 명 이상의 형제 또는 자매가있는 어린이는이 아이들의 모든 대화가 서로 옆에 계획되는 일정을 만듭니다.

이제 문제는 매우 쉽게 해결 될 수 있지만, 다른 한편으로는 이것이 매우 복잡한 문제 일 수 있다고 생각합니다. 우아하게. 하지만 내가 맞아? 거기가 있습니까? 나는 보았다 헝가리 인 알로리즘이지만이 특정 문제에는 적용되지 않습니다.

편집 : 나는 모든 대화에 같은 시간이 걸린다는 것을 언급하는 것을 잊었다.

감사!

Answer 1

나는 그것이 매우 쉽다고 생각합니다.

첫 번째 그룹은 부모를 공유하기 때문에 함께 속한 아이들을 그룹화합니다. 그룹 내부의 어린이를 연속적으로 예약하고 나머지는 무작위로 예약하십시오.

그것을 추상화하고 문제를 더 쉽게 만들 수있는 또 다른 방법은 부모의 관점에서보고 형제 자매를 "아이"로보고 더 많은 시간을주는 것입니다. 그런 다음 부모님을 무작위로 예약 할 수 있지만 일부는 더 많은 시간이 필요합니다 (childeren이 여러 개 있기 때문에).

Answer 2

한 가지 접근 방식은 선언적 제약 언어로 문제를 정의한 다음 문제를 해결하기 위해 DBE를 사용합니다. 마지막 으로이 일을했을 때 사용했습니다 식, 이것은 문제 공간을 제약으로 정의한 다음 해당 제약 조건을 충족시키는 허용 가능한 값을 찾도록하는 멋진 작은 언어입니다.

예를 들어, 나는 당신이 두 가지 클래스의 제약을 가지고 있다고 생각합니다.

1. 교사는 한 번에 하나의 회의 만있을 수 있습니다.
2. 같은 가족의 모든 학생들은 연속 슬롯이 있어야합니다.

일식에서이를 정의하면 요구 사항을 충족하는 각 학생의 값을 계산합니다. 이런 식으로 가면 필요한대로 제약 조건을 쉽게 추가 할 수 있습니다. 예를 들어, 슬롯 y에게는 가르침을 이용할 수 없거나 교사가 행정 업무를 수행해야한다고 말하기 쉽습니다.

Answer 3

이 종류는 "배낭 알고리즘"유형의 문제처럼 느껴집니다. 가족 구성원을 함께 그룹화 한 다음 슬롯을 적절하게 채워야합니다.

Google "백팩 알고리즘"이라면 헤드 스핀과 좋은 코드 솔루션을 만들기에 충분한 쓰기가 표시됩니다.

Answer 4

각 활동에 각 활동에 시작 시간이 있고 종료 시간이있는 "활동"으로 축소 될 수 있다고 생각합니다. 컴퓨터 과학에서 연구 된 활동 선택 알고리즘을 사용할 수 있다고 생각합니다. 그것은 탐욕스러운 접근법을 기반으로하며 O (n)에서 해결할 수 있습니다 (여기서 n은 활동 수). 더 많은 정보를 찾을 수 있습니다 여기. 동일한 유형의 활동으로 형제/자매 문제를 줄일 수 있도록 여기서 사전 처리를해야 할 것입니다.