c++ - 如何提高疯子候机程序的效率

Question

我最近写了一个关于 crazy guy waiting aircraft 问题的程序，它说:

100 名航空公司乘客正在排队等候登机。他们每人都持有该航类 100 个座位之一的机票。 (为方便起见，假设排队的第 n 位乘客有一张座位号为 n 的票。) 不幸的是，排在第一位的人疯了，会无视票上的座位号，随便选一个座位。所有其他乘客都很正常，除非已经有人，否则他们会去他们合适的座位。如果它被占用，他们会随机找一个空闲的座位坐下。 最后一个(第 100 个)登机的人坐在正确座位 (#100) 上的概率是多少？

我做了 monte carlo 来得到答案，但效率不高，因为对于乘客来说，谁的座位就在哪里。我先得到一个随机数，然后从第一个座位开始检查，如果是选址，则跳过那个。

顺便说一句，答案应该是 1/2 :)

有人有更好的主意来做这个吗？

#include <iostream>
#include <vector>
#include <random>

using namespace std;

mt19937 generator;
uniform_real_distribution<double> ranuni(0, 1);

bool test(){
    vector<int> line(100, 0);

    int remaining(100);
    int temp = remaining * ranuni(generator);
    if (temp == 99)
    return 0;
    line[temp] = 1;
    --remaining; 

    for (int i = 1; i < 99; ++i){
        temp = remaining * ranuni(generator);

        auto itr = line.begin();
        while (temp != 0){
            ++itr;
            if (*itr == 0)
                --temp;
        }
        if (itr == line.end()-1)
            return 0;
        else
            *itr = 1;
        --remaining;
    }

    return 1;
}

int main(){
cout << "please input number of simulations" << endl;
int num;
cin >> num;

int sum(0);
for (int i = 0; i < num; ++i)
    sum += test();

cout << double(sum) / double(num) << endl;

return 0;
}

Answer 1

我将提供一些想法。不过，可能不是一个确定的答案。

首先，我想知道:如果您预先计算出一个“随机”使用的飞机座位列表，这会有帮助吗？这个想法是:当一位乘客试图坐在他/她的座位上并发现它已被占用时，您只需从列表中弹出值直到找到一个未被占用的值，而不是调用 random()。您可以将它们弹出，因为您也不希望后来的乘客浪费时间考虑那些(已占用的)座位。这意味着您要避免在行尾附近出现随机数生成器不断生成已占用座位的问题。 (虽然，我看到的不是你的，因为当分配的座位被占用时，你确定性地找到一个空闲的座位)。给定这样一个打乱的座位分配列表，可以非常快速、轻松地评估原始问题。

真正的问题是生成这个“打乱”的列表与原来的问题完全一样(对于0..99中的ticket#，将ticket#放入slot(random)中。它是否被占用？等等)所以，考虑到生成一个经过精心打乱的座位分配列表与原始问题具有相同的复杂性，有没有一种方法可以让我们多次简化这项工作？

这让我想到了第二个想法:一旦你有了一个这样的随机列表，就有很多方法可以创建其他列表，这比对 random() 额外调用 100 次要容易得多。例如，只需交换两个值。结果列表代表问题的不同运行，乘客的选择略有不同。这样做很多次，你会得到很多不同的运行。

不过，我不能完全回答的部分是如何确保您获得的样本对问题空间有良好的采样(这是蒙特卡洛给您好的结果所必需的)。我得把它留给别人。