最佳的座位安排算法 [英] Optimal Seating Arrangement Algorithm
问题描述
有25条凳子在一排。客户谁进入酒吧遵循以下两条规则：
There are twenty-five bar stools in a row. Customers who enter the bar follow these two rules:
- 在客户将永远在座位上坐距离最远的任何其他客户。
- 在顾客永远坐在旁边的另一位客户。
使用这两个规则，应该在哪里你把第一个客户，使客户的最大数量可以坐在酒吧？
Using these two rules, where should you place the first customer so that the maximum number of customers could sit at the bar?
我可以解决它在25个凳子条件。但我不能想出一个通用算法n个凳子。
I can solve it in 25 stools condition. But I can not figure out a general algorithm for n stools.
推荐答案
由它这种声音几乎完全一样的小便器协议国际选择（ICUP）的兰德尔·门罗写了一个很好的分析，包括一个封闭的形式方程和最佳小便池计数的阴谋。看完这个答案的其余部分之前，您应该阅读他的文章。
By the sound of it this is almost exactly the same as the International Choice of Urinal Protocol (I.C.U.P.) which Randall Munroe has written up an excellent analysis of, including a closed form equation and a plot of optimal urinal counts. You should read his article before reading the rest of this answer.
在帖子兰德尔提到：
[I] F你进入一间带空置小便池的一排一个尴尬的数字，而不是采取月底者之一，你可以把一个倒行的方式三分之一。这将打破别扭行分成两行最佳折一个最坏的情况下进入一个最好的情况之一。
[I]f you enter a bathroom with an awkward number of vacant urinals in a row, rather than taking one of the end ones, you can take one a third of the way down the line. This will break the awkward row into two optimal rows, turning a worst-case scenario into a best-case one.
虽然他没有进入较详细，但它暗示了我们正在努力做的事情。如果我们有小便池的尴尬号码（或凳子，在我们的例子），我们可以尝试座位第一人在座椅使得它们成为两个不同的最优子组的末端。
While he doesn't go into more detail than that, it hints at what we're trying to do. If we have an awkward number of urinals (or stools, in our case), we can attempt to seat the first person in a seat such that they become the end of two different optimal sub-groups.
7席，基本选择行为网这样的：
For 7 seats, the basic selection behavior nets this:
1 _ _ 3 _ _ 2
留下四个空座。但是，如果不是我们坐的第一个人在三个位置上，我们得到最佳的3和5分团，由一个增加了我们可能的乘客。
Leaving four unoccupied seats. But if instead we seat the first person at position three, we get optimal 3 and 5 sub-groups, increasing our possible occupants by one.
3 _ 1 _ 4 _ 2
25的基本行为同样是次优的，从而导致9 / 25ths入住前的的尴尬的：
1 _ _ 6 _ _ 4 _ _ 7 _ _ 3 _ _ 8 _ _ 5 _ _ 9 _ _ 2
但我们可以容纳人在第9位，创造最佳的9月17日亚群，像这样：
But we can seat someone at position 9, creating optimal 9 17 sub-groups, like so:
3 _ 8 _ 5 _ 9 _ 1 _ 10 _ 6 _ 11 _ 4 _ 12 _ 7 _ 13 _ 2
通往最佳13 / 25ths入住。
Leading to optimal 13/25ths occupancy.
更一般地，相信发现比席位数最大最佳数量小，和安放的第一人那里（在25的情况下，这是17，这是从另一个方向等效第九）将始终最大化的数量可占用椅子。在最坏的情况下，像25，这相当于 CEIL（N / 3）这兰德尔提及。
More generally, I believe finding the largest optimal number smaller than the number of seats, and seating the first person there (in the 25 case, that's 17, which is equivalently 9th from the other direction) will always maximize the number of occupiable chairs. In worst-case scenarios, like 25, this is equivalent to ceil(n/3) which Randall mentions.
在一般情况下（既不是最好的也不是最差的使用基本座位行为），我们不能总是只座位的第一人，因为我们只能创建一个最佳群，留下其他地方低于最佳达到50％入住。因此，我们取最大的最佳分组，以最小化的次优的席位数。例如，对于20个席位，我们把17创造了17 4组，优化了尽可能多的席位越好，只有两个留在一排空的：
In average cases (neither best nor worst using the basic seating behavior), we cannot always reach 50% occupancy by only seating the first person, because we can only create one optimal subgroup, leaving the other somewhere less than optimal. Therefore we take the largest optimal subgroup in order to minimize the number of sub-optimal seats. For instance, for 20 seats, we take 17 and create a 17 4 group, which optimizes as many seats as possible, leaving only two in a row empty:
2 _ 7 _ 4 _ 8 _ 3 _ 9 _ 5 _ 10 _ 1 _ _ 6
四组实际上是在技术上既是最好的和最坏的情况，但希望你能看到的格局将如何扩展。
The four group is actually technically both a best and worst case, but hopefully you can see how the pattern would scale.
这篇关于最佳的座位安排算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
