这种抽象问题的思维蛮巧妙的，看完一定会有不小的收获！

问题

编制一个程序以模拟银行窗口接待客户的排队业务活动，并计算一天中客户在银行的逗留的平均时间

  1. 每个窗口在某个时刻只能接待一个客户
  2. 窗口空闲，则可上前办理业务
  3. 窗口均被占，则新客户便会排在人数少的队伍前面

【运行结果】采用离散事件模拟，输入30多运行几次，可以好好体会这种离散事件模拟的思想

  • 这里营业时间选小一点，一共营业30分钟
  • 用户来的间隔时间nextTime，nextTime∈[0,5]
  • 银行一个业务的办理时间段durtime，durtime∈[1,15]

[离散事件模拟] 银行窗口模拟 - 图1

思考

【问题1】为了对最终的编程结果有一个感性的认识，我们要搞清楚：客户在银行逗留的平均时间meanWaitTime和什么有关？
【答】银行办理一件业务的平均时间、窗口总数、用户间隔到达的时间等
【例如】

  • ①银行办理一件业务需要1min-15min②银行办理一件业务需要1min-30min，那么后者的meanWaitTime会比较长 —> 所以我们这里假定用户办理业务的时间是1min-15min
  • ①两个用户间隔0-5min的时间到达②两个用户相隔5-10min到达 —> 后者的间隔时间大，自然meanWaitTime比较小 —> 所以我们这里假设两个用户相隔时间为0-5min

【问题2】如何来模拟这个问题？
【答】容易想到的是，根据时间主线来刻画这个问题

  1. 设置一个currentTime表示当前的时间，根据currentTime来处理每一个用户，然后算的meanWaitTime
  2. 但这种抽象方法有接问题
    • 其一：currentTime的最小单元设置为多少？是秒？分？时？一般是设置成分钟（业务处理的最小单元是min），但是从早上7:00遍历到下午6:00，一分钟一分钟的推移，这个遍历的规模也是很大的
    • 其二：每到下一分钟，都要去遍历用户表，去判断这个点是不是有用户来
    • 其三：每到下一分钟，都要去遍历每个窗口当前的事件，去判断这个点是不是有用户办理完事情了
    • 其四：事先我们需要知道今天要来多少用户，然后随机生成他们的到达时间、处理业务的时间。虽然我们事先可以通过随机值来确定今天的用户量，但这种方法有它的局限性

【问题3】以客户为主线模拟这个问题，行不行？
【答】

  • 问题2中分析了以时间为主线有很多弊端，但以客户为主线行吗？确实，用户正是一个一个来到的店里，线性的抽象方法，有助于我们单线程编程的实现，值得考虑
  • 但仔细考虑，客户的行为分为“刚到店里”、“办理业务”和“离开银行”，三种事件，所以用户不是最小原子单元，它还可以继续再分，可以分成好几个事件，单线程也要分成3个部分。所以本篇介绍了以事件为主线，来模拟这个问题。

离散事件模拟

【背景】上述谈到以时间为主线来模拟这个问题，虽说思维清晰简单，但时间复杂度大，而且需要事先知道有多少个用户量

【较好的解决方案】离散事件模拟：以事件为主线，作为最小单元来处理。
把用户到达、等待、离开看成一个事件，而且这个时间在时间维度上是离散分布的

  1. 如何生成用户？
    【答】以时间为主线的方法是事先把所有用户都确定下来。而离散事件模拟的思路是：每到一个用户，就新增下一个用户，预计他所到达的时间
    • 而现实中，也是如此，用户是一个接着一个来到的店里，不考虑一起跨入店门（只要不一起跨入店门，最小划分单元为秒时，都可以抽象成用户是一个接着一个来的），这也是离散事件模拟的好处之一
    • 基于上一点，假设银行客户间隔来店的时间time，time∈[0min, 5min]
  2. 离散事件是以什么为主线的？
    【答】主线是事件，创建一个事件的列表eventList，按照事件event的发生时间来进行从小到大排序，并从小到大来处理事件

【数据结构】

  1. 客户：customer
    • 客户到达时间：arrivalTime
    • 办理业务所需时间：duration
      用伪随机数生成该用户的到达时间、办业务的所需的持续时间
  2. 事件：event
    • 该事件的类型：type
      • type=0：预计有下一个用户到达
      • type=value：表示有一个用户正在窗口value上办理业务
        例子：type=1：表示有一个用户正在窗口1上办理业务
    • 该事件发生的时刻：occurTime
  3. 事件链表：eventList
    • 把当前所有事件都串起来
  4. 窗口数组：windows[窗口数]
    • 每个窗口是一个队列
    • 队列的元素时一个用户customer
  5. 总时间totalTime
  6. 客户数customerNum

