|
|
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
Всем привет! Нужна помощь с алгоритмом. Нужно построить регулярны граф на 150 (200), где в каждую вершину входит 5 ребер и выходит 5 ребер. Как эта ситуация выглядит в жизни... Есть организация, в которой где-то 150 человек, нужно чтобы каждый человек оценил 5-х сотрудников. Также есть список кто кого может оценивать. Задачу можно представить в виде графа, где вершина - это сотрудник, а ребро - это кто кого оценивает. И нужно чтобы из вершины выходило 5 ребер и входило столько же. Есть какие-нибудь идей? Просматривал различные алгоритмы, но не нашел ничего подходящего. Уже подумываю создать граф со всеми допустимыми ребрами и отсечь избыточные. Но в этом случае некоторым сотрудникам прибавиться работы, т.к. они будут оценивать более 5 человек. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 10:13 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
nyquist, не совсем понимаю причем здесь графы, но вариант, который сходу приходит в голову: 1. Делаем 2 списка сотрудников - оценивающие, оцениваемые, для каждого списка выполняем шуфл. 2. Идем в цикле по 1му списку (оценивающих) и выдаем ему 5шт на оценку по порядку из второго списка, в случае если выпадает сам на себя, то пропуск, если конец списка, то выполняем переход к началу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 11:06 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
Я бы взял 0,1 матрицу 200х200 (размеры позволяют) и последовательно заполнял строчки, случайно выбирая 5 из 199 (нельзя оценивать себя) в начале, и из меньшего числа - далее, исключая столбцы, набравшие 5 единиц. Сложность заполнения - n 2 . Но тут еще накладываются ограничения на выборку в строке (список, кто кого может оценить), и задача может не иметь решения. Как вариант - обратно "включать" отключенные столбцы, если только в них есть требуемые связи ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 11:24 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
just_vladimirnyquist, не совсем понимаю причем здесь графы, но вариант, который сходу приходит в голову: 1. Делаем 2 списка сотрудников - оценивающие, оцениваемые, для каждого списка выполняем шуфл. 2. Идем в цикле по 1му списку (оценивающих) и выдаем ему 5шт на оценку по порядку из второго списка, в случае если выпадает сам на себя, то пропуск, если конец списка, то выполняем переход к началу. Этот алгоритм подходил бы, если бы каждый сотрудник мог оценивать любого сотрудника. Но в данном случае каждый сотрудник может оценивать только определенных сотрудников (от 5 до 199). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 13:24 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
ivanraЯ бы взял 0,1 матрицу 200х200 (размеры позволяют) и последовательно заполнял строчки, случайно выбирая 5 из 199 (нельзя оценивать себя) в начале, и из меньшего числа - далее, исключая столбцы, набравшие 5 единиц. Сложность заполнения - n 2 . Но тут еще накладываются ограничения на выборку в строке (список, кто кого может оценить), и задача может не иметь решения. Как вариант - обратно "включать" отключенные столбцы, если только в них есть требуемые связи Решение задачи можно представить в виде матрицы. Ответом была бы матрица, где сумма элементов по строкам и столбцам равна 5. Только в матрице будут значения: 0, 1 и #. 0 - не воспользовались ребром 1 - воспользовались ребром # - ребра не существует. Если случайно выбрать 5 из 199, то можем выбрать неоптимальный путь, который не приведет к решению А если полность перебирать 5 из 199, то это 199*198*197*196*195 и это только одна строчка, а их 200. Сейчас подумываю решить задачу симплекс-методом, но сомневаюсь что он осилит такие объемы вычислений. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 13:43 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
На матрице инцедентности проще решать задачу IMHO. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 14:01 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
nyquist, задача в любом случае может не иметь решения. Например, представьте, что списки составлены таким образом, что люди с номерами 2...200 могут оценить №1 и еще 4 случайных. В этом случае, первый номер будет оценен 199 раз. В случае с матрицей можно предложить 2 прохода - случайный выбор по строкам, как описано выше (с исключением "накопленных" столбцов), потом то же самое по столбцам. В результате некоторые участники будут оценивать / оцениваться более 5 раз, вплоть до вырожденных случаев (199) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 14:03 |
|
||
|
Случайный регулярный граф из 150 точек
|
|||
|---|---|---|---|
|
#18+
nyquistjust_vladimirnyquist, не совсем понимаю причем здесь графы, но вариант, который сходу приходит в голову: 1. Делаем 2 списка сотрудников - оценивающие, оцениваемые, для каждого списка выполняем шуфл. 2. Идем в цикле по 1му списку (оценивающих) и выдаем ему 5шт на оценку по порядку из второго списка, в случае если выпадает сам на себя, то пропуск, если конец списка, то выполняем переход к началу. Этот алгоритм подходил бы, если бы каждый сотрудник мог оценивать любого сотрудника. Но в данном случае каждый сотрудник может оценивать только определенных сотрудников (от 5 до 199). ок, пропустил в исходном посте это ограничение, тогда жадный алгоритм, ну и правило отбора наоборот: 1. Идем по спискам сопоставления и считаем для каждого из сотрудников то, сколько человек его может оценить и скольких он может оценить. 2. Сортируем список оцениваемых сотрудников, от самого трудно-оцениваемого (его могут оценить мало людей) к самому легко оцениваемому (его могут оценить много людей), а список оценивающих сотрудников от самого "плохого" оценщика (может оценить мало людей) к самому хорошему оценщику (может оценить много людей). 3. Идем по списку оцениваемых, для каждого выбираем по 5 оценщиков (выполняя проход по списку оценщиков и проверяя условие, может ли он оценивать текущего оцениваемого и не набрал ли он уже себе 5 пар) и после набора 5ых переходим к следующему. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.03.2014, 15:55 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=38587928&tid=2127491]: |
0ms |
get settings: |
10ms |
get forum list: |
14ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
169ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
46ms |
get tp. blocked users: |
1ms |
| others: | 246ms |
| total: | 502ms |

| 0 / 0 |
