V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
melonux
V2EX  ›  问与答

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

  •  
  •   melonux · 2019-04-23 12:40:02 +08:00 · 1746 次点击
    这是一个创建于 2039 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定两个整数 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) 上取值服从指数分布

    给出任意一种情况的最优解都行. 最好有推理证明或思路. 渐进 /次优解也是可以的. 反正就是想看看各种新奇的方法.
    15 条回复    2019-04-23 22:31:31 +08:00
    thedrwu
        1
    thedrwu  
       2019-04-23 12:46:19 +08:00 via Android
    二分
    lance6716
        2
    lance6716  
       2019-04-23 12:49:41 +08:00 via Android   ❤️ 2
    Exponential search
    nanaw
        3
    nanaw  
       2019-04-23 12:53:06 +08:00
    得有个 b 最大的可能范围才能二分吧。这样无限大怎么猜。。
    geelaw
        4
    geelaw  
       2019-04-23 12:55:01 +08:00
    如果你假设 int 是有限范围,可以直接二分,甚至不需要知道 a。

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

    你需要定义什么叫做“最有效”,才能决定如何询问“最有效” 。
    Kirscheis
        5
    Kirscheis  
       2019-04-23 13:07:05 +08:00 via Android   ❤️ 1
    先指数前进,然后二分即可
    rrfeng
        6
    rrfeng  
       2019-04-23 13:22:41 +08:00 via Android
    如果我操作的话选指数前进,再二分定位。

    但实际上感觉可以算出来期望次数
    melonux
        7
    melonux  
    OP
       2019-04-23 14:19:04 +08:00
    @nanaw 肯定有限大啊, 都是给定值了. 不需要预先假设 b-a 的范围的.
    melonux
        8
    melonux  
    OP
       2019-04-23 14:20:26 +08:00
    @geelaw 好的. 更具体一些. b 就在 uint_32 的范围内. 最有效指的是调用 is_greater 函数的次数的期望值最小.
    melonux
        9
    melonux  
    OP
       2019-04-23 14:23:54 +08:00
    @lance6716 嗯. 很有价值
    geelaw
        10
    geelaw  
       2019-04-23 15:02:27 +08:00   ❤️ 1
    @melonux #8 你仍然没有定义好什么叫“最有效”,你没有指定固定 a 后 b 的条件分布。

    一旦有了这个分布,你可以做动态规划来算出最佳策略。
    melonux
        11
    melonux  
    OP
       2019-04-23 16:31:05 +08:00
    嗯. 您这个考虑更加精细了. 那就给个指数分布吧. 用意是 b 更可能出现在离 a 较近的地方. pdf(b-a)=exp(-(b-a))
    melonux
        12
    melonux  
    OP
       2019-04-23 16:35:50 +08:00
    @geelaw 很想知道这个怎么动态规划
    lance6716
        13
    lance6716  
       2019-04-23 17:18:34 +08:00
    @melonux 指数分布是无记忆的(不知道在这个离散程度和规模下能不能这么概括),给定搜索的区间[low, high],只跟区间长度有关

    均匀分布的时候二分中点。不均匀就二分“累计概率达到一半”的那个点
    melonux
        14
    melonux  
    OP
       2019-04-23 17:35:16 +08:00
    @lance6716 嗯. 您说的对. 给定范围和给定这个分布本身冲突了. 我的本意是均匀分布即可. 但看到那个可以动态规划的方法, 就很好奇. 想看到一个不平凡的解, 所以给了一个不均匀的分布.
    geelaw
        15
    geelaw  
       2019-04-23 22:31:31 +08:00 via iPhone   ❤️ 1
    @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。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1811 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 16:32 · PVG 00:32 · LAX 08:32 · JFK 11:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.