Рубрики

Проблема с назначением канала

Есть M передающих и N приемных станций. Дана матрица, которая отслеживает количество пакетов, которые должны быть переданы от данного передатчика к приемнику. Если (i; j) -й элемент матрицы равен k, это означает, что в это время станция i имеет k пакетов для передачи на станцию j.
В течение временного интервала передатчик может отправить только один пакет, а получатель может принять только один пакет. Найдите назначения каналов, чтобы максимальное количество пакетов передавалось от передатчиков к получателям в течение следующего временного интервала.
Пример:

0 2 0
3 0 1
2 4 0

Выше приведен формат ввода. Назовем вышеуказанную матрицу M. Каждое значение M [i; j] представляет количество пакетов, которые передатчик «i» должен отправить получателю «j». Выход должен быть:

The number of maximum packets sent in the time slot is 3
T1 -> R2
T2 -> R3
T3 -> R1 

Обратите внимание, что максимальное количество пакетов, которые могут быть переданы в любом слоте, составляет мин (M, N).

Алгоритм:
Проблема назначения канала между отправителем и получателем может быть легко преобразована в проблему максимального двустороннего согласования (MBP), которая может быть решена путем преобразования ее в потоковую сеть.

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

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

Реализация:
Давайте сначала определим формы ввода и вывода. Входные данные представлены в виде матрицы Эдмондса, которая представляет собой двумерный массив 'table [M] [N]' с M строками (для M отправителей) и N столбцами (для N получателей). Таблица значений [i] [j] — это количество пакетов, которые должны быть отправлены от передатчика «i» к приемнику «j». Выход — это максимальное количество пакетов, которые могут быть переданы без помех пропускной способности во временном интервале.
Простой способ реализовать это — создать матрицу, которая представляет матричное представление смежности ориентированного графа с M + N + 2 вершинами. Вызовите fordFulkerson () для матрицы. Эта реализация требует O ((M + N) * (M + N)) дополнительного пространства.
Дополнительное пространство может быть уменьшено, и код может быть упрощен, используя тот факт, что граф является двудольным. Идея состоит в том, чтобы использовать обход DFS, чтобы найти приемник для передатчика (аналогично увеличению пути в Ford-Fulkerson). Мы вызываем bpm () для каждого кандидата, bpm () — это функция, основанная на DFS, которая пытается использовать все возможности для назначения получателя отправителю. В bpm () мы один за другим пробуем все получатели, которые интересуют отправителя 'u', пока не найдем получателя, или пока все получатели не будут испытаны без удачи.
Для каждого получателя, который мы пытаемся, мы делаем следующее:
Если получатель не назначен никому, мы просто назначаем его отправителю и возвращаем true. Если получатель назначен кому-то еще, скажем, x, то мы рекурсивно проверяем, может ли x быть назначен другому получателю. Чтобы удостовериться, что x не получит тот же получатель снова, мы помечаем получателя как v, прежде чем сделать рекурсивный вызов для x. Если x может получить другого получателя, мы меняем отправителя для получателя 'v' и возвращаем true. Мы используем массив maxR [0..N-1], в котором хранятся отправители, назначенные разным получателям.
Если bmp () возвращает true, то это означает, что в сети потоков есть путь расширения и к результату в maxBPM () добавляется 1 единица потока.

