编程 2

每一种程序员对着电梯都想过调治算法吧编程,本身入手C

By admin in 编程 on 2019年9月24日

电梯调度有很多种模式,参见

不管你是在北上广还是在港澳台,甚至三四线城市,凡是有规模的地区,高楼比比皆是。

1.1先来先服务算法

先来先服务(FCFS-First Come First
Serve)算法,是一种随即服务算法,它不仅仅没有对寻找楼层进行优化,也没有实时性的特征,它是一种最简单的电梯调度算法。它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单,且每个乘客的请求都能依次地得到处理,不会出现某一乘客的请求长期得不到满足的情况[12]。这种方法在载荷较轻松的环境下,性能尚可接受,但是在载荷较大的情况下,这种算法的性能就会严重下降,甚至恶化。人们之所以研究这种在载荷较大的情况下几乎不可用的算法,有两个原因:

任何调度算法在请求队列长度为1时,请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响,而且实现这种算法极其简单。

先来先服务算法可以作为衡量其他算法的标准。

1.2最短寻找楼层时间优先算法

最短寻找楼层时间优先(SSTF-Shortest Seek Time First)
[14]算法,它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。在重载荷的情况下,最短寻找楼层时间优先算法的平均响应时间较短,但响应时间的方差较大,原因是队列中的某些请求可能长时间得不到响应,出现所谓的“饿死”现象。

不管是写字楼,还是大型商城,让你最头痛的就是乘电梯,尤其是在赶时间的时候。

1.3扫描算法

扫描算法是一种按照楼层顺序依次服务请求,它让电梯在最底层和最顶层之间连续往返运行,在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。它进行寻找楼层的优化,效率比较高,但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题,在这个算法中,每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的,所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成,免去了电梯频繁的来回移动[2]。

扫描算法的平均响应时间比最短寻找楼层时间优先算法长,但是响应时间方差比最短寻找楼层时间优先算法小,从统计学角度来讲,扫描算法要比最短寻找楼层时间优先算法稳定。

1.4 LOOK 算法

LOOK算法[18]是扫描算法的一种改进。对LOOK算法而言,电梯同样在最底层和最顶层之间运行。但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向,而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

编程 1

1.5 SAFT 算法

SATF(Shortest Access Time
First)[15,19]算法与SSTF算法的思想类似,唯一的区别就是SATF算法将SSTF算法中的寻找楼层时间改成了访问时间。这是因为电梯技术发展到今天,寻找楼层的时间已经有了很大地改进,但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。SATF算法考虑到了电梯运行过程中乘客上梯时间的影响。

上面是常见的电梯调度模式,这里我们写的是第二种模式,这是一个简化的版本。

运行原理:电梯会将目前所有的请求中最高的楼层请求查出来,通过与电梯所在楼层进行对比,确定电梯的运行方向,是向上运行(方法getRequest1)或者是向下运行(方法getRequest),同时每到一层都会执行下面的操作:

1.这层是否有人请求,如果有,那么要求设置目的层。

2.确定这层是某个请求的目的层,如果是,就将相应的请求归零。

缺陷:将请求单纯简化为层数,其实实际中还会出现请求的方向,这个下次再解决,还有其他的一些。

