Есть 3 группы людей: A, B, C по n человек.
Каждая комбинация людей имеет свой коэффициент эффективность работы. X[i,j,k]
Необходимо из них сформировать n команд такким образом, чтобы суммарная эффективность работы была бы максимальна.
т.е. сумма по i=1 to n (X[a[i],b[i],c[i]]) -> MAX, a[i]<>a[j], b[i]<>b[j], c[i]<>c[j] для любых i,j: i<>j
В случае двух человек в команде имеем в чистом виде задачу о назначениях. Какие есть идеи по поводу 3х человек?
... << Rsdn@Home 1.1.4 beta 1 >>
Здравствуйте, Nikolaus, Вы писали:
N>Есть 3 группы людей: A, B, C по n человек.
N>Каждая комбинация людей имеет свой коэффициент эффективность работы. X[i,j,k]
N>Необходимо из них сформировать n команд такким образом, чтобы суммарная эффективность работы была бы максимальна.
N>т.е. сумма по i=1 to n (X[a[i],b[i],c[i]]) -> MAX, a[i]<>a[j], b[i]<>b[j], c[i]<>c[j] для любых i,j: i<>j
N>В случае двух человек в команде имеем в чистом виде задачу о назначениях. Какие есть идеи по поводу 3х человек?
А поле X имеет какие-нибудь свойства? Если это случайный массив — то только поиск перебором, (вообще-то как и для двух человек).
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, Nikolaus, Вы писали:
N>>Есть 3 группы людей: A, B, C по n человек.
N>>Каждая комбинация людей имеет свой коэффициент эффективность работы. X[i,j,k]
N>>Необходимо из них сформировать n команд такким образом, чтобы суммарная эффективность работы была бы максимальна.
N>>т.е. сумма по i=1 to n (X[a[i],b[i],c[i]]) -> MAX, a[i]<>a[j], b[i]<>b[j], c[i]<>c[j] для любых i,j: i<>j
N>>В случае двух человек в команде имеем в чистом виде задачу о назначениях. Какие есть идеи по поводу 3х человек?
FDS>А поле X имеет какие-нибудь свойства? Если это случайный массив — то только поиск перебором, (вообще-то как и для двух человек).
никаких свойств. Хотя можно рассматривать такой вариант: X[i,j,k]=ab[i,j]+ac[i,j]+bc[j,k], где ab, ac, bc — матрицы качества взаимодействий пар людей.
А для двух не полный перебор. Там венгерский метод используется.
... << Rsdn@Home 1.1.4 beta 1 >>
Здравствуйте, Nikolaus, Вы писали:
N>Здравствуйте, FDSC, Вы писали:
FDS>>Здравствуйте, Nikolaus, Вы писали:
N>>>Есть 3 группы людей: A, B, C по n человек.
N>>>Каждая комбинация людей имеет свой коэффициент эффективность работы. X[i,j,k]
N>>>Необходимо из них сформировать n команд такким образом, чтобы суммарная эффективность работы была бы максимальна.
N>>>т.е. сумма по i=1 to n (X[a[i],b[i],c[i]]) -> MAX, a[i]<>a[j], b[i]<>b[j], c[i]<>c[j] для любых i,j: i<>j
N>>>В случае двух человек в команде имеем в чистом виде задачу о назначениях. Какие есть идеи по поводу 3х человек?
N>А для двух не полный перебор. Там венгерский метод используется.
Согласен. Это я немного неправильно выразился.
Предложение.
1. Венгерский алгоритм смотрел – сплошное зверство. Думаю, на 3-х мерный случай его просто так обобщить.
2. Предлагаю свой собственный алгоритм. За правильность не ручаюсь. Трудоёмкость примерно та же (полиномиальная, я бы даже сказал – кубическая).
Написал на языке MatLab ‘ а. Надеюсь, поймёшь. В конце, для понимания, алгоритм, аналогичный венгерскому. Правильность не доказывал, но вроде работает правильно.
Для 3-х мерного случая (с тремя группами, что требуется)
Тут:
B(i) то же, что и B[i] в C++.
[i, i] – некоторый набор из двух величин (массив).
for i = 1:L – цикл for для I от 1 до L.
B(i, 1:2) – два элемента первой строки (т.е. первая строка, так как там всего два элемента)
% Матрица A – массив коэффициентов производительности. Т.е. A[k, i, j] показывает
% производительность группы из сотрудников с номерами k, i, j из групп A, B, C,
% соответственно
function [V] = Vinny2(A)
L = 3;
B = zeros(L, 2); // Создаём пустую матрицу размера Lx2 (строки x столбцы)
% B – матрица, строка k хранит сопоставленные сотруднику первой группы с номером k % номера сотрудников из групп B и C.
for i = 1:L
B(i, 1:2) = [i, i];
end
% Просматриваем всех сотрудников группы A.
for k = 1:L
% Просматриваем все варианты изменения сопоставления сотрудников групп B и C
for i = 1:L
for j = 1:L
% Пробуем сопоставить сотруднику k принадлежащему A сотрудников i, j из групп % B и C. Эти сотрудники должны быть сопоставлены другому сотруднику группы % A, номер которого мы находим – p.
p = 1;
while B(p, 1:2) ~= [i, j]
p = p + 1;
end
% Если изменение будет увеличивать наш функционал — меняем
q = B(i, 1); r = B(i, 2);
if A(k, i, j) + A(p, q, r) > A(k, q, r) + A(p, i, j)
B(p, 1:2) = B(i, 1:2);
B(i, 1:2) = [i, j];
end;
end
end
end
% Вывод результата
V = B;
% Алгоритм для решения обычной задачи о назначениях
function [V] = Vinny1(A)
k = 3;
% B – массив. B(i) хранит работника гр. B, сопоставленного работнику i гр. A
for i = 1:k
B(i) = i;
end
% Для каждого работника из A пробуем все варианты сотрудников из B.
for i = 1:k
[M, j] = max( A(i, 1:k) );
if A(i, B(i)) == M continue;
end;
for j = 1 : k
p = 1;
while B(p) ~= j
p = p + 1;
end
if A(i, j) + A(p, B(i)) > A(i, B(i)) + A(p, j)
B(p) = B(i);
B(i) = j;
end;
end
end
end
V = B;
Здравствуйте, Nikolaus, Вы писали:
N>Есть 3 группы людей: A, B, C по n человек.
N>Каждая комбинация людей имеет свой коэффициент эффективность работы. X[i,j,k]
N>Необходимо из них сформировать n команд такким образом, чтобы суммарная эффективность работы была бы максимальна.
N>т.е. сумма по i=1 to n (X[a[i],b[i],c[i]]) -> MAX, a[i]<>a[j], b[i]<>b[j], c[i]<>c[j] для любых i,j: i<>j
N>В случае двух человек в команде имеем в чистом виде задачу о назначениях. Какие есть идеи по поводу 3х человек?
Можно попробовать начать поиски тут
http://citeseer.ist.psu.edu/cis?q=three-dimensional+Assignment+problem&cs=1
Но у меня что-то не очень получилось.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, FDSC, Вы писали:
FDS>>% Алгоритм для решения обычной задачи о назначениях
_DA>[skipped]
_DA>Основное: оба этих алгоритма неверны. Одиночными попарными обменами эта задача не решается. Последовательность таких обменов приведет только лишь к получению некоторого локального максимума.
К сожалению, да.Алгоритмы неверны. 
Простой пример:
| 2 3 0 |
A= | 0 2 3 |.
| 3 0 2 |
А если смотреть ещё тройки, четвёрки и т.д., то задача сводится к перебору. Мда-а-а-а.
