问题：农场里有一大堆动物.每只动物可以拥有任何数量的动物朋友,除了反社会动物 – 他们没有属于他们的朋友,但他们属于其他正常动物作为朋友.当然,每只动物和最不幸福的动物朋友一样快乐,除了反社会动物.反社会动物幸福的水平可以是什么.
一天早晨,所有的动物醒来,发现一些反社会动物的心情已经改变了.农民如何计算出每只动物的幸福？
这就是农场的手(他们没有去农民学校)：
DataTable animals = Select_All_Animals();
foreach (DataRow animal in animals.Rows)
{
int worstMood = 10; //Super Happy!
DataTable friendRecords = Select_Comp_Animal_AnimalFriend((int)animal["AnimalID"]);
foreach (DataRow friend in friendRecords.Rows)
{
DataTable animalFriends = Select_AnimalFriend((int)friend["AnimalID_Friend"]);
foreach (DataRow animalFriend in animalFriends.Rows)
{
int animalMood = Get_Animal_Mood((int)animalFriend["Mood"]);
if (animalMood < worstMood)
{
worstMood = animalMood;
}
}
}
}
但这不会奏效,因为动物桌不会顺序地追随已经形成的动物朋友层次结构.动物随时可以互相交朋友！所以动物(1)可能有Animal(4000)作为朋友.动物(1)不会显示准确的心情,因为它会在Animal(4000)的心情更新之前检查Animal(4000)的心情.而新的动物每天都在掉下去.我认为解决方案可能是一个常见的算法设计,但我还没有找到它.我不相信我有正确的术语来准确搜索它.
感谢一堆,抱歉,如果这已经回答了！
添加：
这是一个贫民窟可能关系的油漆图：
反社会动物处于底层,没有属于他们的朋友.正常动物在其他地方.没有正常的动物友谊的确切结构,除了(如塞巴斯蒂安指出的),不能有闭环(如果设计正确).
每周增加数千只动物,加工速度是关键要素.
解决方法
首先抓住所有的反社会动物,并命令他们从最不开心到最开心.将所有社会动物的幸福最大限度地初步化(这使得一切都更容易,因为您不必检测以前不快乐的动物何时变得更快乐).然后只是迭代列表,传播幸福水平的友谊链：
void UpdateFarm()
{
// Start with a list of antisocial animals from least to most happy.
var antisocialAnimals = GetAntisocialAnimals().OrderBy(x => x.Happiness);
// Initialise the social animals to the global maximum. Note the
// global maximum is the happiest antisocial animal. This is done to
// avoid the case where an antisocial animal's happiness has increased,// so some of the social animals are too unhappy.
var maxHappiness = antisocialAnimals.Last().Happiness;
var socialAnimals = GetSocialAnimals();
foreach (var socialAnimal in socialAnimals)
socialAnimal.Happiness = maxHappiness;
// Now iterate from least to most happy,propagating up the friend chain.
foreach (var antisocialAnimal in antisocialAnimals)
UpdateFriends(antisocialAnimal);
}
// To propagate a happiness change,we just find all friends with a higher
// happiness and then lower them,then find their friends and so on.
void UpdateFriends(Animal animal)
{
var friends = GetFriends(animal); // Friends with this animal,not friends of.
foreach (var friend in friends.Where(x => x.Happiness > animal.Happiness))
{
friend.Happiness = animal.Happiness;
// Since this friend's happiness has changed,we now need to update
// its friends too.
UpdateFriends(friend);
}
}
