最小距离的电梯算法

Question

我有一栋只有一部电梯的大楼，我需要为这部电梯找到一个算法。我们得到一个这种形式的对象列表：{i->j}，其中i是居民想要乘电梯的楼层，j是他想要下楼的楼层。

无限多的人可以同时使用电梯，人们在电梯里停留多长时间并不重要。电梯从一楼开始。

我在网上查了一下，发现了“电梯算法”，但它对我没有真正的帮助。它说我应该一直往上走然后一直往下走。但考虑一下，当一个居民想要从1到100，而另一个居民想要从50到49。使用上面的算法，它将需要151层的距离。如果我遵循这样的路径: 1->50->49->100，它只需要102层，这更好。

我应该使用什么算法？

Answer 1

这里有一种方法可以将这个问题表述为一个基于时间的整数程序。(生成所有约束可能看起来有点过头，但它可以保证生成最优解决方案)

假设电梯从floor F到F+1或F-1需要1个单位的时间。

洞察:我们使用的事实是，在任何时候t，只有一个决定要做出。是往上还是往下。这就是我们的问题的决策变量。如果电梯在时间t向上移动，DIR_t = +1，否则为-1。

我们希望最小化所有乘客到达目的地的时间。

此表使其更清晰

Time    FLOOR_t   Dir_t
1        1          1
2       2           1
3       3           1
4       4           1
...    ...          ...
49      49          1
50      50          -1
51      49          1
52      50          1
...     
100     99          1
101     100         NA

现在，让我们把乘客带进来。有P个乘客，每个人都想从SF到EF (他们的起点楼层到终点楼层，他们的目的地)。

因此，我们为每个乘客p提供了(SF_p, EF_p)。

约束条件

我们知道电梯在时间t所在的楼层是

 F_t = F_t-1 + DIR_t-1

(F0 = 0，DIR_0 = 1，F1 =1只是开始。)

现在，假设ST_p是乘客p开始他们的电梯之旅的时刻。假设ET_p是乘客p结束他们的电梯之旅的时刻。请注意，SF和EF是提供给我们的输入参数，但ST和ET是IP在求解时将设置的变量。也就是说，楼层是给我们的，我们要跟上时代。

   ST_p = t if F_t = SF_p  # whenever the elevator comes to a passenger's starting floor, their journey starts.       
   ET_p = t if F_t = EF_p AND ST_p > 0 (a passenger cannot end their journey before it commenced.)
   This can be enforced by introducing new 0/1 indicator variables.

   ETp > STp # you can only get off after you got on

最后，让我们介绍一个数字T，它是完成整个trips集合的时间。它是每个p的所有ET的最大值。这是需要最小化的。

   T > ET_p for all p # we want to find the time when the last passenger gets off.

公式

把所有这些放在一起：

   Min T
   
   T > ET_p for all p
   F_t = F_t-1 + DIR_t-1
   ETp > STp # you can only get off after you got on 
   ST_p = t if F_t = SF_p  # whenever the elevator some to a passenger's starting floor, their journey starts.
   ET_p = t if F_t = EF_p AND ST_p > 0
   ET_p >= 1 #everyone should end their journey. Otherwise model will give 0 as the obj function value.
   DIR_t = (+1, -1) # can be enforced with 2 binary variables if needed.

现在，在解决了这个IP问题之后，可以使用每个DIR_t的每个t的值来跟踪准确的行程。

Answer 2

有一个多项式时间动态规划，它的运行时间与楼层数无关。如果我们贪婪地搭载乘客并让他们等待，那么相关的状态是电梯访问过的楼层的间隔(因此乘客被搭载)，电梯最近升降的楼层，以及两个可选值:为了在里面放下乘客而必须访问的最低楼层和最高楼层。所有这种状态都可以通过五个乘客的身份加上恒定位数来描述。

我很确定这方面还有改进的空间。

Answer 3

您的问题反映了磁盘头调度算法。

查看shortest seek time first vs scan, cscan, etc。

在某些情况下，sstf会胜出，但如果是50比10，并且您也有2比100、3比100、4比100、5比100、6比100等等。您可以看到您将开销添加到所有其他人。此外，如果传入请求的寻道时间较短，则可能会发生starvation (类似于进程调度)。

在您的情况下，这实际上取决于请求是静态的还是动态的。如果您想要最小化差异，请使用scan/cscan等。