通过询问组测试查询来从有限集合S = {1,2,…, n }中检测未知元素x ∗是经典的组合优化问题。 我们考虑问题的一个变化,就是我们所说的骗子搜索游戏小套[N,E,≤k]和制定,如下所示:两名球员,说保罗和Carole,修复整数k≥1,M> 0, Ë≥0提前。 保罗问大小的限制查询,发现X *:“为X *在A”,其中A⊆S和| 一个|≤ķ。 Carole回答“是”或“否”,以告诉x ∗是否属于A。 卡洛尔最多可以说谎e次。 如果保罗在m轮内发现x ∗,他将获胜; 否则,Carole获胜。 我们的目标是确定m的最小值,以确保Paul获胜。 令f(N,E,≤k)的=分钟{M |保罗赢得游戏[N
1