Алгоритм Форда Фулкерсона Java

Мне нужна помощь в реализации эффективного алгоритма для следующей задачи планирования.

Завтра в больницу придут n пациенты для медицинского осмотра, но свободны только 2 врача (врач А и врач Б). Каждое медицинское обследование занимает 1 временной интервал для врача. Если возможно, мне нужно распределить этих n пациентов по n временным интервалам, используя только 1 врача. Если 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

Если я получаю ввод, например:

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

Тогда мне нужно будет назначить обоих врачей, так как P3 и P4 имеют конфликты доступности. выход:

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

Какой самый эффективный алгоритм для такой задачи? Как я могу реализовать алгоритм Форда Фулкерсона для этого?

Что я сделал до сих пор.

Я пытался сохранить доступные временные интервалы каждого пациента в отдельных массивах.

Отсортируйте массивы по длине. Сначала назначьте пациента с наименьшим доступным временным интервалом.

После назначения пациента удалите этот временной интервал в остальных массивах и снова отсортируйте массивы по длине.

Повторяйте этот процесс, пока не будут назначены все пациенты.


java algorithm ford-fulkerson
person Ryan    schedule 11.10.2014    source источник
comment
У меня есть идея, как это сделать, но я не знаю, будет ли это эффективно по сравнению с вашим кодом. Можете ли вы показать свой код?   -  person user562    schedule 11.10.2014
comment
Интересно, как бы вы назначили пациенту наименьшее количество доступных временных интервалов, если у нее есть более 1 доступного временного интервала.   -  person user58697    schedule 11.10.2014

Ответы (1)


arrow_upward
1
arrow_downward

Давайте рассмотрим эту проблему глубже. У нас есть набор пациентов, набор временных интервалов и некоторые связи между ними (наличие пациентов в данный момент времени). Это выглядит точно так же, как задача максимального соответствия в двудольном графе! Таким образом, первый набор вершин должен соответствовать пациентам (одна вершина на одного пациента), второй набор должен соответствовать временным интервалам (по одной вершине на каждый временной интервал). Ребро между вершиной из первого набора и вершиной из второго набора существует тогда и только тогда, когда пациент доступен в этот временной интервал. Если максимальный размер совпадения равен количеству пациентов, то достаточно одного врача, иначе нет.

Как решить эту проблему для 2 врачей? Почти так же. Мы по-прежнему можем построить двудольный граф для пациентов и временных интервалов, но теперь у нас есть 2 вершины во втором наборе для каждого временного интервала (одна для первого врача и вторая для другого). Края добавляются таким же образом. И снова все, что нам нужно проверить, это то, что максимальный размер совпадения равен количеству пациентов.

Чтобы найти максимальное соответствие в двудольном графе, вы можете использовать алгоритм Диника или Хопкрофта-Карпа, чтобы получить временную сложность O(M * sqrt(N)), где N — количество вершин, а M — количество ребер.

person kraskevich    schedule 11.10.2014