헝가리어 알고리즘 및 다중 요인

Question

여러 행사에 사람들을 배정해야 하는 상황이 생겼습니다.가격만 요인으로 삼는다면 괜찮겠지만, 거기에는 여러 가지 요인이 작용합니다.

첫째, 배경지식입니다.이것은 어떤 이유로 병원에 입원한 어린이들을 위한 이야기 ​​시간을 장려하는 비영리 단체를 위한 것입니다. 그래서 그들은 그렇게 하기 위해 자원 봉사에 의존합니다.따라서 그들은 사람들의 선의에 의존하기 때문에 사람들이 할 수 있거나 원하는 만큼 많은 일을 제공합니다. 이는 다음과 같이 다양합니다.

• 어떤 사람은 아침에만 할 수 있고 어떤 사람은 오후에만 할 수 있습니다.
• 월요일과 목요일에만 갈 수 있는 사람도 있고, 8월이나 12월에 갈 수 없는 사람도 있습니다.
• 어떤 사람들은 한 달에 한 번만 갈 수 있고 다른 사람들은 4번만 갈 수 있습니다. (심지어 다른 사람들은 경험이 많고 한 달에 10번 갈 수 있기 때문에 이러한 조치에서 "우선순위"가 부여됩니다)

그래서 처음 두 가지를 알아 냈습니다.헝가리 알고리즘은 가격에 관한 것이기 때문에 그들이 갈 수 없는 시간에 대해서는 어리석게도 높은 가격을 주겠습니다.그러나 다른 사람들은 어떻게 하시겠습니까?

나는 그들에게 일종의 점수를 주려고 생각했습니다.다음과 같은 내용이 있습니다.한 달에 한 번 이 작업을 수행할 수 있는 사람의 비용은 1000포인트 정도입니다.한 달에 10번 갈 수 있다면 그 사람의 비용은 100포인트(1000을 10으로 나눈 값)입니다.또한 이를 분배하는 방법은 다음과 같이 별도의 작업이 수행될 때마다 가격을 높이는 것입니다(선택된 사람들은 관련 비용에 * 표시가 있습니다).

첫 번째 반복

         | August 1st 2009
Person A | 1000
Person B | 500 *

두 번째 반복

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

이것이 모든 사람들에게 그에 따라 분배하는 방법이 될 것이며, 이것을 여러 번 할 수 있는 사람들에게 더 많은 우선권을 주는 방법일 것입니다.

당신은 어떻게 생각하며 어떻게 하시겠습니까?

Answer 1

이는 일정/최적화 문제이므로 핵심 질문은 "최대화하려는 수량은 얼마입니까?"입니다.각 자원봉사자의 시간표 제한에 따라 충돌 없이 모든 자원봉사자의 총 작업 시간을 최대화하려고 하는 것 같습니다.경험이 많은 자원봉사자를 우선시한다고 말씀하셨는데, '일부 자원봉사자는 우선의 다른 사람보다."

그렇다면 이것은 고전이다 이분 매칭 문제.예를 들어 참조하십시오.498페이지 중 알고리즘 설계 매뉴얼 (2판), 스티븐 스키에나 저.기본 접근 방식은 자원 봉사자 세트와 채우려는 시간 슬롯 세트를 모두 나타내는 정점으로 그래프를 구성하는 것입니다.Edge는 자원봉사자를 유효한 시간 슬롯에 연결합니다.그러면 최적의 솔루션은 자원 봉사 또는 시간 슬롯이 반복되지 않는 가능한 가장 큰 에지 세트입니다.이것은 일치입니다.

자원봉사자 중 일부는 두 개 이상의 슬롯을 수행할 수 있습니다.이는 해당 자원 정점을 여러 번 복제하여 모델링할 수 있습니다.

자원봉사자의 우선순위 지정을 구현하려는 경우 각 에지에 가중치를 효과적으로 추가하여 해당 작업에 대한 해당 자원봉사자의 경험을 모델링합니다.이 경우에는 생각한 대로 헝가리 알고리즘과 같은 것이 필요합니다.이것이 없이도 벗어날 수 있다면 문제를 동등한 것으로 변환할 수 있습니다. 흐름 그래프, 네트워크 흐름 알고리즘을 적용합니다.다음은 한 가지 예입니다. 가중치 및 비가중 일치를 모두 구현하는 코드.

다른 대안을 포함한 더 자세한 내용과 구현에 대한 더 많은 링크를 원한다면 알고리즘 설계 매뉴얼의 사본을 구하는 것이 좋습니다. 이는 놀라울 정도로 명확하고 실용적인 참고 자료입니다.