Рубрики

Проблема с назначением задания с использованием ветви и границы

Пусть будет N рабочих и N рабочих мест. Любой работник может быть назначен для выполнения любой работы, что влечет за собой определенные расходы, которые могут варьироваться в зависимости от назначения на работу. Требуется выполнить все задания, назначив ровно одного работника каждому заданию и ровно одно задание каждому агенту таким образом, чтобы сводить к минимуму общую стоимость задания.

Давайте рассмотрим все подходы к этой проблеме.

Решение 1: грубая сила
Мы генерируем! возможные назначения работы, и для каждого такого назначения мы вычисляем его общую стоимость и возвращаем менее дорогостоящее назначение. Поскольку решение является перестановкой из n заданий, его сложность составляет O (n!).

Решение 2: Венгерский алгоритм
Оптимальное назначение можно найти с помощью венгерского алгоритма. Венгерский алгоритм имеет наихудший вариант сложности времени выполнения O (n ^ 3).

Решение 3: DFS / BFS на дереве пространства состояний
Дерево пространства состояний — это N-арное дерево со свойством, что любой путь от корневого до конечного узла содержит одно из многих решений данной проблемы. Мы можем выполнить поиск в глубину по дереву пространства состояний, но последовательные шаги могут отвести нас от цели, а не приблизить. Поиск дерева пространства состояний следует по крайнему левому пути от корня независимо от исходного состояния. Узел ответа никогда не может быть найден в этом подходе. Мы также можем выполнить поиск в ширину по дереву пространства состояний. Но независимо от того, каково начальное состояние, алгоритм пытается выполнить ту же последовательность действий, что и DFS.

Решение 4: Нахождение оптимального решения с использованием ветвления и границы
Правило выбора следующего узла в BFS и DFS является «слепым». т. е. правило выбора не дает никаких предпочтений узлу, который имеет очень хорошие шансы быстро выполнить поиск по узлу ответа. Поиск оптимального решения часто может быть ускорен с помощью «интеллектуальной» функции ранжирования, также называемой функцией приблизительной стоимости, чтобы избежать поиска в поддеревьях, которые не содержат оптимального решения. Это похоже на BFS-подобный поиск, но с одной важной оптимизацией. Вместо того, чтобы следовать порядку FIFO, мы выбираем живой узел с наименьшей стоимостью. Мы не можем получить оптимальное решение, следуя по узлу с наименьшими многообещающими затратами, но это обеспечит очень хорошие шансы быстрого поиска поиска на узле ответа.

Существует два подхода для расчета функции стоимости:

  1. Для каждого работника мы выбираем работу с минимальными затратами из списка неназначенных работ (выбираем минимальную запись из каждой строки).
  2. Для каждой работы мы выбираем работника с наименьшей стоимостью для этой работы из списка неназначенных работников (выбирайте минимальную запись из каждого столбца).

В этой статье используется первый подход.

Давайте возьмем приведенный ниже пример и попробуем рассчитать многообещающую стоимость, когда задание 2 назначено работнику А.

Поскольку задание 2 назначено работнику A (отмечено зеленым), стоимость становится равной 2, а задание 2 и работник A становятся недоступными (отмечены красным).

Теперь мы назначаем задание 3 работнику B, так как оно имеет минимальную стоимость из списка неназначенных заданий. Стоимость становится 2 + 3 = 5, а Работа 3 и работник Б также становятся недоступными.

Наконец, задание 1 назначается работнику C, поскольку оно имеет минимальную стоимость среди неназначенных заданий, а задание 4 назначается работнику C, поскольку это только оставленное задание. Общая стоимость становится 2 + 3 + 5 + 4 = 14.

На приведенной ниже диаграмме показана полная диаграмма пространства поиска с указанием оптимального пути решения зеленым цветом.

Полный алгоритм:

/* findMinCost uses Least() and Add() to maintain the
   list of live nodes

   Least() finds a live node with least cost, deletes
   it from the list and returns it

   Add(x) calculates cost of x and adds it to the list
   of live nodes

   Implements list of live nodes as a min heap */


// Search Space Tree Node
node
{
   int job_number;
   int worker_number;
   node parent;
   int cost;
}

// Input: Cost Matrix of Job Assignment problem
// Output: Optimal cost and Assignment of Jobs
algorithm findMinCost (costMatrix mat[][])
{
   // Initialize list of live nodes(min-Heap)
   // with root of search tree i.e. a Dummy node
   while (true)
   {
      // Find a live node with least estimated cost
      E = Least();

      // The found node is deleted from the list
      // of live nodes
      if (E is a leaf node)
      {
         printSolution();
         return;
      }

     for each child x of E
     {
         Add(x); // Add x to list of live nodes;
         x->parent = E; // Pointer for path to root
     }
   }
} 

Ниже его реализация C ++.

// Программа для решения задачи по назначению
// используя Branch and Bound
#include <bits/stdc++.h>

using namespace std;

#define N 4

  
// узел дерева пространства состояний

struct Node

{

    // сохраняет родительский узел текущего узла

    // помогает в отслеживании пути, когда ответ найден

    Node* parent;

  

