단일 강의용 좌석 배포 알고리즘을 구현하는 방법

Question

우리는 우리의 강의에서 약 1,000 석의 무료 석이 있으며 약 2,000 석 (각 500 명씩 4 곳씩 요구함)이 필요합니다.
나는 학생들이 1 ~ 4까지 우선 순위, 위시리스트를 만들고 블록 당 4 개 강의를 입력 할 수 있습니다 CakePHP를 가진 웹 애플리케이션을 개발하고 있어요, 이제 웹 프론트 엔드를

을 (이것은 다음의 MySQL 데이터베이스로 전환) 관리 작업 (강의 추가, 강사 추가 등)이 완료되었습니다. 남은 유일한 것은 배포 알고리즘을 작성하는 것입니다.

어떻게해야합니까? MySQL 스크립트가 유용하게 보이지만 mysql은 루프와 if-constructs와 관련하여 매우 친숙하지 않습니다. 그렇습니까?
어딘가에 데이터를 내보내고 다른 언어가 문제를 처리하게하는 것이 현명합니까?

편집 : dnagirl이 알고리즘에 대한 자세한 정보를 요청했습니다 : 알고리즘에 대한 비즈니스 규칙이 없습니다. 우리는 방금 적용한 규칙이있는 다른 대학의 다른 누군가로부터 기존 (매우 비싼) 앱을 채택했습니다.
은 그가하고있는 (내가 복제하는 것을 시도하고있는 무슨, 큰 당 학기 요금을 저장하는)이있다 : 모든 블록에 속하는

• 이벤트 (강의, 행사 등) (블록 예 : 4 또는 5 개의 다른 이벤트가있는 국제 정치)
• 학생들은 블록 당 최대 4 개의 이벤트를 우선 순위 1에서 4까지 신청할 수 있습니다.
• 알고리즘은 블록별로 작동합니다. 각 블록마다 순위에 따라 학생들을 여러 그룹으로 나눕니다. (순위는 "더 높을수록 좋습니다."보통 순위는 0에서 20까지입니다.)
• 순위가 가장 높은 학생 그룹에서 임의로 선택하십시오. 그에게 우선 순위 1로 선택한 행사에 자리를주십시오.이 행사가 가득 차면, 그가 우선 순위 2로 선택한 자리를 그에게주십시오;
• 이 순위를 가진 모든 학생이 자리를 잡을 때까지 다음 학생을 선택하고 동일하게하십시오. 그런 다음 다음 순위로 이동하고 모든 것을 다시하십시오. 이 블록이 끝나면 모든 블록이 완료 될 때까지 다음 블록으로 모든 것을 다시하십시오.

나는이 알고리즘이 최선의 해결책이 아니라는 것을 알고 있지만, 나는 지금 그것을 복제 할 것이며, 아마도 논리/가능성의 향상에 대해 연구 할 것이라고 생각했다.

Answer 1

당신은 아마 유전자 알고리즘의 일종을 원하는 :

• 강의를 통해 학생들의 임의의 분포를 만들기
• (성취 소원, 초과 예약 강의 등 처벌 높은 생산 점수)
점수를 계산
• 변경 (예 : 한 학생을 다른 강의로 이동). 점수가 올라가면 그대로 두거나 그렇지 않으면 거부합니다.
• 점수를 높이는 변화가 없을 때까지 반복하십시오 : 로컬 최소값을 찾았습니다
• 다른 로컬 미니 마를 찾기 위해 전체 것을 여러 번 반복하십시오. 그런 다음 최고 득점 솔루션으로 이동하십시오.

몇 가지 테스트를 실행하고 득점 가중치를 조정해야 제대로 할 수 있습니다.

MySQL은 실제로이 용도에 적합하지 않습니다. PHP로 이것을 더 잘 해결하고 한 번에 지속하십시오. 성능이 충분히 좋지 않다면 C++로 구현하는 것을 고려해 볼 수도 있습니다.하지만 PHP를 먼저 시도하고 충분히 빠르는지 확인하십시오. 2 초마다 이걸 실행하는 것과는 다릅니다.