离散事件模拟--银行排队时间模拟

深藏阁楼爱情的钟 2022-08-08 03:24 149阅读 0赞

在数据结构中有个讲述如何模拟银行排队，最终算出每个人平均的逗留时间。

这是需要数据结构的知识。将银行的每个窗口看成是一个队列，那么对于每次来一个人，都需要从最短的队列进行排队。（其实更优秀的做法是从最短的等待时间队列来排队）。

这里的做法是这样的，首选在一个队列中插入一个人，整个事件是事件驱动的，每次去检查所有队列，删除那些业务用时已经超出的人，然后选择最短的队列来插入一个人，也就是说，每次插入一个人之前就需要清除队列中的人。然后再选择合适的队列来插入新的人。

其实更合理更简单的逻辑是：先说一个队列，可以假设一个循环花费1s时间，对于每一个循环，都采用一定的方法（比如随机数）来判断是否有新人来办理业务，有新人则再随机确定耗费时长，然后再将对头的耗时减去1，判断当前队列中是否有已经可以出队的人，如果有，就出队，如果没有，继续循环。

至于多个队列，需要注意的就是每次插入都需要插入人少的队列，然后循环处理所有队列，看是否可以出队

#include <iostream>
    #include <vector>
    #include <deque>
    #include <stdlib.h> 
    #include <time.h> 
    #include <numeric>
    #include <limits>
    using namespace std;
    /*
    模拟一个离散时间情形 
    比如银行的排队系统，记录每一个客户的平均逗留时间 
    */
    /*
    思路：假设银行有多个窗口，那么每个窗口就是每个队列，我们
    记录在规定时刻 或者所有窗口再次为空的情况下结束事件的模拟 
    */
    
    #define CloseTime 10000  //最长的模拟事件是10000分钟以后关闭事件的模拟
    
    typedef struct Record Record;
    struct Record
    {
    	int ArrivedTime;// 到达时间
    	int CostTime;// 办理业务的时间
    };
    
    void Init(vector<deque<Record> >& win)
    {
    	srand((unsigned)time(NULL)); 
        int costtime = rand()%100;
    	Record customer;
    	customer.ArrivedTime =0;
    	customer.CostTime = costtime;
    	win[0].push_back(customer);
    }
    void Bank_Simulation(int WinNum)
    {
    	double CustomerNum=1,TotalTime=0;
    	int CurTime=0;
    	int flag =1;
    	int LenDeque,index,i;
    	Record temp;
    	vector<deque<Record> > Win(WinNum);
    	srand((unsigned)time(NULL)); 
    	Init(Win);
    
    	while(flag)
    	{
    		flag = 0;
    		LenDeque = numeric_limits<int>::max();
    		for(i=0;i<Win.size();i++)
    		{
    
    			if(Win[i].size() == 0)
    			{
    				LenDeque = Win[i].size();	
    				index = i;
    				continue;
    			}
    			
    			else
    			{
    			
    				flag =1;
    				while(Win[i].size())
    				{
    					temp = Win[i].front();
    					if(temp.ArrivedTime + temp.CostTime < CurTime)
    					{
    						Win[i].pop_front();
    						TotalTime += temp.CostTime;
    						
    					}					
    					else
    						break;
    				}
    			    if(Win[i].size() < LenDeque)
    				{
    					LenDeque = Win[i].size();
    					index = i;
    				}
    				
    			}	
    		} 		
    		if(flag ==0)
    			break;
    		if(CurTime >10000)
    			break;
    		cout<<"===="<<endl;
    		int arrivetime = rand()%15;
    		temp.ArrivedTime = arrivetime+CurTime;
    		temp.CostTime = rand()%30;
    		CurTime = temp.ArrivedTime; 
    		Win[index].push_back(temp);	
    		CustomerNum++;
    		
    	}
    	cout<<TotalTime<<endl;
    	cout<<CustomerNum<<endl;
    	cout<<TotalTime/CustomerNum<<endl;
    }
    
    int main() 
    {
    	Bank_Simulation(4);
     
    	return 0;
    }