Рубрики

Максимальное двустороннее соответствие

Графы

Сопоставление в двудольном графе — это набор ребер, выбранных таким образом, что никакие два ребра не разделяют конечную точку. Максимальное соответствие — это соответствие максимального размера (максимальное количество ребер). При максимальном совпадении, если к нему добавлено какое-либо ребро, оно больше не совпадает. Для данного двудольного графа может быть более одного максимального соответствия.

Почему мы заботимся?
Есть много реальных проблем, которые могут быть сформированы как двустороннее сопоставление. Например, рассмотрим следующую проблему:
Есть М соискателей и N рабочих мест. Каждый соискатель имеет подмножество вакансий, в которых он / она заинтересован. Каждое вакансия может принять только одного соискателя, а соискатель может быть назначен только на одну работу. Найдите распределение заданий для заявителей таким образом, чтобы как можно большее количество заявителей получили работу.

Мы настоятельно рекомендуем сначала прочитать следующий пост.

Алгоритм Форда-Фулкерсона для задачи о максимальном расходе

Максимальное двустороннее согласование и проблема максимального расхода
Проблема M aximum B ipartite M atching ( MBP ) может быть решена путем преобразования ее в сеть потоков (см. Это видео, чтобы узнать, как мы пришли к такому выводу). Ниже приведены шаги.

1) Построить потоковую сеть
Должен быть источник и сток в сети потока. Таким образом, мы добавляем источник и добавляем ребра из источника всем заявителям. Аналогично, добавьте ребра из всех заданий в сток. Вместимость каждого края отмечена как 1 единица.

2) Найти максимальный расход.
Мы используем алгоритм Форда-Фулкерсона, чтобы найти максимальный поток в сети потоков, встроенной в шаге 1. На самом деле максимальный поток — это искомая MBP.

Как реализовать вышеуказанный подход?
Давайте сначала определим формы ввода и вывода. Ввод осуществляется в форме матрицы Эдмондса, которая представляет собой двумерный массив «bpGraph [M] [N]» с M строками (для M соискателей) и N столбцами (для N работ). Значение bpGraph [i] [j] равно 1, если i-й заявитель заинтересован в j-й работе, иначе 0.
Выход — это максимальное количество людей, которые могут получить работу.

Простой способ реализовать это — создать матрицу, которая представляет матричное представление смежности ориентированного графа с M + N + 2 вершинами. Вызовите fordFulkerson () для матрицы. Эта реализация требует O ((M + N) * (M + N)) дополнительного пространства.

Можно сократить дополнительное пространство и упростить код, используя тот факт, что граф является двудольным, а емкость каждого ребра равна 0 или 1. Идея состоит в том, чтобы использовать обход DFS для поиска работы для кандидата (аналогично увеличению пути в Ford-Фулкерсон). Мы вызываем bpm () для каждого кандидата, bpm () — это функция, основанная на DFS, которая пробует все возможности назначить работу кандидату.

В bpm () мы один за другим пробуем все вакансии, которые интересуют кандидата 'u', пока мы не найдем работу, или пока все работы не будут выполнены без удачи. Для каждой работы, которую мы пробуем, мы делаем следующее.
Если работа никому не назначена, мы просто назначаем ее заявителю и возвращаем true. Если задание назначено кому-то еще, скажем, x, то мы рекурсивно проверяем, можно ли назначить x другое задание. Чтобы удостовериться, что x не получит ту же самую работу снова, мы помечаем задачу 'v', как показано, прежде чем сделать рекурсивный вызов для x. Если x может получить другую работу, мы меняем претендента на работу 'v' и возвращаем true. Мы используем массив maxR [0..N-1], в котором хранятся кандидаты, назначенные на разные вакансии.

Если bmp () возвращает true, то это означает, что в сети потоков есть путь расширения и к результату в maxBPM () добавляется 1 единица потока.

C ++

// C ++ программа для поиска максимума
// Двухстороннее сопоставление.
#include <iostream>
#include <string.h>

using namespace std;

  
// M - количество претендентов
// а N - количество рабочих мест
#define M 6
#define N 6

  
// рекурсивная функция на основе DFS
// возвращает true, если соответствие
// для вершины u возможно

bool bpm(bool bpGraph[M][N], int u,

         bool seen[], int matchR[])

