今日、友人から課題の問題について質問がありました。非常に簡単な解決策を見つけましたが、それをより簡単かつ迅速に行うことができると感じています。あなたの助けをいただければ幸いです。
問題：私がN人いると仮定すると、それらをM棟に割り当てる必要があり、各建物にはK人を収容できます。すべての人がお互いに住むことをいとわないわけではないので、私はN * Nセルのマトリックスと、お互いに住むことをいとわない人々を示す1を持っています。セルに1が含まれている場合、それはIと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;
}
再帰を使用して可能なすべての配置をカバーします。これは大幅に最適化できると思います。ヒューリスティックではなく、はるかに複雑さの少ないソリューションについて話します。
- これに似た正式なよく知られた問題はありますか？
- より良いアルゴリズムはありますか？
よくわかりませんが、これは安定結婚問題に関係しているのではないかと思います。