最小距离的电梯算法
我有一个电梯的建筑，我需要为这个电梯找到一个算法。 我们得到这种形式的对象列表： {i->j} ，其中i是居民想要乘坐电梯的地板，而j是他想要躺下的地板。
无数的人可以同时使用电梯，这与人们在电梯中逗留多久无关。 电梯从一楼开始。
我在网上查了一下，发现了“电梯算法”，但它并没有真正帮助我。 它说我应该一路走下去，然后一路走下去。 但考虑一个居民想要从1到100，另一个居民想要从50到49.使用上述算法，它将需要151个楼层的距离。 如果我按照这条路线：1-> 50-> 49-> 100，则只需要102层，这样更好。
我应该使用什么算法？
这是将这个问题作为基于时间的整数程序的一种方法。 （产生所有约束可能看起来像是矫枉过正，但它保证产生最佳解决方案）
假设电梯从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 ，它是整个行程完成的时间。 它是每个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问题之后，可以使用每个t的每个DIR_t的值来跟踪确切的行程。
有一个多项式时间动态程序，其运行时间不取决于楼层数量。 如果我们贪婪地提起乘客并让他们等待，那么相关的状态是电梯访问过的楼层的间隔（因此乘客被捡起），电梯最近拾取或下落的楼层，以及两个可选的价值观：最低层是为了降低当前内部乘客的目的而访问的最低层，最高层。 所有这种状态都可以通过五位乘客的身份加上恒定数量的位来描述。
我很确定这里有改进的空间。
您的问题反映了磁盘头调度算法。
先查看最短寻找时间vs扫描，cscan等。
有些情况下，sstf获胜，但是如果是50到10，并且你也有2到100,3到100,4到100,5到100,6到100等等。你可以看到你增加了所有开销的其他人。 另外，如果传入请求的寻道时间较短，则可能发生饥饿（与进程调度类似）。
在你的情况下，这取决于请求是静态的还是动态的。 如果您想最小化差异，请使用扫描/ cscan等。
链接地址: http://www.djcxy.com/p/19477.html