9

问题：农场里有很多动物。每个动物都可以有任意数量的动物朋友，除了反社会动物——它们没有属于它们的朋友，但它们作为朋友属于其他正常动物。每只动物都和它最不快乐的动物朋友一样快乐，当然反社会动物除外。反社会动物的幸福水平可以是任何东西。

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

就农场工人而言（他们没有上过农民学校）：

一对多自引用表

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) 可能有 Animal(4000) 作为朋友。Animal(1) 不会显示准确的情绪，因为它会在 Animal(4000) 的情绪自行更新之前检查 Animal(4000) 的情绪。每天都有新的动物被丢弃。我认为解决方案可能是一种常见的算法设计，但我一直无法找到它。我不相信我有正确的术语来准确搜索它。

非常感谢，很抱歉，如果这已经得到回答！

添加：

这是可能的关系的 ghetto Paint 图表：

像一个无环图

反社会动物处于最底层，没有属于它们的朋友。正常的动物在上面的任何地方。正常的动物友谊没有确切的结构，除了（正如塞巴斯蒂安指出的那样）不可能有一个闭环（如果设计正确）。

每周将增加数十万只动物，处理速度是一个关键因素。

4

6 回答 6

5

首先抓住所有反社会动物，然后将它们从最不快乐到最快乐排序。将所有社交动物的快乐初始化为最大值（这使一切变得更容易，因为您不必检测以前不快乐的动物何时变得更快乐）。然后只需遍历列表并在友谊链上传播幸福水平：

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);
    }
}
于 2013-01-04T06:01:09.663 回答
4

好问题。所以，如果我理解正确，你基本上有带循环的有向图。您可以将每个动物视为一个节点（顶点），它具有其情绪所依赖的动物的出边，以及它影响情绪的动物的传入边。显然，反社会动物只会有传入的边缘。

如果你这样想，你会注意到两件事

1）您可以设计一个迭代算法，它将扫描所有动物，检查每个动物是否有任何仅针对反社会或已处理动物的传出边缘，如果是，我们计算动物的情绪，并将其标记为已处理. 如果没有，我们就在本次迭代中跳过它。

2）因为你的图中可以有循环，所以这个算法不会总是完成。也就是说，您可能有动物 A 取决于 B，B 取决于 C 和 C 取决于 A。如果您有简单的逻辑，就像您的情况一样，最低情绪获胜，您可以通过分配给所有人来检测和解决这些循环循环中的动物 - 在这种情况下 A，B，C 最低的共同情绪。

希望能帮助到你！

于 2013-01-04T05:17:40.580 回答
1

有趣的问题。如果我理解正确，如果是单向朋友（入站），每只动物的幸福就是所有人幸福的最小值。

如果是这样，那么挑战是动物的每个朋友的幸福都取决于他们的朋友等等，所以从哪里开始。

这是我乍一看的想法......

由于每天都有新的动物出现，所以您需要每天从新开始，并且需要从开始时幸福感最低的动物开始。很容易找到这些，然后将这种快乐传播给他们是朋友的所有动物，相应地调整这些快乐水平。然后取出所有调整过的动物并重复，直到没有更多的动物被调整过。一旦该幸福水平被完全传播，移动到下一个最高幸福水平并重复，直到处理完剩余的最高幸福水平。

一个有趣的观点是，如果有的话，哪些动物是反社会的并不重要。它们只是没有影响输入的动物，因此不会通过此过程进行调整。

我认为这会让你到达你想去的地方，而且编码应该一点也不难。

希望能帮助到你。

于 2013-01-04T05:30:34.297 回答
1
  • 如果反社会动物的情绪绝对最低，那么它的所有朋友和朋友的朋友都会继承其压倒一切的坏情绪。
  • 如果反社会动物的情绪是第二绝对最低的，那么它的所有朋友和朋友的朋友都将继承它的情绪，前提是他们还不是绝对最低的朋友/朋友的朋友。情绪动物
  • ...

因此，这建议使用以下算法：

