Друг задал мне сегодня вопрос о проблеме назначения. Я нашел довольно простое решение, но я чувствую, что его можно сделать проще и быстрее. Ваша помощь будет оценена.
Проблема: Предполагая, что у меня есть N люди, мне нужно назначить их в зданиях M, каждое здание может содержать людей K. Не все люди готовы жить друг с другом, поэтому у меня есть матрица N * N клеток и 1, которая знаменует людей, которые хотят жить друг с другом. Если ячейка содержит 1, это означает, что я и J могут жить вместе. Очевидно, что матрица симметрична вокруг главной диагонали.
Мое решение следующее (псевдокод):
int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize)
{
int[] freePeople = findFreePeople(people);
if(freePeople) = 0
{
return people;
}
foreach(int person in freePeople)
{
for(int buildingIndex=0 to numBuildings)
{
if( CheckIfPersonFitsInBuilding(...) )
{
int[] tempPeople = people.Copy();
tempPeople[person] = buildingIndex;
int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize);
if(result != null)
{
return result;
}
}
}
}
return null;
}
Я просто расскажу о всех возможных механизмах, используя рекурсию. Я чувствую, что это может быть сильно оптимизировано, и я не говорю об эвристике, а о решении с гораздо меньшей степенью сложности.
- Существует ли формальная хорошо известная проблема, подобная этому?
- Есть ли лучший алгоритм?
Я думаю, что это может быть связано с стабильной проблемой брака, хотя я не уверен.