流程图

[离散事件模拟] 银行窗口模拟 - 图2
[离散事件模拟] 银行窗口模拟 - 图3

主要逻辑

[主要逻辑] 函数main()

  1. int totalTime=0, customerNum=0; //累计客户逗留时间，客户数
  2. EventList eventList; //事件表
  3. Event event; //事件
  4. CustomerQueue windows[WINDOWS_NUM+1]; //窗口，从1开始存储
  5. Customer customer; //客户记录
  6. int main() {
  7.     int closeTime; //关门时间
  9.     srand(time(NULL)); //设置随机种子，注意：一定要在main函数里，不能放在Random()里，否则无效
  11.     printf("输入营业的总分钟数：\n>>> ");
  12.     scanf("%d", &closeTime);
  13.     BankSimulation(closeTime);
  15.     return 0;
  16. }
  17. // 银行模拟
  18. void BankSimulation(int closeTime) {
  19.     OpenForDay(); //开门，初始化工作
  20.     while ( !ListEmpty(eventList) ) {
  21.         // 事件队列还有事件没有处理完
  22.         DelFirst(&eventList, &event); //取出第一个事件，并删除
  23.         if (event.type==0) //预计有新用户达到
  24.             CustomerArriving(closeTime); //生成这个用户几点来
  25.         else //用户正在办理业务
  26.             CustomerDeparture(closeTime); //用户离开事件
  27.     }
  28.     CloseForDay(); //关门，计算总结果
  29. }

[预计用户到达] 函数CustomerArriving()

  1. // 预测用户到达事件
  2. void CustomerArriving(int closeTime) {
  3.     long durtime, intertime;
  4.     int minWindow;
  6.     customerNum++; //客户量+1
  7.     printf("\t预测第%d客户", customerNum);
  9.     // 创建用户
  10.     durtime = rand()%15 +1; //一个业务的时间在1-15分钟
  11.     intertime = rand()%6; //用户间隔0-5分钟来一个
  12.     customer.id = customerNum; // 这是今天第几个用户了
  13.     customer.arrivalTime = event.occurTime + intertime; //到达时间
  14.     customer.duration = durtime;                        //客户办事的持续时间
  15.     if ( customer.arrivalTime >= closeTime ) { //用户来的时候已经关门了
  17.         printf("\t× 生成的下一个用户将在第%dmin到达，那时候已经关门了\n", customer.arrivalTime);
  19.     } else { //用户来的时候还没有关门
  21.         // 插入最短队
  22.         minWindow = GetMin(windows);                        //得到人数最少的队列
  23.         EnQueue(&windows[minWindow], customer);                //插入最短的队伍
  24.         printf("将在第%dmin到达，办理业务需要%dmin，到窗口%d排队", customer.arrivalTime, customer.duration, minWindow);
  26.         // 插入离开事件
  27.         event.occurTime = customer.arrivalTime + durtime; //预计离开时间
  28.         printf("，预计离开时间%dmin\n", event.occurTime);
  29.         event.type = minWindow; //窗口
  30.         if ( QueueLength(windows[minWindow]) ==1 ) //当前队伍只有他一个人
  31.             OrderInsert(&eventList, event); //插入离开事件，让这个人离开
  33.         // 预计下一个用户的到达
  34.         event.occurTime = customer.arrivalTime; //创建下一个用户到达的事件
  35.         event.type = 0;
  36.         if ( event.occurTime < closeTime ) //如果预计时间已经关门了，就退出
  37.             OrderInsert(&eventList, event);
  39.     }
  40. }

