Рейтинг Computr Sci. Какая группа наиболее избирательна?

Question

Существует четыре группы (вроде рабочих мест или колледжей): A, B, C и D. В проекте их будет намного больше, но сейчас давайте предположим четыре.Люди могут подать заявку на любое число этих групп, и группы могут отклонить или принять их.Человек 1 попал в A, B, C, D. Человек 2 попал в A, B, C, но не в D. Человек 3 попал в A, B, но не в C, D. Человек 4 попал в A, но не в B, C, D, E. Очевидно, что A наименее избирателен, за ним следуют B, C и, наконец, D. Как компьютер выясняет это, когда существует любое количество групп и любое количество людей, которые обращались к любому числугруппы?Заранее спасибо.

Answer 1

Общее решение этой проблемы может быть трудным, поскольку вы можете легко получить циклы (т.е. без транзитивности):

A accepts x and rejects y;
B accepts y and rejects z;
C accepts z and rejects x.

И учреждения могут быть не совсем сопоставимыми (т.е. без симметрии):

A accepts x and rejects y;
B accepts y and rejects x.

Один из методов, который вы можете использовать, - это сетевая модель.Пусть учреждения будут узлами.Добавьте направленную дугу весом w от узла A к узлу B, где w - количество кандидатов, которые были приняты в учреждение B и отклонены в учреждении A. Интуитивно, вес дуг, указывающих на менее отобранные школы, будетбольше.Таким образом, проблема в основном сводится к поиску стационарных потоков внутри и из узлов ... Учреждения вне компонента несопоставимы.

Извините, что не вдавались в подробности, но я надеюсь, что идеяясно.

Answer 2

Я бы использовал (по аналогии с колледжами) показатель приемлемости в качестве критерия для сортировки.

                    number of people accepted by group X
acceptance rate = -----------------------------------------
                    number of people applying to group X

Я не совсем уверен, что еще можно использоватьГруппа может рассматривать только тех людей, которые обращались к ней.