Алгоритмическое исключение на основе ролей объектов

Question

Существует пять возможных ролей, на которые может быть назначен только один человек, и он должен быть опытным. Роли фермер, программист, врач, продавец и футболист . Исключением должен быть результат / результат при отсутствии футболиста.

Что было бы чистым решением для решения этой «проблемы». Примеры в java были бы наиболее полезны, но псевдокод или подсказки также приветствуются.

Ввод:

+--------+--------------------------------------+
| Person |                Roles                 |
+--------+--------------------------------------+
|      1 | Farmer                               |
|      2 | Programmer, Doctor, Farmer           |
|      3 | Programmer, Doctor                   |
|      4 | Salesman, Farmer, Doctor, Programmer |
+--------+--------------------------------------+

+--------+--------------------+
| Person |       Roles        |
+--------+--------------------+
|      1 | Farmer             |
|      2 | Programmer, Doctor |
|      3 | Programmer, Doctor |
|      4 | Salesman           |
+--------+--------------------+

Редактировать:

То, что я пробовал до сих порэто две вещи, но определенно не гибкая, так как есть много возможностей:

1. Если у одного человека есть только одна роль, он автоматически получает роль. Проблема здесь заключается в том, что если несколько человек имеют одинаковую роль, и это их единственная роль.
2. Если два человека имеют две роли и имеют совершенно одинаковые роли, они оба получают назначенные роли. Проблема здесь в том, что более 2 человек играют все одинаковые роли.

Answer 1

Это хороший пример CSP (проблема удовлетворения ограничений) или COP (проблемы оптимизации ограничений), если вы не можете (или не должны) иметь идеальныйрезультат.

Я не буду писать для вас исходный код, но вот основная схема того, что вам нужно сделать:

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

На каждом уровне рекурсии:

1. Сортировать записи по количеству оставшихся назначаемых заданий
2. Для одного с наименьшим числомзаданий, выберите один из них, чтобы сохранить его, и удалите его из всех остальных.
3. Повторите эти шаги для этого задания
4. Если вы обнаружите несогласованность (например, у человека больше нет заданий), вернитесь назад (вернитесь врекурсивное дерево до момента, когда было выполнено критическое назначение), и попробуйте другое назначение из оставшихся доступных. Если нет другого возможного назначения, которое не привело бы к несогласованности, вернитесь назад еще
5. После того, как всем людям назначены роли, вы можете выйти. Если вы добираетесь до вершины дерева от обратного отслеживания, это означает, что решения не существует.

Все это выше предполагает, что у вас достаточно ролей для всех людей (например, каждый человек может сделать хотя бы одну вещьи вещь не такая, как все остальные). С некоторыми изменениями вы можете немного ослабить это условие (зависит от точного определения вашей проблемы)

Этот алгоритм может привести к нескольким решениям. Из вашего примера:

|      2 | Programmer, Doctor |
|      3 | Programmer, Doctor |

Есть (как минимум) 2 действительных результата. Person #1 будет Programmer и #3 a Doctor или наоборот

Есть много других способов ускорить это. Например, вы можете назначать роли людям в наиболее ограниченном порядке, что означает те, которые будут блокировать большинство других людей в первую очередь. Или между каждым шагом выполните проверку согласованности дуги , например AC-3