[用户离开逻辑] 函数CustomerDeparture()

  1. // 事件处理完成，用户离开
  2. void CustomerDeparture(int closeTime) {
  3.     int type; //窗口号
  4.     QNode *p;
  5.     QElemType qe;
  7.     type = event.type; //窗口号
  8.     DelQueue(&windows[type], &customer); //得到出队的用户
  9.     printf("窗口%d %d号用户离开 ", type, customer.id);
  10.     if (event.occurTime > closeTime) { //用户办理业务时已经关门了
  11.         printf("× 他是%dmin到达的，预计办理业务所花费的时间为%dmin，预计离开时间是%dmin。但排到队时已经是%d了，只好改天再来\n", customer.arrivalTime, customer.duration, customer.arrivalTime+customer.duration ,event.occurTime);
  12.         customerNum--; //去掉这个用户
  13.         return ;
  14.     } else {
  15.         printf("√ 离开时间%d（即当前时钟的时间）\n", event.occurTime);
  16.         totalTime += event.occurTime - customer.arrivalTime; //客户等待的时间=当前时间-客户到达店里的时间
  17.         if ( QueueLength(windows[type]) ) {
  18.             // 当前窗口还有人
  20.             // 开始处理下一位
  21.             p = windows[type].front->next;
  22.             qe = p->data;
  23.             customer.arrivalTime = qe.arrivalTime; //开始时间
  24.             customer.duration = qe.duration;       //持续时间
  25.             event.occurTime = event.occurTime + customer.duration; //事件的发生时间
  26.             event.type = type;    //type号窗口开始处理该用户
  27.             OrderInsert(&eventList, event); //插入到事件链表中等待离队
  28.         }
  29.     }
  30. }

总结：离散事件模拟思想的本质

  1. 以上逻辑其实是有模拟时间的，但你也许搞不明白，并没有设置一个currentTime变量存储当前的时间点
  2. 没错，确实是没有。但是我们有一个全局变量event事件，我们模拟的是事件的处理，当前处理的时间event，它所发生的时间event.occurTime就是目前时间啊！
  3. 所以，离散事件的模拟实质就是
    • 随机出很多个事件eventList，然后按时间发生event.occurTime的先后来处理这些事件。处理每个时间event时，event.occurTime就是当前的时间点。其时间的步长正是一个事件！具体分析看下图右侧文字

[离散事件模拟] 银行窗口模拟 - 图4

