Всем привет! Делаю систему по оценке персонала. Что-то вроде методики 360 градусов. Есть следующие сущности: подразделение, должность и персона.
Существуют определенные правила, кто и кого может оценивать. Например: Директор организации может оценивать своего заместителя, заместитель может -> директора, начальник отдела может оценивать своих подчиненных, начальник отдела может оценивать других начальников отдела, сотрудники могут оценивать своих коллег по отделу, сотрудники могут оценивать своих коллег со смежного отдела. Т.е. приведенные выше правила не привязаны к конкретному человеку, а только к его должности.
Нужно составить список, кто кого оценивает так, чтобы каждого сотрудника оценили ровно 5 человек.
Мне пришла в голову мысль, что эту задачу можно решить с помощью теории графов. Если все правила переложить на конкретных сотрудников, то можем получить пары, кто кого может оценивать.
Т.е. можно представить, что персона это вершина, а ориентированное ребро показывает, кто кого оценивает.
Как составить такой граф, чтобы из каждого вершины выходило равно 5 ребер?
Можете подсказать в каком направлении копать? Спасибо!
Очевидный поток: раздвоить каждого человека(на "оцениваемого" и "оценщика"), пустить всевозможные ребра из одних в другие, ну и заодно ребра из истока в оценщики и из оцениваемых в сток.
Точно задача с работы, а не с текущего контеста? Больно уж алгоритмичность очевидна.
Спасибо за ответ! С потоками еще не работал, поэтому не предсталяю как использовать потоки для построения регулярного графа (случайного). Можете посоветовать какую-нибудь задачу с разбором на эту тему?
http://e-maxx.ru/algo/ здесь Вы найдете примеры задач на потоки с примерами и достаточно хорошей теорией алгоритмов решения данных задач
Просмотрел алгоритмы, но не нашел ничего подходящего. В основном алгоритмы на максимумы и минимумы, а мне как ответ нужно получить список ребер. Эту задачу можно рассматривать как обобщенную задачу о назначениях. Думал симплекс-методом решить, но справиться ли он при кол-ве сотрудников 200 человек. Последний вариант: это провести все доступные ребра, и попробовать отсеять избыточные. Но в таком случае, некоторые сотрудники сделают оценку более 5 раз.
Алгоритм поиска максимального потока состоит в его построении. Поэтому как промежуточный результат будет получен список ребер.
Погуглите задачи на минимальный разрез (находится по остаточной сети после построения максимального потока). Вам в даном случае по рёбрам разреза нужно построить свой граф. Т.е. сначала строите "полный" граф как сказал JKeeJ1e30, затем находите максимальный поток, и по рёбрам минимального разреза строите свой граф с пятью оценками.