Анализ сложности времени и пространства:
В случае двунаправленной проблемы соответствия F? | V | поскольку может быть только | V | возможные ребра, выходящие из исходного узла. Таким образом, общее время работы O (m'n) = O ((m + n) n). Сложность пространства также существенно уменьшается от O ((M + N) * (M + N)) до просто одномерного массива размера M, таким образом сохраняя отображение между M и N.

С

#include <iostream>
#include <string.h>
#include <vector>
#define M 3
#define N 4

using namespace std;

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

bool bpm(int table[M][N], int u, bool seen[], int matchR[])

{

    // Попробуйте каждый получатель один за другим

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

    {

        // Если отправитель u имеет пакеты для отправки получателю v и

        // получатель v еще не сопоставлен ни с одним другим отправителем

        // просто проверяем, больше ли число пакетов, чем 0

        // потому что только один пакет может быть отправлен в любом случае

        if (table[u][v]>0 && !seen[v])

        {

            seen[v] = true; // Пометить v как посещенное

  

            // Если получатель 'v' не назначен ни одному отправителю ИЛИ

            // ранее назначенный отправитель для получателя v (который

            // matchR [v]) имеет альтернативный получатель. поскольку

            // v отмечен как посещенный в вышеуказанной строке, matchR [v] в

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

            if (matchR[v] < 0 || bpm(table, matchR[v], seen, matchR))

            {

                matchR[v] = u;

                return true;

            }

        }

    }

    return false;

}

  
// Возвращает максимальное количество пакетов, которые могут быть отправлены параллельно в 1
// временной интервал от отправителя к получателю

int maxBPM(int table[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));

  

        // Найти, может ли отправитель 'u' быть назначен получателю

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

            result++;

    }

  

    cout << "The number of maximum packets sent in the time slot is "

         << result << "\n";

  

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

        if (matchR[x]+1!=0)

            cout << "T" << matchR[x]+1 << "-> R" << x+1 << "\n";

    return result;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int table[M][N] = {{0, 2, 0}, {3, 0, 1}, {2, 4, 0}};

    int max_flow = maxBPM(table);

    return 0;

}

Джава

import java.util.*;

class GFG 

{

static int M = 3;

static int N = 3;

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

static boolean bpm(int table[][], int u,

                   boolean seen[], int matchR[])

{

    // Попробуйте каждый получатель один за другим

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

    {

        // Если у отправителя есть пакеты для отправки

        // к получателю v, а к получателю v нет

        // уже сопоставлены с любым другим отправителем

        // просто проверяем количество пакетов

        // больше 0, потому что только один пакет

        // может быть отправлено в любом случае

        if (table[u][v] > 0 && !seen[v])

        {

            seen[v] = true; // Пометить v как посещенное

  

            // Если получатель 'v' не назначен

            // любой отправитель ИЛИ ранее назначенный отправитель

            // для получателя v (который соответствует matchR [v]) имеет

            // доступен альтернативный приемник. Так как v

            // отмечен как посещенный в вышеуказанной строке,

            // matchR [v] в следующем рекурсивном вызове

            // снова не получит получатель v

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

                                      seen, matchR))

            {

                matchR[v] = u;

                return true;

            }

        }

    }

    return false;

}

  
// Возвращает максимальное количество пакетов
// который может быть отправлен параллельно в
// 1 временной интервал от отправителя к получателю

static int maxBPM(int table[][])

{

    // Массив для отслеживания получателей

    // присваивается отправителям. Значение matchR [i]

    // идентификатор отправителя, назначенный получателю i.

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

    int []matchR = new int[N];

  

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

    // не сопоставлено ни с одним отправителем

    Arrays.fill(matchR, -1);

  

    int result = 0; // Количество получателей, назначенных отправителям

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

    {

        // Пометить всех получателей как невидимых для следующего отправителя

        boolean []seen = new boolean[N];

        Arrays.fill(seen, false);

  

        // Найти, может ли отправитель 'u' быть

        // назначен получателю

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

            result++;

    }

  

    System.out.println("The number of maximum packets"

                       " sent in the time slot is " + result);

  

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

        if (matchR[x] + 1 != 0)

            System.out.println("T" + (matchR[x] + 1) +

                               "-> R" + (x + 1));

    return result;

}

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

public static void main(String[] args) 

{

    int table[][] = {{0, 2, 0},

                     {3, 0, 1}, 

                     {2, 4, 0}};

      

    maxBPM(table);

}
}

  
// Этот код предоставлен Rajput-Ji

python3