{

    // Попробуйте каждую работу по очереди

    for (int v = 0; v < N; v++)

    {

        // Если заявитель заинтересован в

        // работа v и v не посещена

        if (bpGraph[u][v] && !seen[v])

        {

            // Пометить v как посещенное

            seen[v] = true; 

  

            // Если задание 'v' не назначено

            // заявитель ИЛИ ранее назначенный

            // претендент на работу v (которая соответствует matchR [v])

            // есть альтернативная работа

            // Поскольку v отмечен как посещенный в

            // вышеуказанная строка, matchR [v] в следующей

            // рекурсивный вызов не получит работу 'v' снова

            if (matchR[v] < 0 || bpm(bpGraph, matchR[v],

                                     seen, matchR))

            {

                matchR[v] = u;

                return true;

            }

        }

    }

    return false;

}

  
// Возвращает максимальное количество
// соответствия от М до N

int maxBPM(bool bpGraph[M][N])

{

    // Массив для отслеживания

    // соискатели, назначенные на работу.

    // Значение matchR [i] является

    // номер заявителя, присвоенный заданию i,

    // значение -1 означает, что никто не

    // назначен

    int matchR[N];

  

    // Изначально все вакансии доступны

    memset(matchR, -1, sizeof(matchR));

  

    // Количество заданий, назначенных заявителям

    int result = 0; 

    for (int u = 0; u < M; u++)

    {

        // Пометить все работы как невидимые

        // для следующего заявителя

        bool seen[N];

        memset(seen, 0, sizeof(seen));

  

        // Найти, может ли соискатель 'и' получить работу

        if (bpm(bpGraph, u, seen, matchR))

            result++;

    }

    return result;

}

  
// Код драйвера

int main()

{

    // Давайте создадим bpGraph

    // показано в примере выше

    bool bpGraph[M][N] = {{0, 1, 1, 0, 0, 0},

                          {1, 0, 0, 1, 0, 0},

                          {0, 0, 1, 0, 0, 0},

                          {0, 0, 1, 1, 0, 0},

                          {0, 0, 0, 0, 0, 0},

                          {0, 0, 0, 0, 0, 1}};

  

    cout << "Maximum number of applicants that can get job is "

         << maxBPM(bpGraph);

  

    return 0;

}

Джава

// Java программа для поиска максимума
// Двухстороннее сопоставление.

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GFG

{

    // M - количество претендентов

    // а N - количество рабочих мест

    static final int M = 6;

    static final int N = 6;

  

    // основанная на DFS рекурсивная функция, которая

    // возвращает true, если соответствие для

    // возможна вершина u

    boolean bpm(boolean bpGraph[][], int u, 

                boolean seen[], int matchR[])

    {

        // Попробуйте каждую работу по очереди

        for (int v = 0; v < N; v++)

        {

            // Если заявитель заинтересован

            // в задании v и v не посещается

            if (bpGraph[u][v] && !seen[v])

            {

                  

                // Пометить v как посещенное

                seen[v] = true; 

  

                // Если задание 'v' не назначено

                // заявитель ИЛИ ранее

                // назначенный претендент на работу v (которая

                // is matchR [v]) имеет альтернативную работу.

                // Поскольку v отмечен как посещенный в

                // над строкой, matchR [v] в следующем

                // рекурсивный вызов не получит работу 'v' снова

                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],

                                         seen, matchR))

                {

                    matchR[v] = u;

                    return true;

                }

            }

        }

        return false;

    }

  

    // Возвращает максимальное количество

    // соответствия от М до N

    int maxBPM(boolean bpGraph[][])

    {

        // Массив для отслеживания

        // соискатели, назначенные на работу.

        // Значение matchR [i] является

        // номер заявителя, присвоенный заданию i,

        // значение -1 указывает, что никто не назначен.

        int matchR[] = new int[N];

  

        // Изначально все вакансии доступны

        for(int i = 0; i < N; ++i)

            matchR[i] = -1;

  

        // Количество заданий, назначенных заявителям

        int result = 0; 

        for (int u = 0; u < M; u++)

        {

            // Пометить все работы как невидимые

            // для следующего заявителя

            boolean seen[] =new boolean[N] ;

            for(int i = 0; i < N; ++i)

                seen[i] = false;

  

            // Найти, может ли соискатель 'и' получить работу

            if (bpm(bpGraph, u, seen, matchR))

                result++;

        }

        return result;

    }

  

    // Код драйвера

    public static void main (String[] args) 

                       throws java.lang.Exception

    {

        // Давайте создадим показанный bpGraph

        // в приведенном выше примере

        boolean bpGraph[][] = new boolean[][]{

                              {false, true, true, 

                               false, false, false},

                              {true, false, false, 

                               true, false, false},

                              {false, false, true, 

                               false, false, false},

                              {false, false, true, 

                               true, false, false},

                              {false, false, false, 

                               false, false, false},

                              {false, false, false, 

                               false, false, true}};

        GFG m = new GFG();

        System.out.println( "Maximum number of applicants that can"+

                            " get job is "+m.maxBPM(bpGraph));

    }

}