    // содержит стоимость для узлов предков

    // включая текущий узел

    int pathCost;

  

    // содержит наименьшую перспективную стоимость

    int cost;

  

    // содержит рабочий номер

    int workerID;

  

    // содержит идентификатор задания

    int jobID;

  

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

    // информация о доступных вакансиях

    bool assigned[N];

};

  
// Функция для выделения нового узла дерева поиска
// Здесь Person x назначен на работу y

Node* newNode(int x, int y, bool assigned[],

              Node* parent)

{

    Node* node = new Node;

  

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

        node->assigned[j] = assigned[j];

    node->assigned[y] = true;

  

    node->parent = parent;

    node->workerID = x;

    node->jobID = y;

  

    return node;

}

  
// Функция для расчета наименее перспективной стоимости
// узла после того, как рабочий x назначен заданию y.

int calculateCost(int costMatrix[N][N], int x,

                  int y, bool assigned[])

{

    int cost = 0;

  

    // для хранения недоступных заданий

    bool available[N] = {true};

  

    // начать со следующего работника

    for (int i = x + 1; i < N; i++)

    {

        int min = INT_MAX, minIndex = -1;

  

        // делаем для каждой работы

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

        {

            // если работа не назначена

            if (!assigned[j] && available[j] &&

                costMatrix[i][j] < min)

            {

                // сохранить номер задания

                minIndex = j;

  

                // стоимость магазина

                min = costMatrix[i][j];

            }

        }

  

        // добавляем стоимость следующего работника

        cost += min;

  

        // работа становится недоступной

        available[minIndex] = false;

    }

  

    return cost;

}

  
// Объект сравнения, который будет использоваться для упорядочения кучи

struct comp

{

    bool operator()(const Node* lhs,

                   const Node* rhs) const

    {

        return lhs->cost > rhs->cost;

    }

};

  
// распечатать задания

void printAssignments(Node *min)

{

    if(min->parent==NULL)

        return;

  

    printAssignments(min->parent);

    cout << "Assign Worker " << char(min->workerID + 'A')

         << " to Job " << min->jobID << endl;

  
}

  
// Находит минимальную стоимость используя Branch and Bound.

int findMinCost(int costMatrix[N][N])

{

    // Создать приоритетную очередь для хранения живых узлов

    // поиск дерева;

    priority_queue<Node*, std::vector<Node*>, comp> pq;

  

    // инициализируем кучу для фиктивного узла со стоимостью 0

    bool assigned[N] = {false};

    Node* root = newNode(-1, -1, assigned, NULL);

    root->pathCost = root->cost = 0;

    root->workerID = -1;

  

    // Добавить фиктивный узел в список живых узлов;

    pq.push(root);

  

    // Находит живой узел с наименьшей стоимостью,

    // добавляем своих детей в список живых узлов и

    // окончательно удаляет его из списка.

    while (!pq.empty())

    {

      // Найти живой узел с наименьшей оценочной стоимостью

      Node* min = pq.top();

  

      // Найденный узел удаляется из списка

      // живые узлы

      pq.pop();

  

      // я храню следующего работника

      int i = min->workerID + 1;

  

      // если всем работникам назначена работа

      if (i == N)

      {

          printAssignments(min);

          return min->cost;

      }

  

      // делаем для каждой работы

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

      {

        // Если не назначено

        if (!min->assigned[j])

        {

          // создаем новый узел дерева

          Node* child = newNode(i, j, min->assigned, min);

  

          // стоимость для узлов предков, включая текущий узел

          child->pathCost = min->pathCost + costMatrix[i][j];

  

          // вычисляем его нижнюю границу

          child->cost = child->pathCost +

            calculateCost(costMatrix, i, j, child->assigned);

  

          // Добавить дочерний элемент в список живых узлов;

          pq.push(child);

        }

      }

    }

}

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

int main()

{

    // x-cordinate представляет Работника

    // Y-Cordinate представляет работу

    int costMatrix[N][N] =

    {

        {9, 2, 7, 8},

        {6, 4, 3, 7},

        {5, 8, 1, 8},

        {7, 6, 9, 4}

    };

  

  

    / * int costMatrix [N] [N] =

    {

        {82, 83, 69, 92},

        {77, 37, 49, 92},

        {11, 69, 5, 86},

        {8, 9, 98, 23}

    };

    * /

  

    / * int costMatrix [N] [N] =

    {

        {2500, 4000, 3500},

        {4000, 6000, 3500},

        {2000, 4000, 2500}

    }; * /

  

    / * int costMatrix [N] [N] =

    {

        {90, 75, 75, 80},

        {30, 85, 55, 65},

        {125, 95, 90, 105},

        {45, 110, 95, 115}

    }; * /

  

  

    cout << "\nOptimal Cost is "

        << findMinCost(costMatrix);

  

    return 0;

}

Выход :

Assign Worker A to Job 1
Assign Worker B to Job 0
Assign Worker C to Job 2
Assign Worker D to Job 3

Optimal Cost is 13

Ссылка :
www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bb.pdf

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Проблема с назначением задания с использованием ветви и границы

0.00 (0%) 0 votes