首先，将社交动物的情绪设置为 MAX_MOOD，然后循环遍历反社交动物以增加情绪并递归更新其所有朋友和朋友的朋友的情绪。如果在递归期间您没有更新情绪，那么您可以停止递归，这就是为什么您会按照情绪增加的顺序循环：尽可能多地“阻止”未来的递归。

这类似于 Sebastian K 的“标记为已处理”，尽管您不需要保留已处理内容的单独列表，因为情绪本身包含此信息。这也将实现他对循环问题的解决方案，因为递归将遍历循环一次并停止。

于 2013-01-04T06:20:12.217 回答
1

已经有其他更合适的答案了，但我将把它作为一个有趣的思想实验扔出去——在数据库中做这件事会很麻烦，而且效率极低：

任何动物的幸福程度都是当前幸福的关系，被它的朋友“拉”或“推”。

因此，一只动物的幸福水平的变化会引起一波可能影响所有动物的调整浪潮。

将“友谊图”想象成一堆通过弹簧连接到其他盒子的盒子。盒子显然代表动物，弹簧对邻近动物产生“影响”。

拉一个盒子，一波运动从被移动的盒子里展开；这反过来最终会导致反向连锁反应——我让你更快乐，所以随着时间的推移，你最终会因为这种关系的影响让我更快乐（或更悲伤）。

“但它会永远自我调整，不会进入稳定状态！” 输入一个“摩擦”术语，它可以抵消微小的运动（比如在某个阈值下，“拉”不能克服悲伤/快乐的惯性）。

听起来很像 Craig whats-his-name 的 Boids 的集群行为。（需要参考） - 再次，我必须强调这对于你想要做的事情来说绝对不是最佳的，但我总是喜欢从多个角度看待一个问题。

于 2013-01-04T06:43:29.457 回答
1

听起来像家庭作业，但我会尝试一下，我从其他人那里得到一两个想法：

public void MoodCalculator()
{

 /** Reasoning:
 * 
 * The unidirectional cyclic graph can be also expressed as multiple friend 
 * trees where
 * anti-social animal is the root node of a friend tree. Because a social animal's
 * mood is that of its lowest mood friend this means that regardless of the 
 * tree depth of an animal
 * it's mood is that of the mood of the lowest mood antisocial animal 
 * who's tree it is a member of.  
 * 
 * */

  SortedList<int, List<Animal>> moodGroups = new SortedList<int, List<Animal>>();

  HashSet<Animal> allAnimals = new HashSet<Animal>();

  //get all antisocial animals and group according to mood
  //work from low to high mood
  forach(Animal a in GetAllAntiSocialAnimalsFromDb()) 
  {
     if(!moodGroups.ContainsKey(a.Mood)) moodGroups.Add(a.Mood, new List<Animal>());
     moodGroups[a.Mood].Add(a);
  }

  foreach(var item in moodGroups)
  {
     //add our root antisocial animals to master group
     foreach(Animal a in item.Value) allAnimals.Add(a);

     //recurse over tree starting at antisocial animal roots
     TreeRecurse(item.Value, allAnimals, item.Key);
  }


 }

 public void TreeRecurse(List<Animal> children, List<Animal> allAnimals, int mood)
 {
    //can look for list as we are just grouping everything and don't care about tree 
    //structure
    //db call should only get unique/distinct animals
    List<Animal> parentAnimals = GetParentAnimalsOfChildAnimalListFromDb(children);
    //remove animals from from parents if they are already in the allAnimal set
    //working from low mood to high we can ignore animals that have appeared in a 
    //lower mood tree
    parentAnimals.RemoveAll(a => allAnimals.Contains(a));
    //add animals to allAnimals and set mood
    foreach (Animal a in parentAnimals)
    {
       a.Mood = mood;
       allAnimals.Add(a);
    }
    //end recurse
    if (parentAnimals.Count == 0) return;
    //recurse
    else TreeRecurse(parentAnimals, allAnimals, mood);
   }
于 2013-01-04T10:58:20.513 回答