美文网首页程序员
稳定脱单问题(延迟接受算法)

稳定脱单问题(延迟接受算法)

作者: 赫尔特 | 来源:发表于2019-12-06 13:29 被阅读0次

    Discrete mathematics and its applications 7th 第三章笔记

    文章目录

    \color{orange}{1.停机问题(The Halting Problem)}
    \color{red}{2.三分法}
    \color{green}{3.延迟接受算法}
    \color{pink}{4.判断logn!log n!logn!是否是Θ(nlogn)\Theta (nlogn)Θ(nlogn)的}
    \color{purple}{5.矩阵连乘的最少乘法次数}
    \color{blue}{6.给运行时间排序}

    算法及其复杂度分析

    说明:笔记并不完整,只记录了书本的部分。

    1.停机问题(The Halting Problem)

    停机问题是 “证明存在不可解问题” 的一个例子

    问题描述:

    是否存在这样一个过程,该过程能以一个计算机程序以及该程序的一个输入作为输入,并判断在给定输入运行时是否最终停止。

    原书证明(反证法):

    1
    最后与H所给的结果相违背是指和最开始H的定义相违背。

    相似的题:

    1.证明 判断一个程序在给定一个输入时总会输出数字“1”这个问题是不可解的。

    证明:假设我有一个程序,它能够判断在给定一个输入时,是否输出数字“1”,那么我们就有办法解决停机问题(输入为程序P'及P'的输入I)。可以构造一个新的程序P,P和P'的原理一样,唯一不同的是,当P终止时,P'也会终止,但同时会输出数字“1”,然后我们把P'和I作为P的输入,这样就可以说明P在输入为P'和I的情况下判断是否终止,这与停机问题不可解相矛盾。

    2.证明:“给定两个程序以及它们的输入,并且已知其中恰有一个会终止,判断哪一个程序会终止”这个问题是可解的。

    证明:运行这两个程序,输入为上面的输入,看哪个程序会终止。进而判断这个程序会终止。(因为题目说恰有一个会终止)

    3.证明判定一个特定程序给定特定输入时是否会停机的问题是可解的。

    证明:因为是特定的程序和输入,运行判断是否终止,是就说明会停机,否则就说明不会停机。(因为这里指明了是特定输入,哪怕运行了10亿年才停止,这也是属于会停机,所以在输入确定的情况下,答案要么是yes,要么是no,且答案一旦确定就不会改变。但是停机问题不能这么做,因为停机问题没有指明特定输入,也就是说停机问题里面可能停机也可能不停,不能靠运行来判断)

    2.三分法

    三分搜索算法:和二分搜索类似,在待搜索的序列中,找到两个三分点,进行比较,从而把区间长度变成原来的1/3(如果原来的序列是单调的话)

    参考代码:

    exp=1e-10
    def ternarySearch(left,right,key,array):
        while right>=left:
            # //得到的相除结果是整数
            mid1=left+(right-left)//3
            mid2=right-(right-left)//3
            if abs(key-array[mid1])<exp:
                return mid1
            if abs(key-array[mid2])<exp:
                return mid2
            if key<array[mid1]:
                right=mid1-1
            elif key>array[mid2]:
                left=mid2+1
            else:
                left=mid1+1
                right=mid2-1
        # 如果没有找到,返回-1
        return -1
    
    if __name__=='__main__':
        nums=[1,2,3,4,5,6,7,8,9,10]
        l=0
        r=9
        key=6
        index=ternarySearch(l,r,key,nums)
        print('Index of',key,'is',index)
    
        key=66
        index=ternarySearch(l,r,key,nums)
        print('Index of',key,'is',index)
    

    三分法的平均(最坏)时间复杂度是:O(log_3n)
    这和二分法的O(log_2n)比较起来并没有快,比较最坏情况:
    二分算法的开销(比较次数)满足:T(n)=T(n/2)+2,T(1)=1
    故需要2log_2n+1次比较
    三分法:T(n)=T(n/3)+4,T(1)=1
    故需要4log_3n+1次比较,而4log_3n=\frac{4log_2n}{log_23}\ge2log_2n

    不过三分法可以做二分法处理不了的问题,因为二分法只能处理单调的数据,三分法除了处理单调数据外,还可以处理单峰(凸)数据(也就是有峰值,且峰值两边都单调的数据)(对具有凹特点的数据当然也可以用三分法)

    处理方法大致为:按上述步骤找到mid1,mid2,然后比较mid1和mid2的大小,较大的那个说明更靠近峰值,然后舍去较小的mid对应的1/3区间

    例子:

    比如:给出圆锥体的表面积,在误差范围内求解圆锥体的最大体积
    http://www.voidcn.com/article/p-rneuvsrj-s.html

    3.延迟接受算法

    原书描述:

    在这里插入图片描述

    看不懂上面的描述没有问题,可以看下面的伪代码(网上的参考答案)

    while里的第一个for循环,每个男的向自己心仪的妹子提婚,条件是在妹子曾经没有拒绝过他的情况下,妹子在男性心目中排名应当最靠前
    while里的第二个for循环,轮到每个妹子从收到的提婚申请中挑选自己心目中排名最高的,然后把其他所有的对自己提婚男性加入黑名单(哈哈哈),当然这次挑选只是暂时的,因为只要while还没结束,就有可能有更心仪的男性取代现在被选中的男性

    Here we assume that the men
    are the suitors and the women the suitees.
    
    procedure stable(M1, M2,...,Ms, W1, W2,...,Ws:
    preference lists)
    for i := 1 to s
        mark man i as rejected
    for i := 1 to s
        set man i’s rejection list to be empty
    for j := 1 to s
        set woman j ’s proposal list to be empty
    
    while rejected men remain
    for i := 1 to s
        if man i is marked rejected then add i to the
        proposal list for the woman j who ranks highest
        on his preference list but does not appear on his
        rejection list, and mark i as not rejected
    for j := 1 to s
        if woman j ’s proposal list is nonempty then
        remove from j ’s proposal list all men i
        except the man i0 who ranks highest on her
        preference list, and for each such man i mark
        him as rejected and add j to his rejection list
    
    for j := 1 to s
        match j with the one man on j ’s proposal list
    {This matching is stable.}
    
    

    一些证明:

    1.证明延迟接受算法可终止:

    可以证明迭代的次数不超过n^2-2n+2,而且从上面可以看出终止的时候一定是一一匹配的
    证明参考链接里面的那个数学归纳法(偷一波懒):
    最坏情况的时间复杂度

    2.证明延迟匹配算法总可以产生一个稳定的匹配:

    假设算法不能产生一个稳定的匹配,也就是说,存在一个男的A,他相比妹子B',更喜欢妹子B,但是他却和B'结婚了,同时妹子B明明更喜欢A,却和A'结婚了,这就导致了不稳定,因为它把两情相悦的给拆开了。下面证明上述现象会产生矛盾:
    根据算法描述,A一定会先向B进行提婚而不是B'(因为B优先级更高),但是上面假设A和B没有结婚,说明A被B拒绝了,根据算法描述,B之所以拒绝A,一定是遇到自己认为更好的,但是A'并不比A好,故矛盾,所以延迟匹配算法总可以产生一个稳定的匹配。

    4.判断log n!是否是\Theta (nlogn)

    1. 证明: f(x)\Theta(g(x))当且仅当f(x)O(g(x))中,且g(x)O(f(x))中。

    证明:
    充分性,如果f(x)\Theta(g(x)),那么存在实数C_1,C_2,
    x>k时,C_1|g(x)|\le|f(x)|\le C_2|g(x)|,也就是说,
    |g(x)|\le \frac1C_1|f(x)| , |g(x)|\ge \frac1C_2|f(x)|
    所以f(x)O(g(x))中,且g(x)O(f(x))中。

    必要性,如果f(x)O(g(x))中,且g(x)O(f(x))中。,那么|g(x)|\le \frac1C_1|f(x)|x>k_1 ; |g(x)|\ge \frac1C_2|f(x)|x>k_2,取k=max\{k_1,k_2\},则有当x>k时,C_1|g(x)|\le|f(x)|\le C_2|g(x)|
    所以f(x)\Theta(g(x))

    1. 证明:log n!O(nlogn)中

    显然有n!<n^n

    1. 证明:nlognO(log n!)中

    考虑(n!)^2=(n\cdot1)\cdot((n-1)\cdot2)\cdot((n-2)\cdot3)\cdot\cdot\cdot(1\cdot n)
    因为0\le i\le n-1时,(n-i)\cdot(i+1)-n=i\cdot(n-i-1)\ge0
    (n!)^2\ge n^n

    1. 判断log n!是否是\Theta (nlogn)

    由前面3个命题得出 log n!\Theta (nlogn)

    5.矩阵连乘的最少乘法次数

    参考链接

    2

    6.给运行时间排序

    3

    (源自 标题教材里面中文版P201)

    (里面的lognlog_2n就行des~)
    第一题排序:
    (logn)^2,2^{\sqrt{log_2n}},n(logn)^{1001},n^{1.0001},1.0001^n,n^n
    比较(logn)^2,2^{\sqrt{log_2n}},把根号整体换元成t即可看出
    比较n(logn)^{1001},n^{1.0001}

    3

    第二题排序:


    4

    相关文章

      网友评论

        本文标题:稳定脱单问题(延迟接受算法)

        本文链接:https://www.haomeiwen.com/subject/autegctx.html