X****r
发帖数: 3557 | 1 这涉及到你对对方的策略的知识(e.g.先验分布).
1.如果你知道或你们约定TA一定会站着不动, 那你无疑应该到处乱跑. 如果把
SUPERMKT模型为二维平面网格, 定义曼哈顿距离, 那么这又涉及到你对TA当
时离你的距离的分布的先验知识或模型.
1.1.如果这个类似于指数分布, 可能螺旋式地往外找更好些
1.2.如果这个类似于均匀分布, 可能你怎么走都一样, 只要不走重复路线.
1.3.如果你根本没有这个先验知识, 那么就不能用期望来评价某种算法的优劣,
而要代之以在最坏情况下与最优算法的结果之比例, 目的是使这个比例为
最大. 直觉认为螺旋式地往外找或随机游动比较好, 两者的比例可能都是
1/O(d)左右.
2.如果你知道TA一定是某一种走法, 比如螺旋式地往外找, 那么也许你站着不
动和也是螺旋式地外找的期望相仿, 但最坏情况就差别很大, 所以还是站着
不动吧...
3.要是根本就不知道TA会怎么走, 就很复杂了, 参见(1.3) 的讨论. 一个可行
的方案是站着不动T 时间, 随机游动T 时间, 站着不动2T时间, 随机游动2T
|
|