代码如下:

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace 电梯调度算法{    struct elevatorRequest    {        public int start;        public int end;        public int rFlag;    }    class elevator    {        public static int count = 0;        public static int now = 0;        elevatorRequest[] sRequest = new elevatorRequest[12];        public static int runNow = 0;        public void run()        {            while (count > 0)            {                getRequest();                getRequest1();            }        }        public void setDirect()        {            int max = 0;            int ns = count;            if (ns != 0)            {                max = sRequest[0].start;                int i = 0;                while (ns > 0)                {                    if (max < sRequest[i].end || max < sRequest[i].start)                    {                        max = sRequest[i].end > sRequest[i].start ? sRequest[i].end : sRequest[i].start;                    }                }                if(max>runNow)                {                    getRequest();                }                else                {                    getRequest1();                }            }        }        public void getRequest1()        {            if (count > 0)            {                Console.WriteLine("电梯开始方向运行");                for (int i = 11; i >= 0; i--)                {                    Console.WriteLine("-----" + i + "----");                    int j = isEnd;                    if (j != 0)                    {                        Console.WriteLine("完成了从" + sRequest[j].start + "层到" + sRequest[j].end + "的请求");                        runNow = i;                        count--;                        sRequest[j].start = 0;                        sRequest[j].end = 0;                    }                }                if (count == 0)                {                    Console.WriteLine("请求执行完毕,电梯停止运行");                    Console.WriteLine("电梯停留在" + runNow + "层");                }            }            else            {                Console.WriteLine("请求执行完毕,电梯停止运行");                Console.WriteLine("电梯停留在" + runNow + "层");            }        }        public void getRequest()        {            if (count > 0)            {                //int next = getNextFloor();                for (int i = 0; i < 12; i++)                {                    Console.WriteLine("-----" + i + "----");                    if (sRequest[i].start != 0)                    {                        Console.WriteLine("响应了" + i + "层的请求");                        Console.WriteLine("请输入要去的楼层");                        int e;                        string str = Console.ReadLine();                        e = Convert.ToInt32;                        setRequest;                    }                    int j = isEnd;                    if (j != 0)                    {                        Console.WriteLine("完成了从" + sRequest[j].start + "层到" + sRequest[j].end + "的请求");                        runNow = i;                        count--;                        sRequest[j].start = 0;                        sRequest[j].end = 0;                    }                }                if (count == 0)                {                    Console.WriteLine("请求执行完毕,电梯停止运行");                    Console.WriteLine("电梯停留在" + runNow + "层");                }            }            else            {                Console.WriteLine("请求执行完毕,电梯停止运行");                Console.WriteLine("电梯停留在" + runNow + "层");            }        }        public int isEnd(int i)        {            for (int j = 0; j < 12; j++)            {                if (i == sRequest[j].end)                {                    return j;                }            }            return 0;        }        public int getNextFloor()        {            int min = sRequest[0].start - runNow > 0 ? (sRequest[0].start - runNow) : (runNow - sRequest[0].start);            for (int i = 0; i < now; i++)            {                if (min > sRequest[i].start - runNow)                {                    min = sRequest[i].start - runNow;                }            }            return min + runNow;        }        public void setRequest(int i, int e)        {            sRequest[i].end = e;            if (i > e)            {                sRequest[i].rFlag = 0;            }            else            {                sRequest[i].rFlag = 1;            }        }        public void setRequest(int s)        {            count++;            sRequest[s].start = s;        }        public void show()        {            for (int i = 0; i < 12; i++)            {                if (sRequest[i].end != 0)                {                    string s = "";                    if (sRequest[i].rFlag > 0)                    {                        s = "上";                    }                    else                    {                        s = "下";                    }                    Console.WriteLine("我要从" + sRequest[i].start + "层到" + sRequest[i].end + "层,方向向" + s);                }            }        }    }    class Program    {        static void Main(string[] args)        {            elevator es = new elevator();            es.setRequest(1);            es.setRequest(10);            es.setRequest(7);            es.run();            es.show();            es.setRequest(9);            es.setRequest(4);            es.run();            Console.ReadKey();        }    }}

运行结果:

编程 2

每天早上,那些差5分钟就迟到的程序员,在等电梯时,一般会做两件事:

第一,在心里骂电梯慢;

第二,在心里暗算着电梯调度如何优化;

前者可能是写字楼里上班族惯有的精神类疾病,但后者肯定是程序员的职业病。

本文对“骂电梯”不给予任何指导性建议。

但说起电梯调度算法,我觉得还是可以给大家科普一下,好为大家在等电梯之余,打发时间而做出一点贡献。(电梯调度算法可以参考各种硬盘换道算法,下面内容整理自网络)

如果你依然在编程的世界里迷茫,不知道自己的未来规划,可以加入JAVA架构学习交流群:614478470
里面可以与大神一起交流并走出迷茫。进群免费领取学习资料,看看前辈们是如何在编程的世界里傲然前行!群里不停更新最新的教程和学习方法(进群送JAVA架构视频资料),有想学习JAVA的,或是转行,还有工作中想提升自己能力的,正在学习的小伙伴欢迎加入学习

1.1 先来先服务算法

先来先服务(FCFS-First Come First
Serve)算法,是一种随即服务算法,它不仅仅没有对寻找楼层进行优化,也没有实时性的特征,它是一种最简单的电梯调度算法。

它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单,且每个乘客的请求都能依次地得到处理,不会出现某一乘客的请求长期得不到满足的情况。

这种方法在载荷较轻松的环境下,性能尚可接受,但是在载荷较大的情况下,这种算法的性能就会严重下降,甚至恶化。

人们之所以研究这种在载荷较大的情况下几乎不可用的算法,有两个原因:

任何调度算法在请求队列长度为1时,请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响,而且实现这种算法极其简单。

先来先服务算法可以作为衡量其他算法的标准。

1.2 最短寻找楼层时间优先算法

最短寻找楼层时间优先(SSTF-Shortest Seek Time
First)算法,它注重电梯寻找楼层的优化。

最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。

这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

在重载荷的情况下,最短寻找楼层时间优先算法的平均响应时间较短,但响应时间的方差较大,原因是队列中的某些请求可能长时间得不到响应,出现所谓的“饿死”现象。

1.3 扫描算法

扫描算法
是一种按照楼层顺序依次服务请求,它让电梯在最底层和最顶层之间连续往返运行,在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

它进行寻找楼层的优化,效率比较高,但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题,在这个算法中,每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的。

所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成,免去了电梯频繁的来回移动。

扫描算法的平均响应时间比最短寻找楼层时间优先算法长,但是响应时间方差比最短寻找楼层时间优先算法小,从统计学角度来讲,扫描算法要比最短寻找楼层时间优先算法稳定。

1.4 LOOK 算法

LOOK
算法是扫描算法的一种改进。对LOOK算法而言,电梯同样在最底层和最顶层之间运行。

但当 LOOK
算法发现电梯所移动的方向上不再有请求时立即改变运行方向,而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

1.5 SATF 算法

SATF(Shortest Access Time First)算法与 SSTF
算法的思想类似,唯一的区别就是 SATF 算法将 SSTF
算法中的寻找楼层时间改成了访问时间。

这是因为电梯技术发展到今天,寻找楼层的时间已经有了很大地改进,但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。

SATF 算法考虑到了电梯运行过程中乘客上梯时间的影响。

2.1 最早截止期优先调度算法

最早截止期优先(EDF-Earliest Deadline
First)调度算法是最简单的实时电梯调度算法,它的缺点就是造成电梯任意地寻找楼层,导致极低的电梯吞吐率。

它与 FCFS 调度算法类似,EDF 算法是电梯实时调度算法中最简单的调度算法。

它响应请求队列中时限最早的请求,是其它实时电梯调度算法性能衡量的基准和特例。

2.2 SCAN-EDF 算法

SCAN-EDF 算法是 SCAN 算法和 EDF 算法相结合的产物。SCAN-EDF 算法先按照
EDF
算法选择请求列队中哪一个是下一个服务对象,而对于具有相同时限的请求,则按照
SCAN 算法服务每一个请求。它的效率取决于有相同 deadline
的数目,因而效率是有限的。

2.3 PI 算法

PI(Priority
Inversion)算法将请求队列中的请求分成两个优先级,它首先保证高优先级队列中的请求得到及时响应,再搞优先级队列为空的情况下在相应地优先级队列中的请求。

2.4 FD-SCAN 算法

FD-SCAN(Feasible Deadline
SCAN)算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求,作为下一次
SCAN 的方向。

并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。

这种算法忽略了用 SCAN
算法相应其它请求的开销,因此并不能确保服务对象时限最终得到满足。

算法基础阅读:8 种排序算法:从原理到改进,再到代码兑现透彻解析

以上两结介绍了几种简单的电梯调度算法。

但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。

随着微机在电梯系统中的应用和人工智能技术的发展,智能群控技术得以迅速发展起来。

由此,电梯的群控方面陆续发展出了一批新方法,包括:基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。

4.1 电梯的初始状态

本人设置的电梯的初始状态,是对住宅楼的电梯的设置。

建筑共有21层,其中含有地下一层。

建筑内部设有两部电梯,编号分别为A梯、B梯。

电梯内部有23个按钮,其中包括开门按钮、关门按钮和楼层按钮,编号为-1,1,2,3,4……20。

电梯外部含有两个按钮,即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外,建筑顶层只设置有向下运行按钮,地下一层只设置有向上运行按钮。

电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒,而运行中通过一层的时间为1秒。

在凌晨2:00——4:30之间,如若没有请求信号,A梯自动停在14层,B梯自动停在6层。

当电梯下到-1层后,如果没有请求信号,电梯自动回到1层。

4.2 电梯基本功能

每一架电梯都有一个编号,以方便监控与维修。每一架电梯都有一实时监控器,负责监控电梯上下,向电梯升降盒发送启动、制动、加速、减速、开关电梯门的信号。若电梯发生故障,还应向相应的电梯负责人发送求救信号。

4.3 电梯按钮功能

电梯内部的楼层按钮:电梯内部对应每一个楼层的按钮成为楼层按钮,即本章第一结提到的编号为
-1,1,2,3,4……20的按钮。当乘客进入电梯后按下楼层按钮,此按钮显示灰色,代表不可以用。

这样就表示乘客将要去往此层,电梯将开往相应层。当电梯到达该层后,按钮恢复可以使用状态。

电梯内部开门按钮:当电梯达到乘客想要去往的某楼层后,乘客需要准备离开电梯,当电梯停稳后,乘客可以按下开门按钮,电梯门将打开,让用户离开。

如若电梯到了乘客曾经按下的楼层,但是无乘客按开门按钮,电梯将自动在停稳后1秒后自动开门。

电梯内部关门按钮:当所有想要乘坐电梯的乘客都进入电梯以后,准备让电梯开始运行的时候,乘客需要按下关门按钮,让电梯门关闭,使电梯进入运行状态。设置电梯的自动关门时间为8秒。

电梯外部向上按钮:此按钮表示上楼请求,当按下此按钮时,如果电梯到达按下此按钮的楼层,且电梯运行方向是向上的,那么电梯响将停下,并在电梯停稳之后自动开门,此请求被响应后,取消此请求信号。

电梯外部向下按钮:此按钮表示下楼请求,当按下此按钮时,如果电梯到达按下此按钮的楼层,且电梯运行方向是向下的,那么电梯响将停下,并在电梯停稳之后自动开门,此请求被响应后,取消此请求信号。

想要学习Java高架构、分布式架构、高可扩展、高性能、高并发、性能优化、Spring
boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分布式项目实战学习架构师视频免费获取
架构群:614478470

编程,点击链接加入群聊:

结束语

你肯能意识到哪个算法都不是一个最佳方案,只是它确实解决了一定情况的问题。

但是对一个优秀的程序员而言,研究各种算法是无比快乐的。也许你下一次面试,就有关于调度算法的问题。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 澳门新葡亰官网app 版权所有