ATM队列模拟结果不收敛：问题排查及解决方案请求

阅读《C++ Primer Plus》中的「队列模拟」章节后，实现了ATM队列模拟程序，计划多次运行程序计算平均值以观察结果趋近的稳定值，但实际结果并未收敛，甚至出现负等待时间的异常情况。

程序代码 #

test.h #

// queue.h  -- interface for a queue
#pragma once
class Customer
{
private:
    long arrive;    // arrival time for customer
    int processtime;    // processing time for customer
public:
    Customer() { arrive = processtime = 0; }
    void set(long when);
    long when() const { return arrive; }
    int ptime() const { return processtime; }
};

typedef Customer Item;

class Queue
{
private:
    //class scope definitions
    //Node is nested structure definition local to this class
    struct Node { Item item; struct Node* next; };
    enum {Q_SIZE = 10};
    //private class members
    Node* front;        // pointer to front of Queue
    Node* rear;         // pointer to rear of Queue
    int items;          // current number of items
    const int qsize;    // maximum number of items
    // preemptive definitions to prevent public copying
    Queue(const Queue& q) : qsize(0) {};
    Queue& operator=(const Queue& q) { return *this; }
public:
    Queue(int qs = Q_SIZE); //create queue with a qs limit
    ~Queue();
    bool isempty() const;
    bool isfull() const;
    int queuecount() const;
    bool enqueue(const Item& item);     // add item to end
    bool dequeue(Item& item);           // remove item from front
};

test.cpp #

// queue.cpp -- Queue and Customer methods
#include "test.h"
#include <cstdlib>

// Queue methods
Queue::Queue(int qs) : qsize(qs)
{
    front = rear = NULL;    // or nullptr
    items = 0;
}

Queue::~Queue()
{
    Node* temp;
    while (front != NULL)   // while queue is not yet empty
    {
        temp = front;       // save address of front item
        front = front->next;// reset pointer to next item
        delete temp;        // delete former front
    }
}

bool Queue::isempty() const
{
    return items == 0;
}

bool Queue::isfull() const
{
    return items == qsize;
}

int Queue::queuecount() const
{
    return items;
}

// Add item to queue
bool Queue::enqueue(const Item& item)
{
    if (isfull())
        return false;
    Node* add = new Node;   // create node
    // on failure, new throws std::bad_alloc exception
    add->item = item;       // set node pointers
    add->next = NULL;       // place item at front  
    items++;
    if (front == NULL)      // if queue is empty
        front = add;        // place rear point to new node
    else
        rear->next = add;   // else place at rear
    rear = add;             // have rear point to new node
    return true;
}

// Place front item into variable and remove from queue
bool Queue::dequeue(Item& item)
{
    if (front == NULL)
        return false;
    item = front->item;     // set item to first in queue
    items--;
    Node* temp = front;     // save location of first item
    front = front->next;    // reset front to next item
    delete temp;            // delete former first item
    if (items == 0)
        rear = NULL;
    return true;
}

// custormer method
// when is the time at which the customer arrives
// the arrival tiem is set to when and the processing
// time set to a random value in the rang 1 -3
void Customer::set(long when)
{
    processtime = std::rand() % 3 + 1;
    arrive = when;
}

simulat.cpp #

#include <iostream>
#include <cstdlib>      // for rand() and srand()
#include <ctime>        // for time()
#include "test.h"
const int MIN_PER_HR = 60;  // 60 minutes a hour
using std::cout;
using std::endl;

struct SimulationStats {
    long customers;     // joined the queue
    long served;        // served during the simulation
    long turnaways;     // turned away by full queue
    double avgQueueSize;  // average queue size
    double avgWaitTime;   // average wait time
    
    SimulationStats() : customers(0), served(0), turnaways(0), avgQueueSize(0), avgWaitTime(0) {}
};

// x = average time, in minutes between customers
// return value is true if customre shows up this minute
static bool newcustomer(double x)
{
    return (std::rand() * x / RAND_MAX < 1);
}

void simulate(int times, int qs, int hr, double ph)
{
    Queue line(qs);     // line queue holds up to qs people
    long cyclelimit = MIN_PER_HR * hr;  
    // simoulation will run 1 cycle per minute
    double min_per_cust = MIN_PER_HR / ph;  // average time between arrivals
    
    Item temp;          // new customer data
    long turnaways = 0; // turned away by full queue
    long customers = 0; // joined the queue
    long served = 0;    // served during the simulation
    long sum_line = 0;  // cumulative line length
    int wait_time = 0;  // time until autoteller is free
    long line_wait = 0; // cumulative time in line
    SimulationStats status;

    std::srand(std::time(0));   // random initializing for rand()
    
    for (int t = 0; t < times; t++)
    {
        for (int cycle = 0; cycle < cyclelimit; cycle++)
        {
            if (newcustomer(min_per_cust))  // have newcomer
            {
                if (line.isfull())
                    turnaways++;
                else
                {
                    customers++;
                    temp.set(cycle);    // cycle = time of arrival
                    line.enqueue(temp); // add newcomer to line
                }
            }
            if (wait_time <= 0 && !line.isempty())
            {
                line.dequeue(temp);     // attend next customer
                wait_time = temp.ptime();   // for wait_time minutes
                line_wait += cycle - temp.when();
                served++;
            }
            if (wait_time > 0)
                wait_time--;
            sum_line += line.queuecount();
        }

        //  customers
        status.customers += customers;
        //  customers served
        status.served += served;
        //  turnaways
        status.turnaways += turnaways;
        // average queue size
        status.avgQueueSize += static_cast<double>(sum_line) / cyclelimit;
        // average wait time
        status.avgWaitTime += served > 0 ? static_cast<double>(line_wait) / served : 0;
    }
    // reporting results
    cout << "After " << times << " times simulations: " << endl;
    cout << "Average customers accepted: " << status.customers / times << endl;
    cout << "Average customers served: " << status.served / times << endl;
    cout << "Average turnaways: " << status.turnaways / times << endl;
    cout.precision(2);
    cout.setf(std::ios_base::fixed, std::ios_base::floatfield);
    cout << "Average queue size: " << status.avgQueueSize / times << endl;
    cout << "Average wait time: " << status.avgWaitTime / times << endl;
}