питон

# Python программа для поиска
# максимальное совпадение.

  

class GFG:

    def __init__(self,graph):

          

        # остаточный график

        self.graph = graph 

        self.ppl = len(graph)

        self.jobs = len(graph[0])

  

    # Рекурсивная функция на основе DFS

    # возвращает true, если соответствие

    # для вершины u возможно

    def bpm(self, u, matchR, seen):

  

        # Попробуйте каждую работу по очереди

        for v in range(self.jobs):

  

            # Если заявитель заинтересован

            # в заданиях v и v не видно

            if self.graph[u][v] and seen[v] == False:

                  

                # Отметить v как посещенный

                seen[v] = True 

  

                '' 'Если задание' v 'не назначено

                   заявитель ИЛИ ранее назначенный

                   претендент на работу v (которая соответствует matchR [v])

                   имеет альтернативную работу.

                   Поскольку v отмечен как посещенный в

                   выше строки, matchR [v] в следующем

                   рекурсивный вызов не получит работу 'v' снова '' '

                if matchR[v] == -1 or self.bpm(matchR[v], 

                                               matchR, seen):

                    matchR[v] = u

                    return True

        return False

  

    # Возвращает максимальное количество совпадений

    def maxBPM(self):

        '' 'Массив для отслеживания

           соискатели назначены на работу.

           Значение matchR [i] является

           номер заявителя, присвоенный вакансии i,

           значение -1 указывает, что никто не назначен. '' '

        matchR = [-1] * self.jobs

          

        # Количество заданий, назначенных претендентам

        result = 0 

        for i in range(self.ppl):

              

            # Пометить все вакансии как невидимые для следующего соискателя.

            seen = [False] * self.jobs

              

            # Найдите, может ли соискатель 'и' получить работу

            if self.bpm(i, matchR, seen):

                result += 1

        return result

  

  

bpGraph =[[0, 1, 1, 0, 0, 0],

          [1, 0, 0, 1, 0, 0],

          [0, 0, 1, 0, 0, 0],

          [0, 0, 1, 1, 0, 0],

          [0, 0, 0, 0, 0, 0],

          [0, 0, 0, 0, 0, 1]]

  

g = GFG(bpGraph)

  

print ("Maximum number of applicants that can get job is %d " % g.maxBPM())

  
# Этот код предоставлен Neelam Yadav

C #

// AC # программа для поиска максимума
// Двухстороннее сопоставление.

using System;

  

class GFG

{

    // M - количество претендентов

    // а N - количество рабочих мест

    static int M = 6;

    static int N = 6;

  

    // рекурсивная функция на основе DFS

    // возвращает true, если соответствие

    // для вершины u возможно

    bool bpm(bool [,]bpGraph, int u, 

             bool []seen, int []matchR)

    {

        // Попробуйте каждую работу по очереди

        for (int v = 0; v < N; v++)

        {

            // Если заявитель заинтересован

            // в задании v и v не посещается

            if (bpGraph[u, v] && !seen[v])

            {

                // Пометить v как посещенное

                seen[v] = true; 

  

                // Если задание 'v' не назначено

                // заявитель ИЛИ ранее назначенный

                // претендент на работу v (которая соответствует matchR [v])

                // есть альтернативная работа

                // Поскольку v отмечен как посещенный в выше

                // line, matchR [v] в следующей рекурсивной

                // вызов не получит работу 'v' снова

                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],

                                         seen, matchR))

