您所在位置：主题：理发店问题的决策与仿真解决方案参考
beggarson
[专家分：330] 发布于 2006-08-23 22:42:00
我以前在这个论坛混的时候发过一个帖子是理发店问题的仿真，后来很多网友给我要算法代码，现在我考研，有看了看原来的程序。以现在的眼光，很多地方当然不完善了（要不就没进步了，是吧:P）。
我把代码和当时写的论文放在了我的blog上，以后有学弟学妹再做这个问题时，可以参考下，当然有人能提出改进算法最好了。共同进步吧。
我不大上网，回帖就不看了。
网址在：http://blog.csdn.net/patriotlml/archive/2006/08/23/1108453.aspx
贴出一部分，呵呵。
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
这是我大二学过数据结构后做的课程设计，用的是C，并且当时做了些改进后没有再管，毕竟只是个100多行的小程序，没什么价值。后来看了个比较经典的，是软件水平考试程序员教材（蓝皮的，比较厚），在队列一章里面看到的。这里就是自己当时写的论文，比较粗糙，应该对理解本模拟算法有所帮助，有达人能指点下最好不过了。这种东西最好用C++写。C++的恐怕要用到面向对象的技术，否则和pure C的就没什么区别了。文末附上了网友改写的C++版，是BIT的邹斌同学完成的，在VC6下调试成功。
引言篇
用队列结构可以模拟现实世界生活中的很多排队现象。例如车站候车、医院候诊、等候理发等各种排队现象都可以通过程序进行仿真，并由此预测客流等多种经营指标，为经办人的决策提供有价值的量化指标。现在以理发馆的运作情况为模型，讨论排队问题的系统仿真。
题目内容：使用的排队现象，通过仿真手法评估其营业状况。
*基本要求：设某理发馆有N把理发椅，可同时为N位顾客进行理发。
*当顾客进门时，若有空椅，则可以立即坐下理发，否则需要依次排队等候。
*一旦有顾客理完发离去时，排在队头的顾客便可开始理发。
*若理发馆每天连续营业T小时，求一天内顾客在理发馆内的平均逗留时间
*顾客排队等候的队列平均长度。
*测试数据：理发椅数目N及关门时间由用户读入，第一个顾客进门的时刻为0，
之后每个顾客的进门时间在前一个顾客进门时设定。即在进门事件发生时立刻产生两个随机数**(durtime,intertime）durtime为进门顾客理发所需要的时间，intertime为下一个顾客将要到达的时间间隔。*R为由随机数发生器产生的随机数，顾客理发时间和顾客之间的时间间隔不妨
假设与R有关，可以由以下公式确 定 ：durtime=15+R%50,intertime=2+R%10。
1.可行性分析
队列结构有着其本身极其特殊的特点：先进先出（First in First out缩写为FIFO）。他本质上还是一中种线形表，允许在表的一端进行插入，而在另一端删除元素。这和我们生活中的排队理发现象很一致：最早进入的人最早能得到服务离开，某一个人不可能在他前面的人未得到服务时就抢先得到服务。这样我们就可以假设理发店中有N把椅子，理发店在start点开门营业并连续营业T个时间单位，当我们把某一既定理发店的这些信息输入后，经过计算机的模拟就可以看到所有有关顾客理发的信息。
总体操作上，我主要对计算机如何正确模拟仿真现实中的理发过程即如何处理进出队列相关数据感兴趣。这样，我在实现模拟过程中设某理发馆有N把理发椅，可同时为N位顾客进行理发。当顾客进门时，若有空椅，则可以立即坐下理发，否则需要依次排队等候。一旦有顾客理完发离去时，排在队头的顾客便可开始理发。若理发馆每天连续营业T小时，求一天内顾客在理发馆内的平均逗留时间，顾客排队等候的队列平均长度。有了这样一个指导思想，我首先构建了一个结构体，存放某一顾客进门理发、等待、接受服务等等各种信息。然后出于简洁方面的考虑，我在建设一个等待队列，用来存放等待的顾客的相关信息时，只把顾客的编号（即在所有顾客数组中的下标）入队，简单来说就是队列结点的结构体中包含等待顾客的编号和指向下一个结构体的指针。
在实现技术上，我沿用了在Mirosoft Visiual Basic中比较利于实时功能的时钟计时器。假设一个当前时间curtime每过一分钟让它加一，然后
判断在这个时间单位中是否有人符合离开的条件（正在理发的顾客理发已用时间是否满足其所需时间），如有让其离开（调用cus_leave()函数）；
判断是否有人可以接受服务（当等待队列中的人发现有空闲椅子时），让等待队列中第一个等待的人出队（调用dequeue()函数）并去理发（调用cus_serve()函数），否则继续等待；
判断最后一个进入理发店的顾客的下一个人是否满足进入条件（即与最后一个进入理发店的顾客的时间间隔是否已经达到），如有人可以进入，则调用cus_in()函数。时间片加一，重复进行。
需要说明的是cus_in()函数，他是顾客进入的函数，他本身的实现是进入一名顾客时，为其分配空间存放各种有关信息并把他记入结构体数组中。然后判断有没有人在等待，如果有则他直接进入等待队列等待，调用enqueue(int n)函数；如果有空闲位置则他可以直接调用cus_serve()函数，否则无空闲位置也进入等待队列中继续等待。
2.需求分析
要做好需求分析，首先要能正确模拟理发店顾客不确定性进入和理发时间的随机问题。进入某一理发店的顾客的人数在不同时刻是不同的，所以我们要采用电脑随机产生顾客理发所需时间、下一个顾客到来时间等相关信息。在研究了某理发店的顾客到来时间间隔和顾客理发所需总时间后，发现基本符合以下随机种子：durtime=15+R%50,interval=2+R%10。其中durtime是顾客理发所需时间，而interval是顾客到来之间的时间间隔。
按以上公式计算出的顾客相关信息可以基本上满足需求的分析。当我们在输入了本理发店的椅子数、开业时间和营业总时间后就可以利用随机数模拟这些过程了。模拟后所有顾客相关信息都会在调用print（）函数时打印出来，除此之外，本模拟系统又带回一些返回值：顾客数（number_custeromer）、平均等候时间(average_time)、平均队长(average_queuelength)。
（其中顾客数有公式number_custeromer=customernum算得；
平均等候时间由公式average_time=totaltime/customernum算得；
平均队长由average_queuelength=totallenth/customernum算得；）
3.系统总体设计
3.1系统功能分析
该系统主要模拟的是理发店的顾客服务过程，以能为某一店铺提供适合它自己的、精确而有用的参考数据，有效地帮助店主作出经济决策。具体来说是用计算机按我们输入的相关要求如相关数据、公式等帮我们随机生成顾客的相关信息，并能利用队列来模拟进入理发店的顾客当理发椅不可用时先等待后按先来先服务的原则进行接受理发。计算机模拟的这种功能我们不妨叫做仿真，但这种决策仿真是建立在排队的基础上的。
3.2系统功能模块设计
首先我们按系统的流程图理解实现这一决策仿真的算法。
先是主函数中对预处理的一些全局变量进行初始化赋值，其中包括针对某一理发店的椅子数和开业时间以及营业时间的输入，这是通过最简单的调用函数scanf（）实现的。然后让第一个人进入理发店，表示理发店今天正式开张。其中第一个人进入后判断是否有空闲椅子即N_valid是大于0的数并且无人在等待，如是则直接调用为他服务函数，否则排队等候。第一个人明显符合直接接受服务的条件。
然后利用计时器，，每过一分钟（或一个时间单位），就进行以下判断：
①首先判断是否有人符合离开的条件即cus[i].starttime+cus[i].durtime等于curtime，如果有人满足的话就让其离开，调用void customer_leave(int n)函数，否则继续；
②其次判断等待在队列首位的顾客是否有机会理发即正好刚有人离开。这样调用void customer_serve(int n)函数实现；
③最后判断最后一个进来的顾客的下一个顾客是否可以进来了，如果他的时间间隔和他进来的时间只和等于当前时间的话，那么就调用下一个顾客来的函数void customer_in()。当然在调用void customer_in()函数时注意一点是刚刚进来的顾客也要判断是否可以直接理发还是进入等待队列去等待，类似于第一位顾客。
执行完这个时间片后继续执行剩下的时间片，即while循环直到时间片用完为止。
时间片用完后，我们要考虑到那些正在等待的顾客。从经济因素考虑，我以为继续为他们提供服务比较好，这样就有一个等待队列是否为空的问题：如果不为空，我们要继续让那些正在理发并符合离开条件的人执行离开函数以能留出空闲位置提供为正在等待的人。但当等待队列为空时，我们已经得到最后一批理发人的所有信息，不必继续模拟，直接打印相关信息调用list()。这样就完成了对一次营业的决策仿真。
<流程图>
4.系统详细设计
4.1数据库需求分析
这里所涉及的随机数据库是对应于所有进入顾客的相关信息，这是随机的，他不是磁盘中固定位置固定大小的一组数据，而是在计算机模拟理发店的决策仿真时按给定的公式随机产生的。我在实现这个系统的仿真时用到了rand（）函数以能实现“随机”这一目标。当然如果要实现每一次产生的随机数不相同的话，还可以调用srnd(time(NULL))函数，简单起见我省略了。
4.2 数据字典
我觉得有必要在这里以数据字典的形式介绍一下在实现计算机模拟中用到的一些变量和函数的意义。5.用户手册
5.1相关说明
这是我的实习和课程设计成果，花了不到一个星期的时间，做的并不好。
功能很单一的一个计算机模拟系统，在创意上也没什么独到之处只是实现起来算法比较好理解，而且采用调用函数，主函数的执行步骤是很具备逻辑性的。
在TC2.0和Win-C上都调试通过。
5.2问题解决
如果产生一些意外的问题的话请参照在文本文档中的中文注释，相信会对您理解和正确实现决策仿真有极大的帮助。请不要将您的改动直接保存在此系统中，当本程序因你的私自改动而产生无法得到预期效果，作者概不负责。
6.运行维护
请在运行本程序前先认真阅读用户手册，如有疑问请直接与我联系。
结束语
感谢汪静老师一直以来的关心与支持，并在本系统的立意和算法实现上的帮助。感谢徐杰同学的技术支持和熊浩同学的友情客串，以及赵浩同学在分析本系统的初始形态时提出的问题，并及时得以解决。
感谢自己能熬四个通宵为自己认为值得的事这么卖命。
参考资料：
1、《信息系统分析与设计》清华大学出版社。
2、《数据结构》清华大学出版社严蔚敏等编著。
3、《C程序设计》 清华大学出版社。
4、《C++程序设计》 清华大学出版社。
5、《VB程序设计》清华大学出版社
float wait_length; /*等待的队列长度*/
float totalnum; /*总共服务过的顾客数*/
float totaltime; /* 顾客理发总时间*/
int start; /*开张时间*/
int curtime; /*当前时间*/
int N_valid; /*可用椅子数*/
int T,N; /*椅子总数，营业时间*/
typedef struct customer
{
int NO; /*编号*/
int durtime; /*理发所需时间*/
int intime; /*进入理发店时间*/
int starttime; /*开始理发时间*/
int interval; /*他的下一个人到来的时间间隔*/
int wait_flag,serve_flag; /*是否在等待，是否在理发*/
}customer;
customer cus[MAX];
LinkQueue *W; /*等待队列*/
void InitQueue(LinkQueue *Q) /*等待队列初始化*/
tatus Queue_Length(LinkQueue *Q) /*求等待队列的当前长度*/
void EnQueue(LinkQueue *Q,int e) /*入队等待*/
status DeQueue(LinkQueue *Q) /*出队*/
status QueueEmpty(LinkQueue *Q) /*判断等待队列是否为空*/
void customer_serve(int n) /*为顾客理发*/
void customer_in() /*顾客进入理发店*/
void customer_leave(int n) /*顾客离开理发店*/
void list() /*打印所有值*/
我把代码和当时写的论文放在了我的blog上，以后有学弟学妹再做这个问题时，可以参考下，当然有人能提出改进算法最好了。共同进步吧。
我不大上网，回帖就不看了。
网址在：http://blog.csdn.net/patriotlml/archive/2006/08/23/1108453.aspx
贴出一部分，呵呵。
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
这是我大二学过数据结构后做的课程设计，用的是C，并且当时做了些改进后没有再管，毕竟只是个100多行的小程序，没什么价值。后来看了个比较经典的，是软件水平考试程序员教材（蓝皮的，比较厚），在队列一章里面看到的。这里就是自己当时写的论文，比较粗糙，应该对理解本模拟算法有所帮助，有达人能指点下最好不过了。这种东西最好用C++写。C++的恐怕要用到面向对象的技术，否则和pure C的就没什么区别了。文末附上了网友改写的C++版，是BIT的邹斌同学完成的，在VC6下调试成功。
引言篇
用队列结构可以模拟现实世界生活中的很多排队现象。例如车站候车、医院候诊、等候理发等各种排队现象都可以通过程序进行仿真，并由此预测客流等多种经营指标，为经办人的决策提供有价值的量化指标。现在以理发馆的运作情况为模型，讨论排队问题的系统仿真。
题目内容：使用的排队现象，通过仿真手法评估其营业状况。
*基本要求：设某理发馆有N把理发椅，可同时为N位顾客进行理发。
*当顾客进门时，若有空椅，则可以立即坐下理发，否则需要依次排队等候。
*一旦有顾客理完发离去时，排在队头的顾客便可开始理发。
*若理发馆每天连续营业T小时，求一天内顾客在理发馆内的平均逗留时间
*顾客排队等候的队列平均长度。
*测试数据：理发椅数目N及关门时间由用户读入，第一个顾客进门的时刻为0，
之后每个顾客的进门时间在前一个顾客进门时设定。即在进门事件发生时立刻产生两个随机数**(durtime,intertime）durtime为进门顾客理发所需要的时间，intertime为下一个顾客将要到达的时间间隔。*R为由随机数发生器产生的随机数，顾客理发时间和顾客之间的时间间隔不妨
假设与R有关，可以由以下公式确 定 ：durtime=15+R%50,intertime=2+R%10。
1.可行性分析
队列结构有着其本身极其特殊的特点：先进先出（First in First out缩写为FIFO）。他本质上还是一中种线形表，允许在表的一端进行插入，而在另一端删除元素。这和我们生活中的排队理发现象很一致：最早进入的人最早能得到服务离开，某一个人不可能在他前面的人未得到服务时就抢先得到服务。这样我们就可以假设理发店中有N把椅子，理发店在start点开门营业并连续营业T个时间单位，当我们把某一既定理发店的这些信息输入后，经过计算机的模拟就可以看到所有有关顾客理发的信息。
总体操作上，我主要对计算机如何正确模拟仿真现实中的理发过程即如何处理进出队列相关数据感兴趣。这样，我在实现模拟过程中设某理发馆有N把理发椅，可同时为N位顾客进行理发。当顾客进门时，若有空椅，则可以立即坐下理发，否则需要依次排队等候。一旦有顾客理完发离去时，排在队头的顾客便可开始理发。若理发馆每天连续营业T小时，求一天内顾客在理发馆内的平均逗留时间，顾客排队等候的队列平均长度。有了这样一个指导思想，我首先构建了一个结构体，存放某一顾客进门理发、等待、接受服务等等各种信息。然后出于简洁方面的考虑，我在建设一个等待队列，用来存放等待的顾客的相关信息时，只把顾客的编号（即在所有顾客数组中的下标）入队，简单来说就是队列结点的结构体中包含等待顾客的编号和指向下一个结构体的指针。
在实现技术上，我沿用了在Mirosoft Visiual Basic中比较利于实时功能的时钟计时器。假设一个当前时间curtime每过一分钟让它加一，然后
判断在这个时间单位中是否有人符合离开的条件（正在理发的顾客理发已用时间是否满足其所需时间），如有让其离开（调用cus_leave()函数）；
判断是否有人可以接受服务（当等待队列中的人发现有空闲椅子时），让等待队列中第一个等待的人出队（调用dequeue()函数）并去理发（调用cus_serve()函数），否则继续等待；
判断最后一个进入理发店的顾客的下一个人是否满足进入条件（即与最后一个进入理发店的顾客的时间间隔是否已经达到），如有人可以进入，则调用cus_in()函数。时间片加一，重复进行。
需要说明的是cus_in()函数，他是顾客进入的函数，他本身的实现是进入一名顾客时，为其分配空间存放各种有关信息并把他记入结构体数组中。然后判断有没有人在等待，如果有则他直接进入等待队列等待，调用enqueue(int n)函数；如果有空闲位置则他可以直接调用cus_serve()函数，否则无空闲位置也进入等待队列中继续等待。
2.需求分析
要做好需求分析，首先要能正确模拟理发店顾客不确定性进入和理发时间的随机问题。进入某一理发店的顾客的人数在不同时刻是不同的，所以我们要采用电脑随机产生顾客理发所需时间、下一个顾客到来时间等相关信息。在研究了某理发店的顾客到来时间间隔和顾客理发所需总时间后，发现基本符合以下随机种子：durtime=15+R%50,interval=2+R%10。其中durtime是顾客理发所需时间，而interval是顾客到来之间的时间间隔。
按以上公式计算出的顾客相关信息可以基本上满足需求的分析。当我们在输入了本理发店的椅子数、开业时间和营业总时间后就可以利用随机数模拟这些过程了。模拟后所有顾客相关信息都会在调用print（）函数时打印出来，除此之外，本模拟系统又带回一些返回值：顾客数（number_custeromer）、平均等候时间(average_time)、平均队长(average_queuelength)。
（其中顾客数有公式number_custeromer=customernum算得；
平均等候时间由公式average_time=totaltime/customernum算得；
平均队长由average_queuelength=totallenth/customernum算得；）
3.系统总体设计
3.1系统功能分析
该系统主要模拟的是理发店的顾客服务过程，以能为某一店铺提供适合它自己的、精确而有用的参考数据，有效地帮助店主作出经济决策。具体来说是用计算机按我们输入的相关要求如相关数据、公式等帮我们随机生成顾客的相关信息，并能利用队列来模拟进入理发店的顾客当理发椅不可用时先等待后按先来先服务的原则进行接受理发。计算机模拟的这种功能我们不妨叫做仿真，但这种决策仿真是建立在排队的基础上的。
3.2系统功能模块设计
首先我们按系统的流程图理解实现这一决策仿真的算法。
先是主函数中对预处理的一些全局变量进行初始化赋值，其中包括针对某一理发店的椅子数和开业时间以及营业时间的输入，这是通过最简单的调用函数scanf（）实现的。然后让第一个人进入理发店，表示理发店今天正式开张。其中第一个人进入后判断是否有空闲椅子即N_valid是大于0的数并且无人在等待，如是则直接调用为他服务函数，否则排队等候。第一个人明显符合直接接受服务的条件。
然后利用计时器，，每过一分钟（或一个时间单位），就进行以下判断：
①首先判断是否有人符合离开的条件即cus[i].starttime+cus[i].durtime等于curtime，如果有人满足的话就让其离开，调用void customer_leave(int n)函数，否则继续；
②其次判断等待在队列首位的顾客是否有机会理发即正好刚有人离开。这样调用void customer_serve(int n)函数实现；
③最后判断最后一个进来的顾客的下一个顾客是否可以进来了，如果他的时间间隔和他进来的时间只和等于当前时间的话，那么就调用下一个顾客来的函数void customer_in()。当然在调用void customer_in()函数时注意一点是刚刚进来的顾客也要判断是否可以直接理发还是进入等待队列去等待，类似于第一位顾客。
执行完这个时间片后继续执行剩下的时间片，即while循环直到时间片用完为止。
时间片用完后，我们要考虑到那些正在等待的顾客。从经济因素考虑，我以为继续为他们提供服务比较好，这样就有一个等待队列是否为空的问题：如果不为空，我们要继续让那些正在理发并符合离开条件的人执行离开函数以能留出空闲位置提供为正在等待的人。但当等待队列为空时，我们已经得到最后一批理发人的所有信息，不必继续模拟，直接打印相关信息调用list()。这样就完成了对一次营业的决策仿真。
<流程图>
4.系统详细设计
4.1数据库需求分析
这里所涉及的随机数据库是对应于所有进入顾客的相关信息，这是随机的，他不是磁盘中固定位置固定大小的一组数据，而是在计算机模拟理发店的决策仿真时按给定的公式随机产生的。我在实现这个系统的仿真时用到了rand（）函数以能实现“随机”这一目标。当然如果要实现每一次产生的随机数不相同的话，还可以调用srnd(time(NULL))函数，简单起见我省略了。
4.2 数据字典
我觉得有必要在这里以数据字典的形式介绍一下在实现计算机模拟中用到的一些变量和函数的意义。5.用户手册
5.1相关说明
这是我的实习和课程设计成果，花了不到一个星期的时间，做的并不好。
功能很单一的一个计算机模拟系统，在创意上也没什么独到之处只是实现起来算法比较好理解，而且采用调用函数，主函数的执行步骤是很具备逻辑性的。
在TC2.0和Win-C上都调试通过。
5.2问题解决
如果产生一些意外的问题的话请参照在文本文档中的中文注释，相信会对您理解和正确实现决策仿真有极大的帮助。请不要将您的改动直接保存在此系统中，当本程序因你的私自改动而产生无法得到预期效果，作者概不负责。
6.运行维护
请在运行本程序前先认真阅读用户手册，如有疑问请直接与我联系。
结束语
感谢汪静老师一直以来的关心与支持，并在本系统的立意和算法实现上的帮助。感谢徐杰同学的技术支持和熊浩同学的友情客串，以及赵浩同学在分析本系统的初始形态时提出的问题，并及时得以解决。
感谢自己能熬四个通宵为自己认为值得的事这么卖命。
参考资料：
1、《信息系统分析与设计》清华大学出版社。
2、《数据结构》清华大学出版社严蔚敏等编著。
3、《C程序设计》 清华大学出版社。
4、《C++程序设计》 清华大学出版社。
5、《VB程序设计》清华大学出版社
float wait_length; /*等待的队列长度*/
float totalnum; /*总共服务过的顾客数*/
float totaltime; /* 顾客理发总时间*/
int start; /*开张时间*/
int curtime; /*当前时间*/
int N_valid; /*可用椅子数*/
int T,N; /*椅子总数，营业时间*/
typedef struct customer
{
int NO; /*编号*/
int durtime; /*理发所需时间*/
int intime; /*进入理发店时间*/
int starttime; /*开始理发时间*/
int interval; /*他的下一个人到来的时间间隔*/
int wait_flag,serve_flag; /*是否在等待，是否在理发*/
}customer;
customer cus[MAX];
LinkQueue *W; /*等待队列*/
void InitQueue(LinkQueue *Q) /*等待队列初始化*/
tatus Queue_Length(LinkQueue *Q) /*求等待队列的当前长度*/
void EnQueue(LinkQueue *Q,int e) /*入队等待*/
status DeQueue(LinkQueue *Q) /*出队*/
status QueueEmpty(LinkQueue *Q) /*判断等待队列是否为空*/
void customer_serve(int n) /*为顾客理发*/
void customer_in() /*顾客进入理发店*/
void customer_leave(int n) /*顾客离开理发店*/
void list() /*打印所有值*/