# Рекурсивный поиск по глубине
# функция, которая возвращает true, если соответствие
# для вершины u возможно

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

    global M, N

      

    # Попробуйте каждый приемник один за другим

    for v in range(N):

          

        # Если у отправителя есть пакеты для отправки

        # получатель v и получатель v не

        # уже сопоставлен с любым другим отправителем

        # просто проверьте количество пакетов

        # больше '0', потому что только один

        # пакет может быть отправлен в любом случае

        if (table[u][v] > 0 and not seen[v]):

            seen[v] = True # Отметить v как посещенный

  

            # Если получатель 'v' не назначен ни

            # отправитель ИЛИ ранее назначенный отправитель

            # для получателя v (который соответствует matchR [v]) имеет

            # доступен альтернативный приемник. поскольку

            # v помечен как посещенный в вышеуказанной строке,

            # matchR [v] в следующем рекурсивном вызове

            # больше не получит получатель 'v'

            if (matchR[v] < 0 or bpm(table, matchR[v], 

                                       seen, matchR)):

                matchR[v] =

                return True

    return False

  
# Возвращает максимальное количество пакетов
# которые могут быть отправлены параллельно в 1
# временной интервал от отправителя к получателю

def maxBPM(table):

    global M, N

      

    # Массив для отслеживания получателей

    # присваивается отправителям. Значение

    # matchR [i] - идентификатор отправителя, назначенный

    # получатель я. Значение -1 никого не указывает

    # назначен.

  

    # Изначально все получатели не отображаются

    # любому отправителю

    matchR = [-1] * N

  

    result = 0 # Количество получателей, назначенных отправителям

    for u in range(M):

          

        # Отметить все получатели как невидимые

        # для следующего отправителя

        seen = [0] * N

  

        # Найти, можно ли назначить отправителя 'u'

        # получателю

        if (bpm(table, u, seen, matchR)): 

            result += 1

  

    print("The number of maximum packets sent"

          "in the time slot is", result)

  

    for x in range(N):

        if (matchR[x] + 1 != 0): 

            print("T", matchR[x] + 1, "-> R", x + 1

    return result

  
Код водителя

M = 3

N = 4

  

table = [[0, 2, 0], [3, 0, 1], [2, 4, 0]]

max_flow = maxBPM(table)

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

C #

// C # реализация вышеуказанного подхода

using System;

      

class GFG 

{

static int M = 3;

static int N = 3;

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

static Boolean bpm(int [,]table, int u,

                   Boolean []seen, int []matchR)

{

    // Попробуйте каждый получатель один за другим

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

    {

        // Если у отправителя есть пакеты для отправки

        // к получателю v, а к получателю v нет

        // уже сопоставлены с любым другим отправителем

        // просто проверяем количество пакетов

        // больше 0, потому что только один пакет

        // может быть отправлено в любом случае

        if (table[u, v] > 0 && !seen[v])

        {

            seen[v] = true; // Пометить v как посещенное

  

            // Если получатель 'v' не назначен

            // любой отправитель ИЛИ ранее назначенный отправитель

            // для получателя v (который соответствует matchR [v]) имеет

            // доступен альтернативный приемник. Так как v

            // отмечен как посещенный в вышеуказанной строке,

            // matchR [v] в следующем рекурсивном вызове

            // снова не получит получатель v

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

                                     seen, matchR))

            {

                matchR[v] = u;

                return true;

            }

        }

    }

    return false;

}

  
// Возвращает максимальное количество пакетов
// который может быть отправлен параллельно в
// 1 временной интервал от отправителя к получателю

static int maxBPM(int [,]table)

{

    // Массив для отслеживания получателей

    // присваивается отправителям. Значение 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];

  

        // Найти, может ли отправитель 'u' быть

        // назначен получателю

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

            result++;

    }

  

    Console.WriteLine("The number of maximum packets"

                      " sent in the time slot is " + result);

  

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

        if (matchR[x] + 1 != 0)

            Console.WriteLine("T" + (matchR[x] + 1) +

                              "-> R" + (x + 1));

    return result;

}

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

public static void Main(String[] args) 

{

    int [,]table = {{0, 2, 0},

                    {3, 0, 1}, 

                    {2, 4, 0}};

      

    maxBPM(table);

}
}

  
// Этот код предоставлен 29AjayKumar


Выход:

The number of maximum packets sent in the time slot is 3
T3-> R1
T1-> R2
T2-> R3

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

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

Проблема с назначением канала

0.00 (0%) 0 votes