有限状态机应用

1大作业-文件IO版本设计思路12/25/20192大作业文件IO版本模块结构图模型内部状态控制器策略算法结果记录写入文件状态变化事件改变状态文件输入读取请求事件时间同步12/25/20193大作业文件IO版本程序框架/*大作业文件IO版本的程序主体结构*/structSTATE{…}//电梯或银行的运行状态structLIST{…}//请求队列链表节点structREQ{…}//暂存每次获得的请求事件intmain(){inttimeCount=0;//计时器，每循环一次模拟2msstructREQtheReq={};//暂存每次获得的请求事件structSTATEpreST,theST={};//保存电梯或银行的运行状态structLIST*headp=NULL;//存请求队列链表头指针File*fpin,*fpout;12/25/20194大作业文件IO版本程序框架openFile(**fpin,**fpout);//打开输入输出文件theReq=get_fileInput(fpin);//读取第一个请求while(!(endInput(fpin)&&isIdle(theST))){//当文件输入结束，且电梯或营业厅空闲才退出if(theReq.time==timeCount){headp=addServList(headp,theReq,theST,1);/*当请求事件发生的时间到，添加请求事件到服务队列中,策略参数为1对应先来先服务，2对应顺便服务*/theReq=get_fileInput(fpin);//读取文件中的下一个请求事件}//endif12/25/20195大作业文件IO版本程序框架preST=theST;theST=runService(preST,&headp,timeCount);if(theST.state!=preST.state)set_fileOutput(fpout,timeCount,theST,headp);/*当状态变化，将当前时间、状态和等待队列的情况写入到文件中。*/timeCount++;}//endwhilecloseFile(fpin,fpout);//关闭输入输出文件return0;}//endmain12/25/20196大作业文件IO版本函数接口intendInput(File*fp)//判断文件输入是否结束intisIdle(structSTATEstate)//判断电梯或营业厅当前状态是否空闲structREQget_fileInput(File*fp)//顺序读取文件中的一个请求事件structLIST*addServList(structLIST*hp,structREQreq,structSTATEstate,intmode);//按照策略，将新请求插入请求队列中structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根据状态、请求和时间条件，运行电梯或营业厅服务。运行服务后将改变的状态返回。注意当服务完一个请求后，删除该节点并修改头指针！*/12/25/20197大作业文件IO版本函数接口structSTATErunService(structSTATEstate,structLIST**hp,inttime)/*根据状态、请求和时间条件，运行电梯或营业厅服务。运行服务后将改变的状态返回。注意当服务完一个请求后，删除该节点并修改头指针！*/voidset_fileOutput(File*fp,inttime,structSTATEstate,structLIST*hp)/*将当前时间、状态和等待队列的情况顺序写入文件*/12/25/20198输入文件格式定义：电梯•输入用电梯请求文件格式：•文本文件，每一行表示一个时刻发生的电梯请求。格式定义如下：T=请求发生时间,CallF=楼层请求\n例:T=1,CallF=4UT=2,CallF=4U5T请求发生时间：按程序运行的系统时钟时间，单位秒.楼层请求：由呼叫方向(U/D/T)和数字（1～9）组成，同时有多个请求时用空格分割。如2U5D6T，表示2层上行呼叫、5层下行呼叫、6层目标停靠。12/25/20199输出文件格式定义：电梯•电梯运行结果记录文件格式：•文本文件，每一行表示一个电梯停靠或启动、转向动作，当前楼层和目标楼层，以及排队的楼层请求。格式定义如下：T=当前时间,State=电梯状态,NowF=电梯当前楼层,GoalF=电梯目标楼层,StopT=停靠时间,WaitF=未响应的楼层请求\n例:T=3,State=UP_RUN,NowF=1.0,GoalF=3,StopT=0,WaitF=4U5D6TT=3,State=UP,NowF=1.0,GoalF=3,StopT=0,WaitF=4U5T6U9D8D12/25/201910输出文件格式定义：电梯•当前时间：程序开始运行的系统时钟时间，单位秒。•电梯状态：UP_RUN表示向上运行、DOWN_RUN表示向下运行、UP_STOP表示上行停靠、DOWN_STOP表示下行停靠、IDLE表示空闲。•电梯当前楼层：1.0-9.0。停靠时间：记录电梯已经停靠的时间,单位秒。只有在停靠状态下，该信息才大于0。•未响应的楼层请求：按照电梯控制策略，按响应顺序将尚未响应的呼叫请求和目标楼层列出来。是由呼叫方向(U/D/T)和数字（1～9）组成的序列，中间用一个空格分割。如2U5D6T，表示2层上行呼叫、5层下行呼叫、6层目标停靠。12/25/201911输入文件格式定义：银行•输入用银行请求文件格式：•文本文件，每一行表示一个时刻发生的客户到达事件、窗口休息请求或下班指令。格式定义如下：T=请求发生时间,Req=请求\n请求=C客户人数|W请求休息的窗口号|Q下班时间例:T=1,Req=C5T=6,Req=W3T=200,Req=Q250时间：按程序运行的系统时钟时间，单位秒.12/25/201912输出文件格式定义：银行•银行运行结果记录文件格式：•文本文件，每一行表示一个营业厅窗口的叫号、暂停休息、准备下班、进入空闲、下班等动作，各窗口状态和正在服务的客户号码，以及等待服务的客户情况。格式定义如下：T=当前时间,Event=事件描述,Now=各窗口状态,Wait=等待服务的客户情况\n事件描述=JH空格W窗口号空格C客户号码ZT空格W窗口号空格R休息时长KX空格W窗口号ZB空格下班时间XB12/25/201913输出文件格式定义：银行客户号码=0001~9999各窗口状态=W窗口号空格S窗口状态空格C当前客户号码S窗口状态=S0表示空闲S1表示服务S2表示暂停等待服务的客户情况=策略1：Q队列长度空格F队首客户号码空格L队尾客户号码策略2：W窗口号空格队列中客户号码例:T=3,Event=JHW2C0009,Now=W1S1C0004W2S2C0000W3S0C0000,Wait=Q19F0010L002814用有限状态自动机模型实现复杂的过程控制策略15什么是有限状态自动机？FiniteStateMachine,又称有限状态机或简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。–状态：存储关于过去的信息，就是说,它反映从系统开始到现在时刻的输入变化。–转移:指示状态变更，并且用必须满足来确使转移发生的条件来描述它。–动作:是在给定时刻要进行的活动的描述。有多种类型的动作：进入动作（Entryaction）-在进入状态时进行退出动作-在退出状态时进行输入动作-依赖于当前状态和输入条件进行转移动作-在进行特定转移时进行16•为了描述一个有限状态机的工作状况，可采用状态转换图。状态转换图是一个有向图，图中的每个节点表示一种状态，一条边（或弧）表示一个转换关系。•初始状态通常用“没有起点的箭头”指向它来表示。•终止状态是机器完成了它的程序之后的状态，它通常表示为双重圆圈。q0q1q3q2aabbb状态转换图a17状态表•除了状态转换图以外,还可以使用多种类型的状态转移表。最常见的表示如下：•当前状态和条件的组合指示出下一个状态。•完整的动作信息可以只使用脚注来增加。状态转移表当前状态→条件↓状态A状态B状态C条件X………条件Y…状态C…条件Z………18•FSM有两个不同的类别：接受器／识别器和变换器。•接受器产生一个二元输出，说要么“是”要么“否”来回答输入是否被机器接受。•在所有输入都被处理了的时候，如果当前状态是接受状态，输入被接受；否则被拒绝。•作为规则，输入是符号（字符）；动作不使用。接受器状态机q0q1q3q2aabbbErr19•变换器使用动作基于给定输入和／或状态生成输出。常分为两种类型：Moore机和Mealy机。•Moore机-只使用进入动作的FSM，就是说输出只依赖于状态。Moore模型的好处是行为的简单性。•例：一个电梯门的MooreFSM。状态“Opening”中的进入动作(E:)开启电机开门，在状态“Closing”中的进入动作以反方向开启电机关门。状态“Opened”和“Closed”不进行任何动作。变换器状态机（1）q0openingcloseing开门关门openedclosed20•Mealy机-只使用输入动作的FSM，就是说输出依赖于输入和状态。•MealyFSM的使用经常导致状态数目的简约。•例：电梯门的MealyFSM•有两个输入动作：“开启电机关门如果command_close下达”和“反向开启电机开门如果command_open下达”。变换器状态机（2）q0openedclosed21FSM的类型•在实践中经常使用混合模型。•进一步可区分为确定型（DFA）和非确定型（NDFA、GNFA）自动机。在确定型自动机中，每个状态对每个可能输入只有精确的一个转移。在非确定型自动机中，给定状态对给定可能输入可以没有或有多于一个转移。•这个区分在实践而非理论中更有用，因为存在算法把任何NDFA转换成等价的DFA，尽管这种转换一般会增加自动机的复杂性。22有限状态自动机的应用•有限状态自动机在很多不同领域中都是重要的，包括电子工程、语言学、计算机科学、哲学、生物学、数学和逻辑学。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中，有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程，编译器、网络协议、和计算与语言的研究。•针对许多类型的编程问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。23例1：串口通信两台微机通过串口通信,需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。传输数据收到应答断开连接发出连接请求q0q1q2q0：空闲状态q1:等待应答状态q2：通信状态24例2：打电话(状态机在通信领域的应用)。在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。q0q1q2q3q4摘机收到拨号音拨号收应答信号挂机q0:空闲状态q1:等待拨号音状态q2:可以拨号状态q3:等待应答状态q4:通话状态状态迁移状态25•接受器有限状态机的形式化定义一个五元组其中：：有限的状态集合；：有限的输入字母表；：转换函数，是到的映射；：初始状态，；：终止状态集，；QT0qFTQQQF接受器的形式化定义Qq0),,,,(0FqTQM（初始状态只有一个）26aq0q1q3q2aabbb状态集合字母表初始状态终止状态集},,,{3210qqqqQ},{baT}{3qF0q转换函数10),(qaq20),(qbq31),(qaq11),(qbq22),(qaq3