Ford Fulkerson 알고리즘 Java

Question

다음 예약 문제에 효율적인 알고리즘을 구현하는 데 도움이 필요합니다.

내일 건강 검진을 위해 병원에 오는 환자는 n입니다. 단, 의사는 2 명 (의사 A와 B)입니다. 각 건강 검진에는 의사에게 1 시간이 소요됩니다. 가능한 경우 의사 1 명만 사용하여 n 명의 환자를 n 시간 슬롯에 할당해야합니다. 1 명의 의사가 가능하지 않은 경우 2 명의 의사 만 사용할 수 있으므로 최대 2 명의 의사를 지정할 수 있습니다. 2 명의 의사가 아직 충분하지 않은 경우. 간단히 출력 impossible

나는 환자의 입수 가능성을 입력으로하고 있습니다. 예를 들어, 5 명의 환자가 있고, 환자 1은 시간 슬롯 1,2,5에서만 사용 가능하고 환자 2는 시간 슬롯 3, 4에서 사용 가능하며 환자 3은 시간 슬롯 1 ...에서 사용할 수 있습니다 ...... 등등 .

P1: 1 2 5 
P2: 3 4 
P3: 1 
P4: 2 
P5: 3 5 

이 경우 작업을 수행하려면 의사가 1 명이면됩니다. 출력

P1: Time slot 5 - Doc A 
P2: Time slot 4 - Doc A 
P3: Time slot 1 - Doc A 
P4: Time slot 2 - Doc A 
P5: Time slot 3 - Doc A 

내가 얻을 경우처럼 입력 : P3와 P4 가용성에 충돌이 있기 때문에

P1: 1 2 5 
P2: 3 4 
P3: 2 
P4: 2 
P5: 3 5 

가 그럼 난 둘 다 의사를 할당해야합니다. 출력 :

P1: Time slot 5 - Doc A 
P2: Time slot 4 - Doc A 
P3: Time slot 2 - Doc A 
P4: Time slot 2 - Doc B 
P5: Time slot 3 - Doc A 

이 같은 문제에 대한 가장 효율적인 알고리즘이 무엇입니까? Ford Fulkerson 알고리즘을 어떻게 구현할 수 있습니까?

지금까지 내가 한 것.

각 환자의 사용 가능한 시간 슬롯을 별도의 어레이에 저장하려고했습니다.

길이별로 정렬하십시오. 가장 가용 한 시간 슬롯을 먼저 환자에게 할당하십시오.

환자가 지정되면 나머지 배열에서이 시간대를 삭제하고 배열을 길이별로 다시 정렬하십시오.

모든 환자가 할당 될 때까지이 과정을 반복하십시오.

Answer 1

이 문제를 자세히 살펴 보겠습니다. 우리는 세트 환자, 시간 슬롯 및 그 사이의 연결 (주어진 시간에 환자의 가용성)을 가지고 있습니다. 이진 그래프에서 최대 일치 문제와 정확히 같습니다! 따라서 첫 번째 꼭지점 세트는 환자 (한 환자 당 하나의 꼭지점)에 해당해야하며 두 번째 세트는 시간 슬롯 (각 시간 슬롯 당 하나의 꼭지점)에 해당해야합니다. 환자가이 시간 슬롯에서 사용 가능한 경우에만 첫 번째 세트의 정점과 두 번째 세트의 정점 사이에 모서리가 있습니다. 최대 일치 크기가 환자 수와 같으면 의사 한 명이면 충분합니다.

2 명의 의사에게이 문제를 해결하는 방법은 무엇입니까? 거의 같은 방식으로. 우리는 여전히 환자와 시간 슬롯을위한 bipartite 그래프를 만들 수 있습니다. 그러나 이제는 각 시간 슬롯에 대해 두 번째 세트에 2 개의 꼭지점이 있습니다 (첫 번째 의사는 하나, 다른 하나는 두 번째). 가장자리도 같은 방식으로 추가됩니다. 다시 확인해야 할 것은 최대 일치 크기가 환자 수와 같습니다.

가 된 그래프에서 최대의 일치를 찾으려면 N 정점의 수와 M는 모서리의 수입니다 O(M * sqrt(N)) 시간 복잡도를 얻을 수 Dinic 또는 Hopcroft - 카프 알고리즘을 사용할 수 있습니다.