학생이 실험실에 배정되어야하는 대학의 석사 프로그램에 실질적인 문제가 있습니다. 관련된 숫자는 그리 크지 않기 때문에 빠른 해결책을 찾는 것이 아니라 오히려 이해하기 쉬운 솔루션이므로 학생과 그룹 리더 모두 제안 된 페어링에 대한 정당성을 제공 할 수 있습니다.실험실과 학생 페어링
을 감안할 때 2 다음은 각 학생 S는 우선 순위에 따라 자신의 상위 3 개 실험실을 나열하고있다
S1 Li,Lj,Lk
S2 Lu,Lv,Lw
.
Sn
목록
. 따라서 학생 S1은 이상적으로 실험실 1에 속하는 것입니다. 그 연구소가 그를 원하지 않는다면, 그는 연구소 j에 있어야 할 것입니다.각 실험실들이 실험실에서 싶습니다 학생들을 나열
L1 Si,Sj,Sk
L2 Su,Sv,Sw,Sx,Sy
.
Lm
. 따라서 실험실 1은 먼저이 실험실을 선택한 경우 학생 1을 원합니다 (상위 3 개 선택 중 하나에서). 실험실은 같은 수의 학생을 선택할 수 있습니다.
각 학생은 단 하나의 실험실에만있을 수 있지만 각 실험실 일 수 있습니다.에는 0,1 명 이상의 학생이 있습니다.
목표는 모든 학생이 실험실에 배정되고 일치가 최대 으로 이어지는 일치도 (Si, Lj)를 생성하는 것입니다..
은 만족 점수는 직관적으로이 자신의 최선의 선택으로 많은 학생들과 실험실을 페어링 시도
Z=sum_{i=1..n}(sum_{j=1...m} (abs(i-j))
으로 정의된다.
배열을 정의 길이 L.의 할당 및 초기화라는 :
그래서 나는 다음과 같은 Z.에게
가능한 부분적인 해결책을 최소화하는 솔루션을 찾고이 최적화 알고리즘에 대한 알고리즘을한다 추구 그것은 모두 거짓
첫째로, 최초의 선택과 일치 (이 학생들에게
for each s in {S1,..,Sn}:
Assigned[s]=False
Assigned[s]=j
repeat until all(Assigned)==True:
for each s in S:
if RANK(Lj,s)==1:
Assigned[s]=j # i.e. pair student s with lab Lj
del(S,s) # delete s from the list S
함수 RANK을 폐기 Lj, s)는 실험실 j의 선호 학생 목록에있는 위치를 반환합니다. 학생 j가 실험실 j의 원하는 학생 목록에없는 경우 무한대를 반환합니다.
여기에서 또는이 방법은 어떤 도움이 많이 주시면 감사하겠습니다
점수 (Z)을 최소화 여부를 진행하는 방법을 잘 모르겠습니다.