[算法求助] 如何快速猜到 upper limit

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2041 天前的主题，其中的信息可能已经有所发展或是发生改变。

给定两个整数 a, b, 其中 a<=b. 给定一个函数, bool is_greater(int c), 当 c>b 时返回 true. 告知 a, 要猜 b, 怎么做最有效?

brute force 的话, 就是让 c=a, 逐渐+1, 直到is_greater(c)==false, 则 b=c-1

第 1 条附言 · 2019-04-23 14:21:11 +08:00

更具体一些. b 就在 uint_32 的范围内. 最有效指的是调用 is_greater 函数的次数的期望值最小.

第 2 条附言 · 2019-04-23 16:31:55 +08:00

再限定一下. 那就给个指数分布吧. 用意是 b 更可能出现在离 a 较近的地方. pdf(b-a)=exp(-(b-a))

第 3 条附言 · 2019-04-23 17:38:14 +08:00

上面两条有冲突. 那就分两种情况吧.
1. b <= uint32_max. b 在(a, uint32_max] 上取值服从均匀分布
2. b 无上限. b 在(a, +Inf) 上取值服从指数分布

给出任意一种情况的最优解都行. 最好有推理证明或思路. 渐进 /次优解也是可以的. 反正就是想看看各种新奇的方法.

is_greater

给定

Upper

brute

15 条回复 • 2019-04-23 22:31:31 +08:00

thedrwu

2019-04-23 12:46:19 +08:00 via Android

二分

lance6716

2019-04-23 12:49:41 +08:00 via Android

Exponential search

nanaw

2019-04-23 12:53:06 +08:00

得有个 b 最大的可能范围才能二分吧。这样无限大怎么猜。。

geelaw

2019-04-23 12:55:01 +08:00

如果你假设 int 是有限范围，可以直接二分，甚至不需要知道 a。

如果你假设 int 是无限范围且 a < 0，则先通过测试 -1、0 确定 b 的符号；如果 b 是负数，则你已经有上下界，用二分；如果 b 是 0，则结束；如果 b 是正数，则不断测试一个数是否是上界，直到找到上下界，再用二分。

你需要定义什么叫做“最有效”，才能决定如何询问“最有效” 。

Kirscheis

2019-04-23 13:07:05 +08:00 via Android

先指数前进，然后二分即可

rrfeng

2019-04-23 13:22:41 +08:00 via Android

如果我操作的话选指数前进，再二分定位。

但实际上感觉可以算出来期望次数

melonux

2019-04-23 14:19:04 +08:00

@nanaw 肯定有限大啊, 都是给定值了. 不需要预先假设 b-a 的范围的.

melonux

2019-04-23 14:20:26 +08:00

@geelaw 好的. 更具体一些. b 就在 uint_32 的范围内. 最有效指的是调用 is_greater 函数的次数的期望值最小.

melonux

2019-04-23 14:23:54 +08:00

@lance6716 嗯. 很有价值

geelaw

2019-04-23 15:02:27 +08:00

@melonux #8 你仍然没有定义好什么叫“最有效”，你没有指定固定 a 后 b 的条件分布。

一旦有了这个分布，你可以做动态规划来算出最佳策略。

melonux

2019-04-23 16:31:05 +08:00

嗯. 您这个考虑更加精细了. 那就给个指数分布吧. 用意是 b 更可能出现在离 a 较近的地方. pdf(b-a)=exp(-(b-a))

melonux

2019-04-23 16:35:50 +08:00

@geelaw 很想知道这个怎么动态规划

lance6716

2019-04-23 17:18:34 +08:00

@melonux 指数分布是无记忆的（不知道在这个离散程度和规模下能不能这么概括），给定搜索的区间[low, high]，只跟区间长度有关

均匀分布的时候二分中点。不均匀就二分“累计概率达到一半”的那个点

melonux

2019-04-23 17:35:16 +08:00

@lance6716 嗯. 您说的对. 给定范围和给定这个分布本身冲突了. 我的本意是均匀分布即可. 但看到那个可以动态规划的方法, 就很好奇. 想看到一个不平凡的解, 所以给了一个不均匀的分布.

geelaw

2019-04-23 22:31:31 +08:00 via iPhone

@melonux #12 如果是均匀分布显然二分法就是动态规划会给出的解。如果是几何分布，不妨设 a=0 （其他情况把各数虚拟地加上 -a 即可），用 f(x) 表示上界是 c 时（也就是范围是 (0, x]）最小期望次数，那么

f(1) = 0
f(n) = 1 + min ( Pr[b>c] f(n-c) + Pr[b<=c] f(c) )

对于初始无上界的情况，这是一个 Markov 链，因此有

f(infty) = 1 + inf ( Pr[b>c] f(infty) + Pr[b<=c] f(c) )

f(infty) = inf (1/Pr[b<=c] + f(c))

利用有限值的 f 的情况算出最佳的 c。