powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Случайный регулярный граф из 150 точек
8 сообщений из 8, страница 1 из 1
Случайный регулярный граф из 150 точек
    #38587845
nyquist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Всем привет! Нужна помощь с алгоритмом. Нужно построить регулярны граф на 150 (200), где в каждую вершину входит 5 ребер и выходит 5 ребер.

Как эта ситуация выглядит в жизни... Есть организация, в которой где-то 150 человек, нужно чтобы каждый человек оценил 5-х сотрудников. Также есть список кто кого может оценивать.

Задачу можно представить в виде графа, где вершина - это сотрудник, а ребро - это кто кого оценивает. И нужно чтобы из вершины выходило 5 ребер и входило столько же.

Есть какие-нибудь идей?
Просматривал различные алгоритмы, но не нашел ничего подходящего.

Уже подумываю создать граф со всеми допустимыми ребрами и отсечь избыточные. Но в этом случае некоторым сотрудникам прибавиться работы, т.к. они будут оценивать более 5 человек.
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38587902
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nyquist,
не совсем понимаю причем здесь графы, но вариант, который сходу приходит в голову:
1. Делаем 2 списка сотрудников - оценивающие, оцениваемые, для каждого списка выполняем шуфл.
2. Идем в цикле по 1му списку (оценивающих) и выдаем ему 5шт на оценку по порядку из второго списка, в случае если выпадает сам на себя, то пропуск, если конец списка, то выполняем переход к началу.
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38587928
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Я бы взял 0,1 матрицу 200х200 (размеры позволяют) и последовательно заполнял строчки, случайно выбирая 5 из 199 (нельзя оценивать себя) в начале, и из меньшего числа - далее, исключая столбцы, набравшие 5 единиц. Сложность заполнения - n 2 .
Но тут еще накладываются ограничения на выборку в строке (список, кто кого может оценить), и задача может не иметь решения. Как вариант - обратно "включать" отключенные столбцы, если только в них есть требуемые связи
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38588129
nyquist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
just_vladimirnyquist,
не совсем понимаю причем здесь графы, но вариант, который сходу приходит в голову:
1. Делаем 2 списка сотрудников - оценивающие, оцениваемые, для каждого списка выполняем шуфл.
2. Идем в цикле по 1му списку (оценивающих) и выдаем ему 5шт на оценку по порядку из второго списка, в случае если выпадает сам на себя, то пропуск, если конец списка, то выполняем переход к началу.

Этот алгоритм подходил бы, если бы каждый сотрудник мог оценивать любого сотрудника. Но в данном случае каждый сотрудник может оценивать только определенных сотрудников (от 5 до 199).
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38588165
nyquist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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.

Сейчас подумываю решить задачу симплекс-методом, но сомневаюсь что он осилит такие объемы вычислений.
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38588202
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На матрице инцедентности проще решать задачу IMHO.
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38588209
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
nyquist,
задача в любом случае может не иметь решения. Например, представьте, что списки составлены таким образом, что люди с номерами 2...200 могут оценить №1 и еще 4 случайных. В этом случае, первый номер будет оценен 199 раз.
В случае с матрицей можно предложить 2 прохода - случайный выбор по строкам, как описано выше (с исключением "накопленных" столбцов), потом то же самое по столбцам. В результате некоторые участники будут оценивать / оцениваться более 5 раз, вплоть до вырожденных случаев (199)
...
Рейтинг: 0 / 0
Случайный регулярный граф из 150 точек
    #38588409
just_vladimir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
nyquistjust_vladimirnyquist,
не совсем понимаю причем здесь графы, но вариант, который сходу приходит в голову:
1. Делаем 2 списка сотрудников - оценивающие, оцениваемые, для каждого списка выполняем шуфл.
2. Идем в цикле по 1му списку (оценивающих) и выдаем ему 5шт на оценку по порядку из второго списка, в случае если выпадает сам на себя, то пропуск, если конец списка, то выполняем переход к началу.

Этот алгоритм подходил бы, если бы каждый сотрудник мог оценивать любого сотрудника. Но в данном случае каждый сотрудник может оценивать только определенных сотрудников (от 5 до 199).
ок, пропустил в исходном посте это ограничение, тогда жадный алгоритм, ну и правило отбора наоборот:
1. Идем по спискам сопоставления и считаем для каждого из сотрудников то, сколько человек его может оценить и скольких он может оценить.
2. Сортируем список оцениваемых сотрудников, от самого трудно-оцениваемого (его могут оценить мало людей) к самому легко оцениваемому (его могут оценить много людей), а список оценивающих сотрудников от самого "плохого" оценщика (может оценить мало людей) к самому хорошему оценщику (может оценить много людей).
3. Идем по списку оцениваемых, для каждого выбираем по 5 оценщиков (выполняя проход по списку оценщиков и проверяя условие, может ли он оценивать текущего оцениваемого и не набрал ли он уже себе 5 пар) и после набора 5ых переходим к следующему.
...
Рейтинг: 0 / 0
8 сообщений из 8, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Случайный регулярный граф из 150 точек
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]