python - 写优化函数

Question

我正在尝试编写一个网球预订系统，但遇到了这个问题。假设您有一些球员，他们对球场编号、日期和时间有自己的偏好。此外，每个玩家都会排名，所以如果有天/小时时段并且有多个玩家有了这个插槽的偏好，应该选择具有最高优先级的那个。我正在考虑使用一些优化算法来解决这个问题，但我不确定最好的成本函数和/或算法是什么。有什么建议吗？还有一件事我更愿意使用 Python，但也欢迎一些与语言无关的建议。谢谢!

编辑:

一些说明-

优先级高的获胜，失败者移至最近的位置，相当灵活的时间段问题是的，最大化获得他们最喜欢的时间的人数

Answer 1

基本算法

我会根据排名对玩家进行排序，因为排名高的总是排在低位。然后你从等级最高的玩家开始，给他他想要的(如果他真的是最高的，他总是赢，所以你也可以给他任何他想要的)。然后我将从第二高的开始。如果他要求的东西已经被最高层拿走了，试着在附近找一个空位，把这个空位分配给他。现在是第三高的。如果他要求的东西已经被最高的那个拿走了，就把他移到附近的一个位置。如果这个位置已经被第二高的人占据了，就把他移到更远的位置。继续所有其他玩家。

需要考虑的一些调整:

如果多个玩家可以有相同的排名，你可能需要实现一些“公平”。如果您对所有排名相同的玩家进行排序，则他们之间的顺序将是随机的，例如使用快速排序。你可以获得一些公平，如果你不是对玩家进行，而是对排名进行排名。您从最高级别和该级别的第一位玩家开始。处理他的第一个请求。但是，在您处理他的第二个请求之前，先处理排名最高的下一个玩家的第一个请求，然后再处理排名最高的第三个玩家的第一个请求。该算法与上述相同，但假设您有 10 个玩家，玩家 1-4 排名最高，玩家 5-7 排名较低，玩家 8-10 排名非常低，并且每个玩家发出 3 个请求，您将它们处理为

Player 1 - Request 1
Player 2 - Request 1
Player 3 - Request 1
Player 4 - Request 1
Player 1 - Request 2
Player 2 - Request 2
:

这样你就有了一些公平。也可以每次在一个排序类中随机选择，这样也能提供一定的公平性。

您甚至可以跨等级实现公平。例如。如果你有 4 个等级，你可以说

Rank 1 - 50%
Rank 2 - 25%
Rank 3 - 12,5%
Rank 4 - 6,25%

(只是示例值，您可以使用与始终乘以 0.5 不同的键，例如乘以 0.8，导致数字减少得更慢)

现在您可以说，您从 Rank 1 开始处理，但是一旦完成了所有 Rank 1 请求的 50%，您就进入 Rank 2 并确保他们的 25% 的请求得到满足，依此类推。这样即使是 Rank 4 用户也可以赢得 Rank 1 用户，在某种程度上打败了初始算法，但是您提供了一些公平性。即便是四阶玩家有时也能得到他的要求，他不会“跑路”。否则，Rank 1 玩家与 Rank 4 玩家在同一时间安排每个请求将确保 Rank 4 玩家永远没有机会获得单个请求。这样他至少有很小的机会得到一个。

在你确定每个人都处理了他们的最小百分比之后(等级越高，这个越多)，你回到顶部，再次从等级 1 开始处理他们剩下的请求，然后是其余的Rank 2 请求等等。

最后但并非最不重要的一点:您可能想要定义最大插槽偏移量。如果一个槽被占用，应用程序应该搜索最近的仍然空闲的槽。但是，如果最近的插槽距离很远怎么办？如果我在星期一下午 4 点请求一个时段，而应用程序发现下一个空闲时段是星期三上午 9 点，那对我来说并没有什么帮助，不是吗？星期三我可能根本没有时间。因此，您可以将时段搜索限制在同一天，并说时段最多可以休息 3 小时。如果在该范围内找不到插槽，则取消请求。在这种情况下，您需要通知玩家“很抱歉，我们无法为您找到任何附近的空位；请在其他日期/时间申请一个空位，我们将看看是否可以在那里为您找到合适的空位”。