从较大的集合中进行选择时最小化一组 4 中更改次数的算法
Algorithm to minimize number of changes in a set of 4 when choosing from a larger set
我在一台机器上有 4 个插槽，我有一个订单告诉我要在这台机器上放置某些物品。假设有 100 件商品，我有 4 个槽，订单如下所示：
4 8 3 3 8 8 8 10 2 7.
我需要能够以最少的货位更改来完成此订单。例如，对于上面的输入，我应该将编号为 8 的物品放在机器上，这样我就不必将其放回原处再拿起另一个。
问题是我无法在下一个订单实际到达我之前检查它。所以这是一种猜谜游戏。谁有我可以查找并应用于该项目的算法？
听起来您正在寻找类似 page replacement algorithms 的内容。当您到达机器上尚未出现的订单时，这很像页面未命中。您必须逐出四个缓存页面之一，以便为您现在需要的页面腾出空间。
有很多选择，它们都需要权衡取舍。通常，您对订单流的了解或合理假设越多，您可以接受的开销越大，避免不必要的页面丢失的机会就越大。
选择前考虑几个问题：
- 在给定的订单流中，您愿意假设订单的顺序和频率如何？假设均匀分布和随机顺序是完全有效的。
- 对于您遇到的大多数订单流，这些假设是否往往成立，或者是否存在几种不同的模式？
- 订单流通常持续多长时间？
如果这没有帮助，请尝试实施像 LRU 和时钟这样的一对，并针对实际订单流进行测试。要评估它们的准确性，您可以与特定流的理论最佳操作顺序进行比较。此算法称为 OPT，仅当您可以访问完整流时才有效。
我在一台机器上有 4 个插槽，我有一个订单告诉我要在这台机器上放置某些物品。假设有 100 件商品，我有 4 个槽，订单如下所示：
4 8 3 3 8 8 8 10 2 7.
我需要能够以最少的货位更改来完成此订单。例如，对于上面的输入，我应该将编号为 8 的物品放在机器上，这样我就不必将其放回原处再拿起另一个。
问题是我无法在下一个订单实际到达我之前检查它。所以这是一种猜谜游戏。谁有我可以查找并应用于该项目的算法？
听起来您正在寻找类似 page replacement algorithms 的内容。当您到达机器上尚未出现的订单时，这很像页面未命中。您必须逐出四个缓存页面之一，以便为您现在需要的页面腾出空间。
有很多选择，它们都需要权衡取舍。通常，您对订单流的了解或合理假设越多，您可以接受的开销越大，避免不必要的页面丢失的机会就越大。
选择前考虑几个问题：
- 在给定的订单流中，您愿意假设订单的顺序和频率如何？假设均匀分布和随机顺序是完全有效的。
- 对于您遇到的大多数订单流，这些假设是否往往成立，或者是否存在几种不同的模式？
- 订单流通常持续多长时间？
如果这没有帮助，请尝试实施像 LRU 和时钟这样的一对，并针对实际订单流进行测试。要评估它们的准确性，您可以与特定流的理论最佳操作顺序进行比较。此算法称为 OPT，仅当您可以访问完整流时才有效。