最小距离的电梯算法

Question

我有一个单独的电梯的建筑物,我需要找到这个电梯的算法.我们得到了这种形式的对象列表:{i->j},i居民想要乘坐电梯的楼层在哪里,是j他想要下楼的楼层.

无数人可以同时使用电梯,与人们待在电梯里的时间无关.电梯从一楼开始.

我在网上查了一下,发现了"电梯算法",但它并没有真正帮助我.它说我应该一路向上,然后一路向下.但考虑一个居民想要从1到100,而另一个居民想要从50到49.使用上述算法,它将需要151层的距离.如果我改为遵循这条道路:1-> 50-> 49-> 100,它只需要102层,这样更好.

我应该使用什么算法？

Answer 1

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

首先检查最短寻道时间与scan、cscan 等。

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

就您而言，这实际上取决于请求是静态的还是动态的。如果你想最小化方差，请使用 scan/cscan 等。