完整代码

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  5. #define MAX 10000
  6. #define WINDOWS_NUM 4 //银行的窗口数
  8. // 链表类型：有头的单链表
  10. /****** 事件 ******/
  11. typedef struct{
  12.     long occurTime; //事件发生时刻
  13.     int type;        //事件的类型
  14.         // type = 0：预计会有下一个用户到达
  15.         // type != 0：为其他值时，表示该用户在type窗口已经正在办理业务（type=1，表示该用户在窗口1正在处理业务）
  16. }LElemType;
  17. typedef LElemType Event; //事件
  18. typedef struct LNode{
  19.     Event data;
  20.     struct LNode *next;
  21. }LNode, *LinkList; 
  22. typedef LinkList EventList; //事件链表类型（有序链表）
  24. /****** 客户 ******/
  25. typedef struct{
  26.     long arrivalTime; //到达时间
  27.     long duration;    //办理业务所需时间
  28.     int id; //用户的id
  29. }QElemType;
  30. typedef QElemType Customer; //客户
  32. /****** 客户队列 ******/ 
  33. typedef struct QNode{
  34.     QElemType data;
  35.     struct QNode *next;
  36. }QNode, *QueuePtr;
  37. typedef struct{
  38.     QueuePtr front; //队头
  39.     QueuePtr rear;  //队尾
  40. }LinkQueue;
  41. typedef LinkQueue CustomerQueue; //客户队列
  43. void BankSimulation(int closeTime); //银行模拟
  44. void OpenForDay();            //开店
  45. void CloseForDay();            //关店
  46. int GetMin(LinkQueue q[]);  //得到人最少的窗口
  47. void CustomerArriving(int closeTime); //预计用户到来
  48. void CustomerDeparture(int closeTime); //用户离开
  50. /***** 链表操作 ******/
  51. void InitList(LinkList *pL);
  52. int ListEmpty(LinkList L);
  53. void OrderInsert(LinkList *pL, LElemType en);
  54. void DelFirst(LinkList *pL, LElemType *e);
  57. /***** 队列操作 ******/
  58. void InitQueue(LinkQueue *Q);
  59. int DelQueue(LinkQueue *pQ, QElemType *e);
  60. int EnQueue(LinkQueue *pQ, QElemType e);
  61. int QueueLength(LinkQueue Q);
  64. int totalTime=0, customerNum=0; //累计客户逗留时间，客户数
  65. EventList eventList; //事件表
  66. Event event; //事件
  67. CustomerQueue windows[WINDOWS_NUM+1]; //窗口，从1开始存储
  68. Customer customer; //客户记录
  69. int main() {
  70.     int closeTime; //关门时间
  72.     srand(time(NULL)); //设置随机种子，注意：一定要在main函数里，不能放在Random()里，否则无效
  74.     printf("输入营业的总分钟数：\n>>> ");
  75.     scanf("%d", &closeTime);
  76.     BankSimulation(closeTime);
  78.     return 0;
  79. }
  81. // 银行模拟
  82. void BankSimulation(int closeTime) {
  83.     OpenForDay(); //开门
  84.     while ( !ListEmpty(eventList) ) {
  85.         // 事件队列还有事件没有处理完
  86.         DelFirst(&eventList, &event); //取出第一个事件，并删除
  87.         if (event.type==0) //预计有新用户达到
  88.             CustomerArriving(closeTime); //生成这个用户几点来
  89.         else //用户正在办理业务
  90.             CustomerDeparture(closeTime); //用户离开事件
  91.     }
  92.     CloseForDay();
  93. }
  95. // 银行开门：初始化
  96. void OpenForDay() {
  97.     int i;
  98.     totalTime = 0;  //总时间
  99.     customerNum = 0; //客户数
  101.     InitList(&eventList); //初始化事件列表
  102.     //银行一开门，就预计有下一个用户到来
  103.     event.occurTime = 0;
  104.     event.type = 0;
  105.     OrderInsert(&eventList, event); //插入到事件列表
  106.     for (i=1; i<=WINDOWS_NUM; i++) {
  107.         InitQueue(&windows[i]); //初始化银行窗口
  108.     }
  109.     printf("\n△ start 预计下一个用户会来（生成下一个用户到达的事件）\n");
  110. }
  112. void CloseForDay() {
  113.     printf("\n△ 客户数=%ld，累计客户逗留时间%ld，平均逗留时间%ld\n", customerNum, totalTime, totalTime/customerNum);
  114. }
  116. // 预测用户到达事件
  117. void CustomerArriving(int closeTime) {
  118.     long durtime, intertime;
  119.     int minWindow;
  121.     customerNum++; //客户量+1
  122.     printf("\t预测第%d客户", customerNum);
  124.     // 创建用户
  125.     durtime = rand()%15 +1; //一个业务的时间在1-15分钟
  126.     intertime = rand()%6; //用户间隔0-5分钟来一个
  127.     customer.id = customerNum; // 这是今天第几个用户了
  128.     customer.arrivalTime = event.occurTime + intertime; //到达时间
  129.     customer.duration = durtime;                        //客户办事的持续时间
  130.     if ( customer.arrivalTime >= closeTime ) { //用户来的时候已经关门了
  132.         printf("\t× 生成的下一个用户将在第%dmin到达，那时候已经关门了\n", customer.arrivalTime);
  134.     } else { //用户来的时候还没有关门
  136.         // 插入最短队
  137.         minWindow = GetMin(windows);                        //得到人数最少的队列
  138.         EnQueue(&windows[minWindow], customer);                //插入最短的队伍
  139.         printf("将在第%dmin到达，办理业务需要%dmin，到窗口%d排队", customer.arrivalTime, customer.duration, minWindow);
  141.         // 插入离开事件
  142.         event.occurTime = customer.arrivalTime + durtime; //预计离开时间
  143.         printf("，预计离开时间%dmin\n", event.occurTime);
  144.         event.type = minWindow; //窗口
  145.         if ( QueueLength(windows[minWindow]) ==1 ) //当前队伍只有他一个人
  146.             OrderInsert(&eventList, event); //插入离开事件，让这个人离开
  148.         // 预计下一个用户的到达
  149.         event.occurTime = customer.arrivalTime; //创建下一个用户到达的事件
  150.         event.type = 0;
  151.         if ( event.occurTime < closeTime ) //如果预计时间已经关门了，就退出
  152.             OrderInsert(&eventList, event);
  154.     }
  155. }
  157. // 事件处理完成，用户离开
  158. void CustomerDeparture(int closeTime) {
  159.     int type; //窗口号
  160.     QNode *p;
  161.     QElemType qe;
  163.     type = event.type; //窗口号
  164.     DelQueue(&windows[type], &customer); //得到出队的用户
  165.     printf("窗口%d %d号用户离开 ", type, customer.id);
  166.     if (event.occurTime > closeTime) { //用户办理业务时已经关门了
  167.         printf("× 他是%dmin到达的，预计办理业务所花费的时间为%dmin，预计离开时间是%dmin。但排到队时已经是%d了，只好改天再来\n", customer.arrivalTime, customer.duration, customer.arrivalTime+customer.duration ,event.occurTime);
  168.         customerNum--; //去掉这个用户
  169.         return ;
  170.     } else {
  171.         printf("√ 离开时间%d（即当前时钟的时间）\n", event.occurTime);
  172.         totalTime += event.occurTime - customer.arrivalTime; //客户等待的时间=当前时间-客户到达店里的时间
  173.         if ( QueueLength(windows[type]) ) {
  174.             // 当前窗口还有人
  176.             // 开始处理下一位
  177.             p = windows[type].front->next;
  178.             qe = p->data;
  179.             customer.arrivalTime = qe.arrivalTime; //开始时间
  180.             customer.duration = qe.duration;       //持续时间
  181.             event.occurTime = event.occurTime + customer.duration; //事件的发生时间
  182.             event.type = type;    //type号窗口开始处理该用户
  183.             OrderInsert(&eventList, event); //插入到事件链表中等待离队
  184.         }
  185.     }
  186. }
  188. // 得到人数最少的队列
  189. int GetMin(LinkQueue q[]) {
  190.     int i,k,min;
  191.     int cnt;
  192.     QNode *p;
  194.     min = MAX;
  195.     for (i=1; i<=WINDOWS_NUM; i++) {
  196.         if ( q[i].front == q[i].rear ) { // 该窗口没有人
  197.             cnt = 0; //窗口人数=0
  198.         } else { //该窗口有人
  199.             // 计算目前窗口的人数
  200.             for (cnt=1,p=q[i].front->next; p!=q[i].rear; p=p->next) { 
  201.                 cnt++;
  202.             }
  203.         }
  204.         if (min>cnt) {
  205.             min = cnt;
  206.             k = i;
  207.         }
  208.     }
  209.     return k;
  210. }
  212. /***** 链表操作 ******/
  213. // 有头结点的单链表
  214. void InitList(LinkList *pL) { //链表初始化
  215.     *pL = (LNode *)malloc(sizeof(LNode));
  216.     if (!*pL) exit(0);
  217.     (*pL)->next = NULL;
  218. }
  220. int ListEmpty(LinkList L) {
  221.     return L->next==NULL ? 1 : 0; //L的下一个为空 ？ 是空 ： 不空
  222. }
  224. void OrderInsert(LinkList *pL, LElemType en) { //按occurTime从小到大的顺序插入
  225.     LNode *p, *q, *s;
  227.     for (p=*pL,q=p->next; q && q->data.occurTime<en.occurTime; p=q,q=p->next) ; //找到插入位置
  228.     s = (LNode *)malloc(sizeof(LNode)); if (!s) exit(0);
  229.     s->data.type = en.type; s->data.occurTime = en.occurTime;
  230.     p->next = s;
  231.     s->next = q;
  232. }
  234. void DelFirst(LinkList *pL, LElemType *e) {
  235.     LNode *p;
  236.     p = (*pL)->next;
  237.     (*pL)->next = p->next;
  238.     e->occurTime = p->data.occurTime;
  239.     e->type = p->data.type;
  240.     free(p);
  241. }
  244. /***** 队列操作 ******/
  245. // 有头结点的单链表
  246. void InitQueue(LinkQueue *Q) {
  247.     Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
  248.     Q->front->next = NULL;
  249. }
  251. int DelQueue(LinkQueue *pQ, QElemType *e) {
  252.     QNode *p;
  253.     if ( (*pQ).front == (*pQ).rear ) return 0; //空
  254.     p = (*pQ).front->next;
  255.     e->arrivalTime = p->data.arrivalTime;
  256.     e->duration = p->data.duration;
  257.     e->id = p->data.id;
  258.     (*pQ).front->next = p->next;
  259.     if ( (*pQ).rear == p ) //删除一个后，队列变空了
  260.         (*pQ).rear = (*pQ).front;
  261.     free(p);
  262.     return 1;
  263. }
  265. int EnQueue(LinkQueue *pQ, QElemType e) {
  266.     QNode *p;
  267.     p = (QNode *)malloc(sizeof(QNode)); if (!p) exit(0);
  268.     p->data.arrivalTime = e.arrivalTime;
  269.     p->data.duration = e.duration;
  270.     p->data.id = e.id;
  271.     p->next = NULL;
  272.     (*pQ).rear->next = p;
  273.     (*pQ).rear = p;
  274.     return 1;
  275. }
  277. int QueueLength(LinkQueue Q) {
  278.     int cnt=0;
  279.     QNode *p;
  280.     if ( Q.front==Q.rear ) cnt=0;
  281.     else {
  282.         for ( p=Q.front; p!=Q.rear; p=p->next ) cnt++;
  283.     }
  284.     return cnt;
  285. }