                {

                    matchR[v] = u;

                    return true;

                }

            }

        }

        return false;

    }

  

    // Возвращает максимальное количество

    // соответствие от M до N

    int maxBPM(bool [,]bpGraph)

    {

        // Массив для отслеживания

        // соискатели, назначенные на работу.

        // Значение matchR [i] является

        // номер заявителя, присвоенный заданию i,

        // значение -1 указывает, что никто не назначен.

        int []matchR = new int[N];

  

        // Изначально все вакансии доступны

        for(int i = 0; i < N; ++i)

            matchR[i] = -1;

  

        // Количество заданий, назначенных заявителям

        int result = 0; 

        for (int u = 0; u < M; u++)

        {

            // Отметить все работы как не

            // видел следующего заявителя

            bool []seen = new bool[N] ;

            for(int i = 0; i < N; ++i)

                seen[i] = false;

  

            // Найти заявителя

            // ты можешь устроиться на работу

            if (bpm(bpGraph, u, seen, matchR))

                result++;

        }

        return result;

    }

  

    // Код драйвера

    public static void Main () 

    {

        // Давайте создадим показанный bpGraph

        // в приведенном выше примере

        bool [,]bpGraph = new bool[,]

                          {{false, true, true, 

                            false, false, false},

                           {true, false, false, 

                            true, false, false},

                           {false, false, true, 

                            false, false, false},

                           {false, false, true, 

                            true, false, false},

                           {false, false, false, 

                            false, false, false},

                           {false, false, false, 

                            false, false, true}};

        GFG m = new GFG();

    Console.Write( "Maximum number of applicants that can"+

                            " get job is "+m.maxBPM(bpGraph));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска максимума
// Двухстороннее сопоставление.

  
// M - количество претендентов
// а N - количество рабочих мест

$M = 6;

$N = 6;

  
// рекурсивная функция на основе DFS
// возвращает true, если соответствие
// для вершины u возможно

function bpm($bpGraph, $u, &$seen, &$matchR)

{

    global $N;

      

    // Попробуйте каждую работу по очереди

    for ($v = 0; $v < $N; $v++)

    {

        // Если заявитель заинтересован в

        // работа v и v не посещена

        if ($bpGraph[$u][$v] && !$seen[$v])

        {

            // Пометить v как посещенное

            $seen[$v] = true; 

  

            // Если задание 'v' не назначено

            // заявитель ИЛИ ранее назначенный

            // претендент на работу v (которая соответствует matchR [v])

            // есть альтернативная работа

            // Поскольку v отмечен как посещенный в

            // вышеуказанная строка, matchR [v] в следующей

            // рекурсивный вызов не получит работу 'v' снова

            if ($matchR[$v] < 0 || bpm($bpGraph, $matchR[$v],

                                    $seen, $matchR))

            {

                $matchR[$v] = $u;

                return true;

            }

        }

    }

    return false;

}

  
// Возвращает максимальное количество
// соответствия от М до N

function maxBPM($bpGraph)

{

    global $N,$M;

      

    // Массив для отслеживания

    // соискатели, назначенные на работу.

    // Значение matchR [i] является

    // номер заявителя, присвоенный заданию i,

    // значение -1 означает, что никто не

    // назначен

    $matchR = array_fill(0, $N, -1);

  

    // Изначально все вакансии доступны

  

    // Количество заданий, назначенных заявителям

    $result = 0; 

    for ($u = 0; $u < $M; $u++)

    {

        // Пометить все работы как невидимые

        // для следующего заявителя

        $seen=array_fill(0, $N, false);

  

        // Найти, может ли соискатель 'и' получить работу

        if (bpm($bpGraph, $u, $seen, $matchR))

            $result++;

    }

    return $result;

}

  
// Код драйвера

  
// Давайте создадим bpGraph
// показано в примере выше

$bpGraph = array(array(0, 1, 1, 0, 0, 0),

                    array(1, 0, 0, 1, 0, 0),

                    array(0, 0, 1, 0, 0, 0),

                    array(0, 0, 1, 1, 0, 0),

                    array(0, 0, 0, 0, 0, 0),

                    array(0, 0, 0, 0, 0, 1));

  

echo "Maximum number of applicants that can get job is ".maxBPM($bpGraph);

  

  
// Этот код предоставлен chadan_jnu
?>


Выход :

Maximum number of applicants that can get job is 5

Вы можете также увидеть ниже:
Алгоритм Хопкрофта – Карпа для максимального соответствия | Комплект 1 (Введение)
Алгоритм Хопкрофта – Карпа для максимального соответствия | Набор 2 (реализация)

Ссылки:
http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part5.pdf
http://www.youtube.com/watch?v=NlQqmEXuiC8
http://en.wikipedia.org/wiki/Maximum_matching
http://www.stanford.edu/class/cs97si/08-network-flow-problems.pdf
http://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/07NetworkFlowII-2×2.pdf
http://www.ise.ncsu.edu/fangroup/or766.dir/or766_ch7.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Максимальное двустороннее соответствие

0.00 (0%) 0 votes