2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Алгоритм на двудольном графе
Сообщение17.12.2020, 09:42 
Аватара пользователя
Подскажите, пожалуйста, как решать следующую задачу.

Имеется двудольных граф. Число вершин справа больше числа вершин слева. Каждая левая вершина соединена как минимум с двумя правыми вершинами (как правило, их пять). Каждая правая вершина соединена как минимум с одной левой вершиной (но их может быть до пяти включительно). Каждая правая вершина имеет вес, а так же ограничение на возможное число выбранных рёбер (обычно один, но величина может быть больше).

Необходимо для левой вершины выбрать в пару одну правую так, чтобы не нарушались ограничения, а сумма весов выбранных вершин была минимальна.

Для начала подошло бы какое-нибудь простое субоптимальное решение. Но честное решение задачи гораздо интереснее. Тут ещё, правда, есть особенность, заключающаяся в том, что веса не совсем случайны, а связаны с устройством графа. Хотелось бы пока обойтись без учёта этого свойства.

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 10:42 
Аватара пользователя
Забыл ещё добавить, что у каждой левой вершины графа есть выделенная правая вершина, которую можно назвать зеркальной. На эту правую зеркальную вершину могут претендовать другие левые вершины, но она имеет родство только с одной — отражением которой является. Поэтому у задачи всегда есть решение, когда левые вершины соединены ребром со своим отражением.

-- 17.12.2020, 11:24 --

B@R5uk в сообщении #1496903 писал(а):
веса не совсем случайны, а связаны с устройством графа

Конкретно это выражается в том, что как правило, для каждой левой вершины вес правой, в которую ведёт ребро, либо на единицу больше зеркальной, либо на единицу меньше. Хотя могут быть исключения со значительным скачком.

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 11:48 
Аватара пользователя
B@R5uk в сообщении #1496903 писал(а):
сумма весов выбранных вершин была минимальна
Сумма считается с учетом кратности? То есть если мы одну правую выбрали для двух левых - её вес считается дважды, или один раз?
Если с учетом кратности - то это сводится к потоку минимальной стоимости (почти что он и есть).

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 12:23 
Аватара пользователя
С учётом кратности. Но конкретно в моём случае у меня все веса положительны, а у правых вершин, которые допускают несколько выбранных рёбер вес нулевой. Все остальные правые вершины (с ненулевым весом) имеют ограничение в одно выбранное ребро.

mihaild в сообщении #1496912 писал(а):
это сводится к потоку минимальной стоимости

Спасибо! Надо будет вдумываться. Но, если честно, уже страшно.

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 13:28 
Аватара пользователя
Так, я, видимо, ошибся. Вес назначается именно ребру, а не вершине, в которую он идёт. То есть в одну вершину могут идти рёбра с разным весом.

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 14:32 
Аватара пользователя
B@R5uk в сообщении #1496927 писал(а):
Вес назначается именно ребру, а не вершине, в которую он идёт
А это уже в чистом виде поток минимальной стоимости с ограничением пропускной способности вершин (которое элементарно сводится к ограничению пропускной способности ребер).

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 17:09 
Аватара пользователя
Чёрт! Я забыл одну очень важную вещь. На языке поставленной задачи она заключается в том, что при выборе ребра, ведущего в правую вершину нулевого веса, ведущее в зеркальную вершину ребро тоже резервируется (с нулевым весом). Это ещё одна отличительная особенность зеркальной вершины, и она ломает всю красивую постановку задачи. Теперь я прям вообще в тупике.

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 17:24 
Может, на исходном языке сформулируете условие?

 
 
 
 Re: Алгоритм на двудольном графе
Сообщение17.12.2020, 18:07 
Аватара пользователя
Да я на так и сяк кручу задачу о назначениях с хитрыми правилами. Есть несколько работников, каждый из них может быть назначен на некоторое число работ. Для каждого работника это число не больше 5. Число работ больше числа работников и в самом оптимальном случае на работу вообще можно назначить только одного работника В таком случае число работ равно числу рабочих, помноженному на 5. У каждой работы есть цена, целое число от нуля и больше. От обычной задачи о назначениях моя отличается тем, что на некоторые работы можно назначить несколько работников, но не больше заданного числа. А так же тем, что назначение на одну работу (с нулевой ценой) может заблокировать для всех работников назначение на другую работу (зеркальная вершина в предыдущей формулировке). Цена есть только у работ, все работники одинаковые.

Тут ещё есть момент, что цена работ может меняться в зависимости от того, кто куда назначен, но лучше в такие дебри не лезть, выигрыш всё равно будет не большой, а считать ну очень ресурсозатратно.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group