Подразделы

Другие разделы

Дата и время

20/12/2024 07:30:33

Авторизация

Зарегистрироваться
Восстановить пароль

Занятие 18

Эйлеров путь Задача: Уроборос Разбор задачи Топологическая сортировка Максимальное паросочетание Задача о назначениях

Задача о назначениях

Задача о назначениях – одна из наиболее известных дискретных оптимизационных задач. Цель задачи — найти оптимальное (минимальной стоимости) распределение `n` работников по `n` заданным работам. Задача о назначениях имеет широкое применение, например, при закреплении машин за маршрутами, распределении инструментов для обработки различных марок стали и т.д.

Задача формализуется следующим образом: задана матрица стоимостей `С_{ij}`, найти перестановку чисел `1,\ …,\ n`, для которой сумма будет минимальной.

Венгерский метод Куна состоит из трех шагов:

Шаг 1. Редукция матрицы.

В исходной матрице стоимостей в каждой строке определяется минимальная стоимость и вычитается от всех элементов строки. В полученной матрице в каждом столбце определяется минимальная стоимость и вычитается от всех элементов столбца. В результате, в каждой строке и в каждом столбце матрицы появятся нулевые элементы.

Шаг 2. Построение паросочетания.

Строится двудольный граф, вершины которого соответствуют строкам и столбцам матрицы, а ребра – нулевым элементам, стоящим на пересечении соответствующих строк и столбцов. Ищется наибольшее паросочетание в построенном графе. Если паросочетание окажется полным, то оно задает оптимальное решение задачи о назначениях, иначе выполняется шаг 3.

Шаг 3. Преобразование Эгервари.

В последней матрице проводится минимальное число горизонтальных и вертикальных прямых по строкам и столбцам так, чтобы в матрице вычеркнулись все нулевые элементы. Наименьший невычеркнутый элемент вычитается из всех невычеркнутых элементов и прибавляется к элементам, стоящим на пересечении проведенных прямых. В результате в матрице количество нулевых элементов увеличится. Далее снова выполняется шаг 2.

const int INF = 1e9;

int n;
vector < vector<int> > a;
vector<int> xy, yx;
vector<char> vx, vy;
vector<int> minrow, mincol;

bool dotry (int i) {
  if (vx[i])  return 0;
  vx[i] = 1;
  for (int j=0; j<n; ++j)
    if (a[i][j]-minrow[i]-mincol[j] == 0)
      vy[j] = 1;
  for (int j=0; j<n; ++j)
    if (a[i][j]-minrow[i]-mincol[j] == 0 && yx[j] == -1) {
      xy[i] = j;
      yx[j] = i;
      return 1;
  }
  for (int j=0; j<n; ++j)
    if (a[i][j]-minrow[i]-mincol[j] == 0 && dotry (yx[j])) {
      xy[i] = j;
      yx[j] = i;
      return 1;
  }
  return 0;
}

int main() {
  cin>>n;
  a.resize(n,vector<int>(n));
  for (int i=0; i<n; ++n)
    for (int j=0; j<n; ++j)
      cin>>a[i][j]; 
  mincol.assign (n, INF);
  minrow.assign (n, INF);
  for (int i=0; i<n; ++i)
    for (int j=0; j<n; ++j)
      minrow[i] = min (minrow[i], a[i][j]);
  for (int j=0; j<n; ++j)
    for (int i=0; i<n; ++i)
      mincol[j] = min (mincol[j], a[i][j] - minrow[i]);

  xy.assign (n, -1);
  yx.assign (n, -1);
  for (int c=0; c<n; ) {
    vx.assign (n, 0);
    vy.assign (n, 0);
    int k = 0;
    for (int i=0; i<n; ++i)
      if (xy[i] == -1 && dotry (i))
        ++k;
    c += k;
    if (k == 0) {
      int z = INF;
      for (int i=0; i<n; ++i)
        if (vx[i])
          for (int j=0; j<n; ++j)
            if (!vy[j])
              z = min (z, a[i][j]-minrow[i]-mincol[j]);
      for (int i=0; i<n; ++i) {
        if (vx[i]) minrow[i] += z;
        if (vy[i]) mincol[i] -= z;
      }
    }
  }
  int ans = 0;
  for (int i=0; i<n; ++i)
    ans += a[i][xy[i]];
  cout<<ans<<"\n";
  for (int i=0; i<n; ++i)
    cout<<" "<<(xy[i]+1);
  cout<<"\n";
  return 0;
}

Введем следующие понятия.

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

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

3. Элементы, расположенные в выделенных строках или столбцах, называются выделенными элементами.

Описание алгоритма венгерского метода

Алгоритм состоит из предварительного этапа и не более чем (n-2) последовательно проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором максимального числа независимых нулей. Окончательным результатом итерации является увеличение числа независимых нулей на единицу.

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

Предварительный этап. Разыскивают максимальный элемент в столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию проделывают над всеми столбцами матрицы . В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль.

Далее рассматривают строку полученной матрицы и из каждого её элемента вычитают минимальный элемент этой строки. Эту процедуру повторяют со всеми строками. В результате получим матрицу ( ~ ), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования в называется приведением матрицы.

Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы . Очевидно, что нули матрицы , отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.

(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица . Если в ней имеется ровно нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) – й итерации.

Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий – первый. Перед началом итерации знаком '+' выделяют столбцы матрицы , которые содержат нули со звездочками.

Первый этап. Просматривают невыделенные столбцы матрицы . Если среди них не окажется нулевых элементов, то переходят к третьему этапу.

Если же невыделенный нуль матрицы обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.

Во втором случае переходим сразу ко второму этапу, отметив этот нуль штрихом.

В первом случае этот невыделенный нуль отмечают штрихом и выделяют строку, в которой он содержится (знаком '+' справа от строки). Просматривают эту строку, находят нуль со звездочкой и уничтожают знак '+' выделения столбца, в котором содержится данный нуль.

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

Этот процесс за конечное число шагов заканчивается одним из следующих исходов:

1) все нули матрицы выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;

2) имеется такой невыделенный нуль в строке, где нет нуля со звездочкой. Тогда переходят ко второму этапу, отметив этот нуль штрихом.

Второй этап. На этом этапе строят следующую цепочку из нулей матрицы : исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т.д.

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

Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) –, ставим звездочки, уничтожая их над четными элементами ( 0* ). Затем уничтожаем все штрихи над элементами и знаки выделения '+'. Количество независимых нулей будет увеличено на единицу. На этом (k+1) –я итерация закончена.

Третий этап. К этому этапу переходят после первого, если все нули матрицы выделены, т.е. находятся на выделенных строках или столбцах. В таком случае среди невыделенных элементов матрицы выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы , расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу , эквивалентную . Заметим, что при таком преобразовании, все нули со звездочкой матрицы остаются нулями и в , кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.