최소 거리

9 명의 학생과 3 개의 학교가 있습니다. 모든 학교는 최대 3 명의 학생으로 할당 될 수 있습니다. 모든 학교와 학생은 그 좌표를 갖습니다. 이제부터 모든 거리의 합계가 학생은 학교에 최소한이어야합니다.최소 거리

인터뷰에서이 질문을 받았습니다. 누구든지이 알고리즘을 제안 할 수 있습니까?

처음에는 욕심 많은 접근 방식을 시도했지만 작동하지 않습니다. 그런 다음 동적 프로그래밍 방식을 적용했지만 최적의 하위 구조를 찾을 수 없었습니다.

2012-11-12 Avinash

문제는 – RobAu

당신이 이분 그래프 매칭에 좋은 독서 자료를 제시 할 수 일치 된 그래프라고합니다. – Avinash

이 책은 훌륭하지만, 너무 이론적이다 : [MD Plummer, L. Lovász의 "Matching Theory"] (http://books.google.ru/books/about/Matching_Theory.html?id=mycZP-J344wC&redir_esc=y) . –

모든 학교에는 3 곳, 3 곳에는 9 곳이 있습니다. 그리고 9 개 장소와 9 개 지역 학생이 가장 잘 어울리는 곳을 찾아야합니다.

이 할당 문제는 Hungarian algorithm으로 해결할 수 있습니다.

출처

2012-11-12 18:25:48

문제 크기가 충분히 작기 때문에 철저한 검색은 어떨까요?

첫 번째 학교는 9 명 중 3 명을 선택합니다.
두 번째 학교는 남아있는 6 명 중 3 명을 선택합니다.
마지막으로 남아있는 3 명의 학생들이 마지막으로 학교에 갇히게됩니다.

은 그래서 손 (9 choose 3) * (6 choose 3) = 1680

출처

2012-11-12 18:44:20

효율적인 솔루션을 찾고 있습니다. – Avinash

답변

관련 문제