int main()
{
    simulate(5, 10, 4, 30);
    return 0;
}

模拟结果 #

5次模拟结果 #

After 5 times simulations:
Average customers accepted: 343
Average customers served: 337
Average turnaways: 11
Average queue size: 12.83
Average wait time: -1.44

50次模拟结果 #

After 50 times simulations:
Average customers accepted: 2901
Average customers served: 2897
Average turnaways: 80
Average queue size: 104.26
Average wait time: 1.43

500次模拟结果 #

After 500 times simulations:
Average customers accepted: 29040
Average customers served: 29035
Average turnaways: 967
Average queue size: 1155.43
Average wait time: -0.32

问题排查与解决方案 #

核心问题分析 #

1. 模拟状态未重置：simulate函数中，队列和统计变量（turnaways、customers、served等）仅初始化一次，多次模拟时这些变量会持续累加，而非每次模拟独立运行，导致结果随模拟次数线性增长，无法收敛。
2. 随机种子重复：std::srand(std::time(0))放在模拟循环外，若模拟运行速度快（如500次模拟在1秒内完成），多次模拟会使用相同的随机种子，生成重复的随机序列，破坏模拟的随机性。
3. 负等待时间异常：前一次模拟结束后，队列中剩余的未服务顾客会被带入下一次模拟，而下次模拟的时间cycle从0开始，导致cycle - temp.when()出现负数（temp.when()是上一次模拟的时间，远大于0）。

修正后的关键代码（simulate函数） #

void simulate(int times, int qs, int hr, double ph)
{
    long cyclelimit = MIN_PER_HR * hr;  
    double min_per_cust = MIN_PER_HR / ph;

    SimulationStats status;

    for (int t = 0; t < times; t++)
    {
        // 每次模拟重新初始化队列和统计变量
        Queue line(qs);
        Item temp;
        long turnaways = 0;
        long customers = 0;
        long served = 0;
        long sum_line = 0;
        int wait_time = 0;
        long line_wait = 0;

        // 每次模拟使用不同的随机种子，避免重复序列
        std::srand(std::time(0) + t); 

        for (int cycle = 0; cycle < cyclelimit; cycle++)
        {
            if (newcustomer(min_per_cust))
            {
                if (line.isfull())
                    turnaways++;
                else
                {
                    customers++;
                    temp.set(cycle);
                    line.enqueue(temp);
                }
            }
            if (wait_time <= 0 && !line.isempty())
            {
                line.dequeue(temp);
                wait_time = temp.ptime();
                line_wait += cycle - temp.when();
                served++;
            }
            if (wait_time > 0)
                wait_time--;
            sum_line += line.queuecount();
        }

        // 累加单次模拟的统计结果
        status.customers += customers;
        status.served += served;
        status.turnaways += turnaways;
        status.avgQueueSize += static_cast<double>(sum_line) / cyclelimit;
        status.avgWaitTime += served > 0 ? static_cast<double>(line_wait) / served : 0;
    }

    // 输出平均结果，注意强制转换为double避免整数除法
    cout << "After " << times << " times simulations: " << endl;
    cout << "Average customers accepted: " << static_cast<double>(status.customers) / times << endl;
    cout << "Average customers served: " << static_cast<double>(status.served) / times << endl;
    cout << "Average turnaways: " << static_cast<double>(status.turnaways) / times << endl;
    cout.precision(2);
    cout.setf(std::ios_base::fixed, std::ios_base::floatfield);
    cout << "Average queue size: " << status.avgQueueSize / times << endl;
    cout << "Average wait time: " << status.avgWaitTime / times << endl;
}

修正说明 #

• 将队列和统计变量的初始化移至外层循环内部，确保每次模拟都是独立的全新状态。
• 每次模拟重新设置随机种子，通过std::time(0) + t避免同一秒内多次模拟的种子重复。
• 输出平均结果时，将整数变量强制转换为double，避免整数除法导致的精度丢失。
• 移除跨模拟的状态残留，彻底解决负等待时间问题。

内容的提问来源于stack exchange，提问作者Zachary