Подсчет совпадений в двудольном графе
У меня есть двудольный граф с N узлами на одной стороне и почти 100 на другой стороне.
Теперь мне нужно посчитать совпадения таким образом, чтобы каждый узел в первой части имел ссылку на какой-то узел в другой части, так чтобы ни один из узлов в первой части не совпадал с тем же узлом во второй части (точно так же, как одно задание может быть назначено одному только заявитель)
Теперь я знаю, что найти этот счетчик нелегко и это # P-трудная проблема (по ссылке: https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in-general-graphs )
Но что может быть грубым решением для этого? Кто-нибудь может объяснить, пожалуйста, с помощью некоторого кода или псевдокода.
Предположим, что ввод такой, как если бы у нас было X пар, показывающих, что вы подключены к
Если N = 2 и X = 4, а пары равны (1,1), (1,2), (2,3), (2,4).
Решение
Может быть решение для динамического программирования для малых N, где 2 ^ N — практическое число.
Представьте график в виде таблицы N x 100, где записи помечены как истинные при наличии ссылки с одной стороны на другую. Для i = 1..100 мы рассчитаем Count (i, x), где x находится в диапазоне 0..2 ^ N-1 и представляет собой набор узлов на стороне N. Count (i, x) будет подсчетом количества совпадений между узлами в наборе x на стороне N и первыми узлами i на стороне 100.
Мы можем вычислить Count (i, x) из Count (i-1, *), рассматривая случаи, когда есть совпадение между i и одним из узлов в x, и случай, когда их нет. Случай, где нет баллов Count (i — 1, x) — номер способа создания соответствия, не использующего i. Для каждого установленного бита в x, если есть ссылка от i до узла, представленного этим битом, пусть y будет битовой комбинацией для x с этим битом, не установленным, и добавьте Count (i — 1, y) к счету до сих пор , Count (i, x) является суммой всех этих подсчетов.
Окончательный ответ — Count (100, 2 ^ N-1) — количество совпадений между первыми 100 узлами на одной стороне и всеми N узлами на другой стороне.
Другие решения