农民需要通过自引用动物表循环的算法

Question

问题是:农场里有很多动物.每个动物都可以拥有任何数量的动物朋友,除了反社会动物 - 他们没有属于他们的朋友,但他们作为朋友属于其他正常动物.除了反社会动物之外,每只动物都是最不开心的动物朋友.反社会动物幸福的水平可以是任何东西.

一天早上,所有的动物都醒来,发现一些反社会动物的情绪发生了变化.农夫如何找出每只动物的幸福？

这是牧场的手(他们没有去农场学校):

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;
            }
        }
    }
}

但这不起作用,因为动物表不会按顺序跟随已经形成的动物朋友等级.动物可以随时互相交朋友!所以Animal(1)可能有动物(4000)作为朋友.动物(1)不会表现出准确的情绪,因为它会在动物(4000)的情绪自我更新之前检查动物(4000)的情绪.每天都有新动物被甩掉.我认为解决方案可能是一种常见的算法设计,但我无法找到它.我不相信我有正确的术语来准确搜索它.

非常感谢,如果这已经得到了答复,那就很抱歉!

添加:

这是一个可能的关系的贫民窟油漆图表:

反社会动物处于底层,没有属于他们的朋友.正常的动物在上面的其他地方.正常的动物友谊没有确切的结构,除了(正如塞巴斯蒂安指出的那样)不能有一个闭环(如果设计正确).

每周会有成千上万的动物被添加,处理速度是一个关键因素.

Answer 1

首先抓住所有反社会的动物,并命令他们从最开心到最开心.最大限度地将所有社交动物的快乐初始化(这使得一切变得更容易,因为您不必检测以前不快乐的动物何时变得更快乐).然后只需遍历列表并在友谊链中传播幸福级别:

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);
    }
}