我正在构建一个应用程序，该应用程序应该从有限的任务池中为用户提取任务。问题是我想要：
- 用户不会两次获得相同的任务，
- 在一段时间过去之前，用户不会获得与他的朋友（在应用程序中）相同的任务。
总结一下我的问题，我需要从池中提取最不常见的任务。
有人可以参考我找到最不常见的东西（LFU）的已知算法。我还需要理论方面的知识，所以如果有人知道一些关于这方面的文章或研究论文（来自《科学美国人》等知名杂志），那就太好了。
问问题
812 次
4 回答
2
为了获得最不常用的任务，只需给每个任务一个计数器，计算它被使用了多少次。然后搜索计数器值最低的任务。
为了获得一群朋友最不常用的任务，您可以为每个用户存储他/她完成的任务（以及次数）。无论如何，此信息可能很有用。然后，当需要为用户选择新任务时，可以轻松创建用户及其所有朋友使用过的任务及其频率的（临时）组合列表，并按频率排序。这不是很贵。
于 2012-05-04T14:45:08.487 回答
1
根据您的 2 个要求，我看不出“最少”使用的任务与此有什么关系。你说你想要不重复的任务。
选项 1：
您使用什么容器来容纳所有任务？假设它是一个列表，当您或您的朋友选择一个任务时，将该任务移至列表末尾（与那里的任务交换）。现在您已将初始列表拆分为 2 个子列表。第一部分包含未使用的任务，第二部分包含已使用的任务。跟踪分隔 2 个列表的枢轴/索引。
现在，每次您或您的朋友选择一个新任务时，都会从第一个子列表中选择它。然后将其移动到第二个子列表并更新枢轴。
选项 2： 如果您最终重复任务，但首先选择那些选择时间最少的任务，那么您可以使您的容器成为最小堆。为每个任务添加一个使用计数器，并基于此将它们添加到堆中。提取任务并增加其使用计数器，然后将其放回堆中。这是一个很好的解决方案，但根据程序的简单程度，您甚至可以使用循环缓冲区。
很高兴了解更多关于您正在构建的内容:)
于 2012-05-04T14:54:05.457 回答
0
一个好的开始是 Edmond Blossom V 算法，用于在一般图中实现完美的最小匹配。如果您有二分图，则可以查找 Floyd-Warshall 算法以找到最短路径。也许你也可以使用拓扑搜索，但我不知道，因为这些算法真的很难学习。
于 2012-05-04T14:45:29.973 回答
0
我认为您需要的结构是min-heap。它允许提取 O(Log(n)) 中的最小值，并且还允许您增加 O(Log(n)) 中的项目的值。
于 2012-05-04T15:03:01.380 回答