精华内容
下载资源
问答
  • 图的几种表示方法

    千次阅读 2020-05-17 15:06:10
    图的几种表示方法 网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的 算法,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说, 算法的好坏与网络的具体表示方法...

    图的几种表示方法

    网络优化研究的是网络上的各种优化模型与算法。为了在计算机上实现网络优化的 算法,首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说, 算法的好坏与网络的具体表示方法,以及中间结果的操作方案是有关系的。这里我们介 绍计算机上用来描述图与网络的 5 种常用表示方法:邻接矩阵表示法、关联矩阵表示法、 弧表表示法、邻接表表示法和星形表示法。
    在下面数据结构的讨论中,我们首先假设 G = (V, A) 是一个简单有向图,|V |= n,| A |= m ,并假设V 中的顶点用自然数1,2,....,n 表示或编号, A 中的弧用自然数1,2,...,m 表示或编号。对于有多重边或无向网络的情 况,我们只是在讨论完简单有向图的表示方法之后,给出一些说明。
    在这里插入图片描述

    (i)邻接矩阵表示法

    邻接矩阵表示法是将图以邻接矩阵(adjacency matrix)的形式存储在计算机中。图 **G = (V, A)**的邻接矩阵是如下定义的: C 是一个 n × n0 −1矩阵,即
    在这里插入图片描述也就是说,如果两节点之间有一条弧,则邻接矩阵中对应的元素为 1 ;否则为 0 。 可以看出,这种表示法非常简单、直接。但是,在邻接矩阵的所有 n^2 个元素中,只有 m 个为非零元。如果网络比较稀疏,这种表示法浪费大量的存储空间,从而增加了在网络 中查找弧的时间。

    对于图 2 所示的有向图,可以用邻接矩阵表示为
    在这里插入图片描述
    同样,对于网络中的权,也可以用类似邻接矩阵的n × n 矩阵表示。只是此时一条 弧所对应的元素不再是 1,而是相应的权而已。如果网络中每条弧赋有多种权,则可以 用多个矩阵表示这些权。

    (ii)关联矩阵表示法

    在关联矩阵中,每行对应于图的一个节点,每列对应于图的一条弧。如 果一个节点是一条弧的起点,则关联矩阵中对应的元素为 1;如果一个节点是一条弧的 终点,则关联矩阵中对应的元素为 −1;如果一个节点与一条弧不关联,则关联矩阵中 对应的元素为 0
    对于简单图,关联矩阵每列只含有两个非零元(一个 +1,一个 −1)。 可以看出,这种表示法也非常简单、直接。但是,在关联矩阵的所有nm 个元素中,只 有2m 个为非零元。如果网络比较稀疏,这种表示法也会浪费大量的存储空间。但由于 关联矩阵有许多特别重要的理论性质,因此它在网络优化中是非常重要的概念。
    对于图2所示的图,如果关联矩阵中每列对应弧的顺序为(1,2),(1,3),(2,4), (3,2),(4,3),(4,5),(5,3)和(5,4),则关联矩阵表示为

    ————————在这里插入图片描述
    同样,对于网络中的权,也可以通过对关联矩阵的扩展来表示。例如,如果网络中 每条弧有一个权,我们可以把关联矩阵增加一行,把每一条弧所对应的权存储在增加的 行中。如果网络中每条弧赋有多个权,我们可以把关联矩阵增加相应的行数,把每一条 弧所对应的权存储在增加的行中。

    弧表表示法

    弧表表示法将图以弧表(arc list)的形式存储在计算机中。所谓图的弧表,也就是 图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点,共需2m 个存 储单元,因此当网络比较稀疏时比较方便。此外,对于网络图中每条弧上的权,也要对 应地用额外的存储单元表示。

    图2所示的图,假设弧**(1,2),(1,3),(2,4),(3,2), (4,3),(4,5),(5,3)和(5,4)**上的权分别为 8,9,6,4,0,3,67,则弧表表示如表 1 所示。
    在这里插入图片描述
    为了便于检索,一般按照起点、终点的字典序顺序存储弧表,如上面的弧表就是按 照这样的顺序存储的。

    邻接表表示法

    邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的 邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它的邻接表就是它的所 有出弧。邻接表表示法就是对图的每个节点,用一个单向链表列出从该节点出发的所有 弧,链表中每个单元对应于一条出弧。为了记录弧上的权,链表中每个单元除列出弧的 另一个端点外,还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数 组表示。
    在这里插入图片描述这是一个 5 维指针数组,每一维(上面表示法中的每一行)对应于一个节点的邻接 表,如第 1 行对应于第 1 个节点的邻接表(即第 1 个节点的所有出弧)。**每个指针单元 的第 1 个数据域表示弧的另一个端点(弧的头),后面的数据域表示对应弧上的权。**如 第 1 行中的“2”表示弧的另一个端点为 2(即弧为(1,2)),“8”表示对应弧(1,2)上的 权为 8;“3”表示弧的另一个端点为 3(即弧为(1,3)),“9”表示对应弧(1,3)上的权 为 9。又如,第 5 行说明节点 5 出发的弧有(5,3)、(5,4),他们对应的权分别为 6 和 7。

    对于有向图G = (V, A),一般用 A(i) 表示节点i 的邻接表,即节点i 的所有出弧构 成的集合或链表(实际上只需要列出弧的另一个端点,即弧的头)。例如上面例子, **A(1) = {2,3}, A(5) = {3,4}**等。

    星形表示法

    星形(star)表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点, 它也是记录从该节点出发的所有弧,但它不是采用单向链表而是采用一个单一的数组表 示。也就是说,在该数组中首先存放从节点 1 出发的所有弧,然后接着存放从节点 2 出发的所有孤,依此类推,最后存放从节点n 出发的所有孤。对每条弧,要依次存放其 起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号, 只是从同一节点出发的弧的顺序可以任意排列。此外,为了能够快速检索从每个节点出 发的所有弧,我们一般还用一个数组记录每个节点出发的弧的起始地址(即弧的编号)。 在这种表示法中,可以快速检索从每个节点出发的所有弧,这种星形表示法称为前向星 形(forward star)表示法。

    例如,在例 7 所示的图中,仍然假设弧(1,2),(l,3),(2,4),(3,2),(4,3),(4,5), (5,3)和(5,4)上的权分别为 8,9,6,4,0,3,6 和 7。此时该网络图可以用前向 星形表示法表示为表 2 和表 3 。
    在这里插入图片描述在数组 point 中,其元素个数比图的节点数多 1(即n +1),且一定有 **point(1) = 1, point(n +1) = m +1。**对于节点i ,其对应的出弧存放在弧信息数组的位置区间为

    [ point(i), point(i +1) −1], //表示记录弧信息的表中**[point[i],point[i+1]-1]都是以i**为出弧

    如果 point(i) = point(i +1) ,则节点i 没有出弧。这种表示法与弧表表示法也非常相似,“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中, 弧被编号后有序存放,并增加一个数组( point )记录每个节点出发的弧的起始编号。
    前向星形表示法有利于快速检索每个节点的所有出弧,但不能快速检索每个节点的 所有入弧。为了能够快速检索每个节点的所有入孤,可以采用反向星形(reverse star) 表示法:首先存放进入节点 1 的所有孤,然后接着存放进入节点 2 的所有弧,依此类推, 最后存放进入节点n 的所有孤。对每条弧,仍然依次存放其起点、终点、权的数值等有 关信息。同样,为了能够快速检索从每个节点的所有入弧,我们一般还用一个数组记录 每个节点的入孤的起始地址(即弧的编号)。

    图2所示的图,可以用反向星形表 示法表示为表 4 和表 5。
    在这里插入图片描述

    如果既希望快速检索每个节点的所有出弧,也希望快速检索每个节点的所有入弧, 则可以综合采用前向和反向星形表示法。当然,将孤信息存放两次是没有必要的,可以 只用一个数组(trace)记录一条弧在两种表示法中的对应关系即可。

    例如,可以在采用前向星形表示法的基础上,加上上面介绍的 rpoint 数组和如下的trace 数组即可。这相 当于一种紧凑的双向星形表示法,如表 6 所示。
    在这里插入图片描述
    对于网络图的表示法,我们作如下说明

    星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少,并且对那些不提供指针类型的语言(如 FORTRAN 语言 等)也容易实现。邻接表表示法对那些提供指针类型的语言(如 C 语言等)是方便的, 且增加或删除一条弧所需的计算工作量很少,而这一操作在星形表示法中所需的计算工作量较大(需要花费O(m) 的计算时间)。有关“计算时间”的观念【时间复杂度】是网络优化中需要考虑的一个关键因素。

    ② 当网络不是简单图,而是具有平行弧(即多重弧)时,**显然此时邻接矩阵表示法是不能采用的。**其他方法则可以很方便地推广到可以处理平行弧的情形。

    ③ 上述方法可以很方便地推广到可以处理无向图的情形,但由于无向图中边没有方向,因此可能需要做一些自然的修改。

    例如,可以在计算机中只存储邻接矩阵的一半 信息(如上三角部分),因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素 0+1,而不含有 −1,因为此时不区分边的起点和终点。又如,在邻接表和星形表示 法中,每条边会被存储两次,而且反向星形表示显然是没有必要的,等等。

    ————————
    版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/qq_29831163/article/details/89785015

    展开全文
  • 通过这一直观形式,能够让普通大众快速接受企业所想表达的深层含义,同时也便于对数据进行深度的挖掘和分析结果的表达呈现,空间表达较图表、文字等其它表达方式除了直观,易于理解外,也能够将海量数据的效果进行...

    一、前言

    越来越多的出行企业选择空间大数据可视化表达来进行海量数据的分析和展示,如mobike、滴滴、uber。通过这一直观形式,能够让普通大众快速接受企业所想表达的深层含义,同时也便于对数据进行深度的挖掘和分析结果的表达呈现,空间表达较图表、文字等其它表达方式除了直观,易于理解外,也能够将海量数据的效果进行视觉感官上的刺激,同时呈现出一种不规则的美。

    二、空间大数据可视化表达方式

    空间的可视化表达形式有多重多样,有相对量化的,有抽象的,有离散的,也有连续的,不同的表达形式所想表达的含义也不尽相同,主要的表达形式有散点、热力、气泡、分组散点、立体柱状、立体热力、道路密度分级渲染、道路热力渲染、静态线、飞线、动态网格密度、蜂窝网格密度等。这里就以mobike 2017年武汉共享单车出行报告中所涉及的空间可视化,对各个类别的表达方式进行一个阐述。

    三、海量散点图

    散点图是一种离散点在空间中的表达形式,通过海量点的全量展示,能够让我们体会到每一个动作(开关锁、上下车)在特定位置的特殊含义。
    这里写图片描述

    四、分组散点图

    分组散点是一类特殊的散点形式,通过类别进行不同颜色的区分,表达不同的含义,能够使我们获取更加明确的信息,如共享单车开锁点、关锁点设置为不同颜色的渲染,可以观察不同的时间段,如上下班高峰期,两个点的分布是有完全不同的规律的。
    这里写图片描述

    五、气泡图

    气泡图也是散点的一种特殊形式,他是通过不同的权重表达散点的大小,同时也可以关联不同的颜色,形成一个个不同大小,不同颜色的点,相比普通散点和分组散点,它所表达的数据维度更多,展现效果也更华丽多彩。
    这里写图片描述

    六、热力图

    热力图是一种非常常见的空间表达方式,主要是通过离散的数据分布(可能还带有权重),在不同的层级在同一屏幕区域的聚合表达,如离散的手机GPS位置请求,我们可以把每次请求当做一个独立个体,通过热力的展示可以得到某一些区域的人员如果密度大,这时候在热力图上展示这块区域就比较热,密度比较大,可以用比较偏热的颜色表达这种信息,如红色、紫色等。
    这里写图片描述

    七、立体热力

    立体热力其实和热力的概念是一致的,不过不同技术上的表达方式不一致,普通热力主要是在二维地图的表达,立体热力主要是支持webgl的展示平台上的一种展示形式,如mapbox、或者其它三维可视化平台。
    这里写图片描述

    八、网格图

    网格图是一种经过空间统计分析后的表达形式,通过定义规则的网格,如矩形网格、蜂窝网格,然后统计每个网格内的散点数量,最后根据网格的分级标准,如不同的值区间,进行不同颜色的分段表达,其实类似于热力,不过网格在视觉上规则感更强。
    这里写图片描述

    九、网格立体柱状图

    网格立体柱状图是网格图的>2.5维的展示,除了平面网格颜色的不同外,还能够通过柱子的高度直观的体现出网格值的大小,在视觉上冲击更强。
    这里写图片描述

    十、道路密度

    道路密度是将离散的信息点,如骑行轨迹,映射到道路上,然后对道路点进行聚合分析,得到每条道路甚至每条道路的每个路段不同的权重,然后根据 权重进行不同颜色、线宽的表达,形成直观的道路密度图。一种根据骑行轨迹计算道路密度的方法,可以参考我的这篇博客(GeoHash在空间道路密度计算中的应用-以mobike骑行轨迹为例)。
    这里写图片描述
    这里写图片描述

    十一、总结

    还有几种表达空间方式如:飞线、动态网格、动态轨迹等等在这个报告中并没有体现,在我的下一篇博客中,我会基于滴滴的出行分析报告做进一步的描述,这篇报告中所有的截图都是基于《mobike 2017年武汉共享单车出行报告》,大家可以下载这篇报告进行进一步的阅读。

    展开全文
  • 区间调度问题详解

    千次阅读 多人点赞 2017-12-25 22:25:59
    区间调度是一类难度比较大,但同时应用比较广的问题,经常会在面试中以各种形式出现。本文将会介绍区间调度的各种变形,希望能使大家在面临区间调度问题时得心应手,并可以在实际工作中巧妙应用。1. 相关定义在数学...

    今天给大家介绍一下区间调度问题。区间调度是一类难度比较大,但同时应用比较广的问题,经常会在面试中以各种形式出现。本文将会介绍区间调度的各种变形,希望能使大家在面临区间调度问题时得心应手,并可以在实际工作中巧妙应用。

    1. 相关定义

    在数学里,区间通常是指这样的一类实数集合:如果x和y是两个在集合里的数,那么,任何x和y之间的数也属于该集合。区间有开闭之分,例如(1,2)和[1,2]的表示范围不同,后者包含整数1和2。
    在程序世界,区间的概念和数学里没有区别,但是往往有具体的含义,例如时间区间,工资区间或者音乐中音符的开始结束区间等,图一给出了一个时间区间的例子。区间有了具体的含义之后,开闭的概念就显得非常重要,例如时间区间[8:30,9:30]和[9:30,10:30]两个区间是有重叠的,但是[8:30,9:30)和[9:30,10:30)没有重叠。在不同的问题中,区间的开闭往往不同,有时是闭区间,有时是半开半闭区间。时间区间往往是闭区间,但是音符中的开始结束区间则是半开半闭区间,所以在重叠的定义上大家需要具体问题具体分析。稍后你会发现,开闭的区别其实只是差一个等号而已。
    这里写图片描述

    图1 时间区间示例

    假设区间是闭合的,并定义为[start,end]。我们首先看一下区间重叠的定义。给定两个区间[s1,e1]和[s2,e2],它们重叠的可能性有四种:
    这里写图片描述
    可以看出,如果直接考虑区间重叠,判断条件比较复杂,我们从相反的角度考虑,考虑区间不重叠的情况。区间不重叠时的判断条件为:
    这里写图片描述
    也即: (e1<s2||s1>e2) ,所以区间重叠的判断条件为:
    这里写图片描述
    经过化简之后,区间重叠的判断条件只有两个,也很好理解,不再赘述。如果区间是半开半闭的,则只需要将判断条件中的等号去掉。
    现在考虑这样一个问题,如何判断一个区间是否和其他的区间重叠。最坏情况下,我们可能需要和剩下的所有n-1个区间比较一次才能知道结果,每和一个区间比较都需要两次判断。所以完成n个区间相互之间比较的复杂度为 O(n2) ,常系数为2。为了加快比较的速度,通常会先对区间进行一个排序,可以按照开始时间或者结束时间进行排序,需要根据实际情况选择。排序之后每个区间再和其他的n-1个区间进行比较。为什么要排序,排序之后的比较复杂度不还是 O(n2) 吗?原因在于,区间经过排序之后,其实已经有了一个先后顺序,后续再进行重叠判断的时候只需要比较一次即可,这时的复杂度其实变为 O(nlogn+n2) ,常系数为1,比不排序要快一些。例如,假设所有的区间都按照结束时间进行排序,就会有 sititi+1 ,这是两个重叠判断条件中的后一个,所以我们只需要再判断前一个即可。在涉及区间重叠的问题上,一般都会先进行排序。

    2. 区间调度问题分类

    上面介绍了相关基本概念,这节介绍区间调度问题的两个维度,所有的区间调度问题都是从这两个维度上展开的。给定N个区间,如果我们在x坐标轴上将它们都画出,则可能由于重叠的原因而显示很乱。为了避免重叠,我们需要将区间在y轴上进行扩展,将重叠的区间画在纵坐标不同的行上,如图二。区间在两个维度上的扩展也即在横轴时间和纵轴行数上的扩展。几乎所有的区间调度问题都是从这两个维度上展开的。
    这里写图片描述

    图2 区间的两个维度

    x轴上的扩展,可能会让我们计算一行中最多可以不重叠地放置多少个区间,或者将区间的时间累加最大可以到多少,或者用最少的区间覆盖一个给定的大区间;y轴上的扩展,可能会让我们计算为了避免区间重叠,最少需要多少行;还可以将y轴的行数固定,然后考虑为了完成n个工作最短需要多少时间,也即机器调度问题。更复杂一些,有时区间还会变成带权的,例如酒店竞标的最大收益等等。区间调度问题的种类非常多,后面会一一展开详细介绍。

    3. x轴上的区间调度

    x轴上的区间调度主要关注一行中的区间情况,比如最多可以放入多少不重叠的区间,或者最少可以用多少区间覆盖一个大区间等等。该类区间调度问题应用很广,经常会以各种形式出现在笔试面试题中。

    3.1 最多区间调度

    有n项工作,每项工作分别在 si 时间开始,在 ti 时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(闭区间)。你的目标是参与尽可能多的工作,那么最多能参与多少项工作?其中 1N100000 并且 1siti109 。(from《挑战程序设计竞赛 P40》)
    这里写图片描述

    图3 最多区间调度

    这个区间问题就是大家熟知的区间调度问题或者叫最大区间调度问题。在此我们进行细分,将该问题命名为最多区间调度问题,因为该问题的目标是求不重叠的最多区间个数,而不是最大的区间长度和。
    这个问题可以算是最简单的区间调度问题了,可以通过贪心算法求解,贪心策略是:在可选的工作中,每次都选取结束时间最早的工作。其他贪心策略都不是最优的。
    下面是一个简单的实现:

    const int MAX_N=100000;
    //输入
    int N,S[MAX_N],T[MAX_N];
    
    //用于对工作排序的pair数组
    pair<int,int> itv[MAX_N];
    
    void solve()
    {
        //对pair进行的是字典序比较,为了让结束时间早的工作排在前面,把T存入first,//把S存入second
        for(int i=0;i<N;i++)
        {
            itv[i].first=T[i];
            itv[i].second=S[i];
        }
    
        sort(itv,itv+N);
    
        //t是最后所选工作的结束时间
        int ans=0,t=0;
        for(int i=0;i<N;i++)
        {
            if(t<itv[i].second)//判断区间是否重叠
            {
                ans++;
                t=itv[i].first;
            }
        }
    
        printf(“%d\n”,ans);
    }

    时间复杂度:排序 O(nlogn) +扫描 O(n)=O(nlogn) 。该问题已给出最优解,也即用贪心法可以解决。但是思考的思路如何得来呢?我们一步步分析,看看能不能最终得到和贪心法一样的结果。
    最优化问题都可以通过某种搜索获得最优解,最多区间调度问题也不例外。该问题无非就是选择几个不重叠的区间而已,看看最多能选择多少个,其解空间为一棵二叉子集树,某个区间选或者不选构成了两个分支,如图四所示。我们的目标就是遍历这棵子集树,然后看从根节点到叶节点的不重叠区间的最大个数为多少。可以看出,该问题的解就是n位二进制的某个0/1组合。子集树共有2n种组合,每种组合都需要判断是否存在重叠区间,如果不重叠则获得1的个数。
    这里写图片描述

    图4 区间调度的子集树

    假设我们不对区间进行排序,则每种组合判断是否有重叠区间的复杂度为 O(n2) ,从而整个算法复杂度为 O(2nn2) 。复杂度相当高!进行各种剪枝也无济于事!下面我们开始对算法进行优化。
    让我们感到奇怪的是,只是判断n个区间是否存在重叠最坏居然也需要 O(n2) 的复杂度。这是因为在区间无序的情况下,每个区间都要顺次和后面的所有区间进行比较,没有合理利用区间的两个时间点。我们考虑对区间进行一下排序会有什么不同。假设我们按照开始时间进行排序,排序之后有 xi1xixi+1 ,然后从第一个区间开始判断。第一个区间只需要和第二个区间进行判断即可。如果重叠,则这n个区间存在重叠,后面无需再进行判断;如果不重叠,我们只需要再将第二个和第三个进行同样的判断即可。所以按照开始时间进行排序之后,判断n个区间是否存在重叠的复杂度将为 O(n) ,所以整个算法复杂度降为 O(n2n) 。按照结束时间进行排序也会有同样的结论。
    虽然排序可以降低复杂度,但是遍历子集树的代价还是太大。我们换个角度考虑问题,看能不能避免遍历子集树。突破点在哪呢?我们不妨从第一个区间是否属于最优解开始。首先假设区间按照开始时间排序,并且已经求出最优解对应的所有区间。如果最优解中开始时间最小的区间 I1 不是所有区间中开始时间最小的区间 I1 ,我们看看能否进行替换。 I1 I1 肯定是重叠的,否则就可以将 I1 添加到最优解中获得更好的最优解。能否将 I1 替换成 I1 呢? I1 I1 满足 s1s1 ,但是结束时间不确定,这就可能出现 e1e1 的情况,从而也会出现 e1eii>1 的情况,从而替换可能会引入重叠,最优解变成非最优解。所以在按照开始时间排序的情况下,第一个区间不一定属于最优解。
    我们再考虑一下按照结束时间排序的情况,也已经求出最优解对应的所有区间。如果最优解中结束时间最小的区间 I1 不是所有区间中结束时间最小的区间 I1 ,我们看看能否进行替换。 I1 I1 肯定是重叠的,否则就可以将 I1 添加到最优解中获得更好的最优解。能否将 I1 替换成 I1 呢? I1 I1 满足 e1e1 I1 I2 满足 e1s2 (两个区间不重叠),所以有 e1s2 ,从而 I1 I2 不重叠。所以我们可以用 I1 来替换 I1 。这就得出一个结论:在按照结束时间排序的情况下,第一个区间必定属于最优解。按照这个思路继续推导剩下的区间我们就会发现:每次选结束时间最早的区间就可以获得最优解。这就和我们一开始给出的结论一致。
    经过上面的分析,我们就明白为啥选择结束时间最早的工作就可以获得最优解。虽然我们并没有遍历子集树,但是它为我们思考和优化问题给出了一个很好的模型,希望大家能好好掌握这种构造问题解空间的方法。
    下面我们再换个角度考虑上面的问题。很多最优化深搜问题都可以巧妙地转化成动态规划问题,可以转化的根本原因在于存在重复子问题,我们看图四就会发现最多区间调度问题也存在重复子问题,所以可以利用动态规划来解决。假设区间已经排序,可以尝试这样设计递归式:前i个区间的最多不重叠区间个数为dp[i]。dp[i]等于啥呢?我们需要根据第i个区间是否选择这两种情况来考虑。如果我们选择第i个区间,它可能和前面的区间重叠,我们需要找到不重叠的位置k,然后计算最多不重叠区间个数dp[k]+1(如果区间按照开始时间排序,则前i+1个区间没有明确的分界线,我们必须按照结束时间排序);如果我们不选择第i个区间,我们需要从前i-1个结果中选择一个最大的dp[j];最后选择dp[k]+1和dp[j]中较大的。伪代码如下:

    void solve()
    {
        //1. 对所有的区间进行排序
        sort_all_intervals();
    
        //2. 按照动态规划求最优解
        dp[0]=1;
        for (int i = 1; i < intervals.size(); i++) 
           {
            //1. 选择第i个区间
            k=find_nonoverlap_pos();
            if(k>=0) dp[i]=dp[k]+1;
            //2. 不选择第i个区间
            dp[i]=max{dp[i],dp[j]};
        }
    }

    选择或者不选择第i个区间都需要去查找其他的区间,顺序查找的复杂度为 O(n) ,总共有n个区间,每个区间都需要查找,所以动态规划部分最初的算法复杂度为 O(n2) ,已经从指数级降到多项式级,但是经过后面的优化还可以降到 O(n) ,我们一步步来优化。
    可以看出dp[i]是非递减的,这可以通过数学归纳法证明。也即当我们已经求得前i个区间的最多不重叠区间个数之后,再求第i+1个区间时,我们完全可以不选择第i+1个区间,从而使得前i+1个区间的结果和前i个区间的结果相同;或者我们选择第i+1个区间,在不重叠的情况下有可能获得更优的结果。dp[i]是非递减的对我们有什么意义呢?首先,如果我们在计算dp[i]时不选择第i个区间,则我们就无需遍历前i-1个区间,直接选择dp[i-1]即可,因为它是前i-1个结果中最大的(虽然不一定是唯一的),此时伪代码中的dp[j]就变成了dp[i-1]。其次,在寻找和第i个区间不重叠的区间时,我们可以避免顺序遍历。如果我们将dp[i]的值列出来,肯定是这样的:

    1,1,…,1,2,2,…,2,3,3,…,3,4……

    即dp[i]的值从1开始,顺次递增,每一个值的个数不固定。dp[0]肯定等于1,后面几个区间如果和第0个区间重叠,则的dp值也为1;当出现一个区间不和第0个区间重叠时,其dp值变为2,依次类推。由此我们可以得到一个快速获得不重叠位置的方法:重新开辟一个新的数组,用来保存每一个不同dp值的最开始位置,例如pos[1]=0,pos[2]=3,…。这样我们就可以利用 O(1) 的时间实现find_nonoverlap_pos函数了,然后整个动态规划算法的复杂度就降为 O(n) 了。
    其实从dp的值我们已经就可以发现一些端倪了:dp值发生变化的位置恰是出现不重叠的位置!再仔细思考一下就会出现一开始提到的贪心算法了。所以可以说,贪心算法是动态规划算法在某些问题中的一个特例。该问题的特殊性在于只考虑区间的个数,也即每次都是加1的操作,后面会看到,如果变成考虑区间的长度,则贪心算法不再适用。

    3.2 最大区间调度

    该问题和上面最多区间调度问题的区别是不考虑区间个数,而是将区间的长度和作为一个指标,然后求长度和的最大值。我们将该问题命名为最大区间调度问题。
    WAP某年的笔试题就考察了该问题(下载)。看这样一个例子:现在有n个工作要完成,每项工作分别在 时间开始,在 时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(闭区间)。求你参与的所有工作最大需要耗费多少时间。
    这里写图片描述

    图5 最大区间调度

    该问题和最多区间调度很相似,一个考虑区间个数的最大值,一个考虑区间长度的最大值,但是该问题的难度要比最多区间调度大些,因为它必须要用动态规划来高效解决。在最多区间调度问题中,我们用动态规划的方法给大家解释了贪心算法可以解决问题的缘由,而最大区间调度问题则是直接利用上面提到的动态规划算法:首先按照结束时间排序区间,然后按照第i个区间选择与否进行动态规划。我们先给出WAP笔试题的核心代码:

    public int getMaxWorkingTime(List<Interval> intervals) {
        /*
         * 1 check the parameter validity
         */
    
        /*
         * 2 sort the jobs(intervals) based on the end time
         */
        Collections.sort(intervals, new EndTimeComparator());
    
        /*
         * 3 calculate dp[i] using dp
         */
        int[] dp = new int[intervals.size()];
        dp[0] = intervals.get(0).getIntervalMinute();
    
        for (int i = 1; i < intervals.size(); i++) {
            int max;
    
            //select the ith interval
            int nonOverlap = below_lower_bound(intervals, 
                    intervals.get(i).getBeginMinuteUnit());
            if (nonOverlap >= 0)
                max = dp[nonOverlap] + intervals.get(i).getIntervalMinute();
            else
                max = intervals.get(i).getIntervalMinute();
    
            //do not select the ith interval
            dp[i] = Math.max(max, dp[i-1]);
        }
    
        return dp[intervals.size() - 1];
    }
    
    public int below_lower_bound(List<Interval> intervals, int startTime) {
        int lb = -1, ub = intervals.size();
    
        while (ub - lb > 1) {
            int mid = (ub + lb) >> 1;
            if (intervals.get(mid).getEndMinuteUnit() >= startTime)
                ub = mid;
            else
                lb = mid;
        }
        return lb;
    }

    代码和最多区间调度最大的不同在选择第i个区间时。在这里用了一个二分查找来搜索不重叠的位置,然后判断该位置是否存在。如果不重叠位置存在,则算出当前的最大区间长度和;如果不存在,表明第i个区间和前面的所有区间均重叠,但由于我们还要选择第i个区间,所以暂时的最大区间和也即第i个区间自身的长度。在最多区间调度中,如果该位置不存在,我们直接将dp[i]赋值成dp[i-1],在这里我们却要将第i个区间本身的长度作为结果。从图五我们可以清楚地看到解释,在计算左下角的区间时,它和前面的两个区间都重合,但是它却包含在最优解中,因为它的长度比前面两个的和还要长。
    这里求不重叠位置的时候,用了一个和c++中lower_bound函数类似的实现,和lower_bound的唯一差别在于返回的结果位置相差1。所以上述代码如果用C++来实现会更简单:

    const int MAX_N=100000;
    //输入
    int N,S[MAX_N],T[MAX_N];
    
    //用于对工作排序的pair数组
    pair<int,int> itv[MAX_N];
    
    void solve()
    {
        //对pair进行的是字典序比较,为了让结束时间早的工作排在前面,把T存入first,//把S存入second
        for(int i=0;i<N;i++)
        {
            itv[i].first=T[i];
            itv[i].second=S[i];
        }
    
        sort(itv,itv+N);
    
        dp[0] = itv[0].first-itv[0].second;
        for (int i = 1; i < N; i++)
        {
            int max;
    
            //select the ith interval
            int nonOverlap = lower_bound(itv, itv[i].second)-1;
            if (nonOverlap >= 0)
                max = dp[nonOverlap] + (itv[i].first-itv[i].second);
            else
                max = itv[i].first-itv[i].second;
    
            //do not select the ith interval
            dp[i] = max>dp[i-1]?max:dp[i-1];
        }
        printf(“%d\n”,dp[N-1]);
    }

    通过上面的分析,我们可以看出最大区间问题是一个应用范围更广的问题,最多区间调度问题是最大区间调度问题的一个特例。如果区间的长度都一样,则最大区间调度问题就退化为最多区间调度问题,进而可以利用更优的算法解决。一般的最大区间调度问题复杂度为: 排序 O(nlogn) +扫描 O(nlogn)=O(nlogn)

    3.3 带权的区间调度

    该问题可以看作最大区间调度问题的一般化,也即我们不只是求区间长度和的最大值,而是再在每个区间上绑定一个权重,求加权之后的区间长度最大值。先看一个例子:某酒店采用竞标式入住,每一个竞标是一个三元组(开始,入住时间,每天费用)。现在有N个竞标,选择使酒店效益最大的竞标。(美团2013年)
    该问题的目标变成了求收益的最大值,区间不重叠只是伴随必须满足的一个条件。但这不影响算法的适用性,最大区间调度问题的动态规划算法依旧适用于该问题,只不过是目标变了而已:最大区间调度考虑的是区间长度和,而带权区间调度考虑的是区间的权重和,就是在区间的基础上乘以一个权重,就这点差别。所以代码就很简单咯:

    const int MAX_N=100000;
    //输入
    int N,S[MAX_N],T[MAX_N];
    
    //用于对工作排序的pair数组
    pair<int,int> itv[MAX_N];
    
    void solve()
    {
        //对pair进行的是字典序比较,为了让结束时间早的工作排在前面,把T存入first,//把S存入second
        for(int i=0;i<N;i++)
        {
            itv[i].first=T[i];
            itv[i].second=S[i];
        }
    
        sort(itv,itv+N);
    
        dp[0] = (itv[0].first-itv[0].second)*V[0];
        for (int i = 1; i < N; i++)
        {
            int max;
    
            //select the ith interval
            int nonOverlap = lower_bound(itv, itv[i].second)-1;
            if (nonOverlap >= 0)
                max = dp[nonOverlap] + (itv[i].first-itv[i].second)*V[i];
            else
                max = (itv[i].first-itv[i].second)*V[i];
    
            //do not select the ith interval
            dp[i] = max>dp[i-1]?max:dp[i-1];
        }
        printf(“%d\n”,dp[N-1]);
    }

    博客介绍到这里,我们已经比较清楚上述三个问题的关系,带权区间调度应用最广,最大区间调度其次,最多区间调度应用范围最小。算法从通用的DP到特殊的DP再到贪心算法,难度逐渐降低。图六展示了三个问题的关系。
    这里写图片描述

    图6 三种调度问题的关系

    3.4 最小区间覆盖

    问题定义如下:有n 个区间,选择尽量少的区间,使得这些区间完全覆盖某给定范围[s,t]。
    初次遇到该问题,大家可能会把该问题想得很复杂,是不是需要用最长的区间去覆盖给定的范围,然后将给定范围分割成两个更小的子问题,用递归去解决。这时我们就需要获得在给定范围内的最长区间,但是如何判断最长区间却有太多的麻烦,而且即使选择了在给定范围内的最长区间,也不见得能获得最优值。其实该问题根本就没有想象中麻烦,可能很容易地解决。
    解决问题的关键在于,我们不要一开始就考虑整个范围,而是从给定范围的左端点入手。我们选择一个可以覆盖左端点的区间之后,就可以将左端点往右移动得到一个新的左端点。只要我们不停地选择可以覆盖左端点的区间就一定可以到达右端点,除非问题无解。关键是我们应该选择什么样的区间来覆盖左端点。由于我们要用选择区间的右端点和给定范围的左端点比较,所以第一想法会是先对所有的区间按照结束时间排序,然后按照结束时间从小到大和左端点比较。啥时候停止比较然后修改左端点呢?肯定是到了某个区间的开始时间大于给定范围的左端点的时候。这是因为如果我们继续遍历,可能就会不能完全覆盖给定范围。但是这样也可能会得不到最优解,如图七所示。
    这里写图片描述

    图7 按照结束时间排序的最小区间覆盖错误示意图

    在上图中,三个区间按照结束时间排序,第一个区间和给定范围的左端点相交,接着遍历第二个区间。这时发现第二个区间的左端点大于给定范围的左端点,这时我们就需要停止继续比较,修改给定范围新的左端点为end1。接着遍历第三个区间,按照上述规则我们就会将第三个区间也保留下来,但其实只需要第三个区间就满足要求了,第一个区间没有保留的意义,也即我们获得不了最优解。
    既然按照结束时间获得不了最优解,我们再尝试按照开始时间排序看看。区间按照开始时间排序之后,我们从最小开始时间的区间开始遍历,每次选择覆盖左端点的区间中右端点坐标最大的一个,并将左端点更新为该区间的右端点坐标,直到选择的区间已包含右端点。按照这种方法我们就可以获得最优解,但是为什么呢?算法其实根据区间开始时间的值将区间进行了分组:在给定范围左端点左侧的和在左端点右侧的。由于我们按照开始时间排序,所以这两组区间的分界线很明确。而为了覆盖给定的范围,我们必须要从分界线左侧的区间中选一个(否则就不能覆盖整个范围)。上述算法选择了能覆盖给定范围左端点中右端点最大的区间,这是一个最优的选择。对剩余的区间都执行这样的选择显然可以获得最优解。
    这里写图片描述

    图8 按照开始时间排序的最小区间覆盖示意图

    图八给出一个示例。四个区间已经按照开始时间排序,我们从I1开始遍历。I1和I2都覆盖左端点,I3不覆盖,选择右端点最大的一个end1作为新的左端点,并且将I1添加到最小覆盖区间中。然后重复上述步骤,将剩余的区间和新的左端点比较并选择右端点最大的区间,修改左端点,这时左端点就会变为end4,I4添加到最小覆盖区间中。依次处理剩余的区间,我们就获得了最优解。代码实现如下:

    const int MAX_N=100000;
    //输入
    int N,S[MAX_N],T[MAX_N];
    
    //用于对工作排序的pair数组
    pair<int,int> itv[MAX_N];
    
    int solve(int s,int t)
    {
        for(int i=0;i<N;i++)
        {
            itv[i].first=S[i];
            itv[i].second=T[i];
        }
    
        //按照开始时间排序
        sort(itv,itv+N);
    
        int ans=0,max_right=0;
        for (int i = 0; i < N; )
        {
            //从开始时间在s左侧的区间中挑出最大的结束时间
            while(itv[i].first<=s)
            {
                if(max_right<itv[i].end) max_right=itv[i].end;
                i++;
            }   
    
            if(max_right>s) 
            {
                 s=max_right;
                 ans++;
                if(s>=t) return ans;
            }
            else //如果分界线左侧的区间不能覆盖s,则不可能有区间组合覆盖给定范围
            {
                    return -1;
            }
        }
    }

    时间复杂度:排序 O(nlogn) +扫描 O(n)=O(nlogn)

    4. y轴上的区间调度

    x轴上的区间调度关注的是区间在一维空间上的摆放(重叠或者不重叠),而y轴上的区间调度则将问题扩展到二维。虽然维度增加了,但是解决问题的难度没有增大多少。

    4.1 最大区间重叠(最少工人调度)

    该问题似乎有两个矛盾的描述,既是最大又是最少,但其实是从不同的方面描述同一个问题。先看最大的一方面,问题可以这样描述:给定的n个区间,在任意时刻最多有几个重叠的区间,如图九所示,在12:00到12:30的范围内,最多有三个区间重叠,没有其他时刻超过三个区间重叠。WAP2013年的笔试题是从该角度考察该问题的(下载)。再看最少的一方面,假设我们将这些区间认为是一些工作,然后将这些工作分配给一些工人,每个工人不能同时干两件工作,最少需要几名工人。也即将所有的区间不重叠地摆在二维平面上,最少能够占据几行(很显然,可以一个工人干一件工作,这时n个工作就需要n个工人,也即在二维平面上一个工作占据一行,但显然不是最优的)。虽然该问题有两种理解方式,但是它们要解决的是同一个问题,所以解决方法相同。我们从最少工人调度角度看看如何解决该问题。
    这里写图片描述

    图9 最大区间重叠
    4.1.1 解法一

    在最多区间调度中,我们分配尽可能多的不重叠工作给工人,这启发我们是否可以沿着这个思路去解决问题。按照最多区间调度分配不重叠工作给第一个工人,如果还有剩余工作,肯定需要别的工人来完成,我们继续按照最多区间调度问题来解,并分配一个新的工人,…,直到没有工作为止。很可惜,上面的策略不可行,请看图十。如果按照最多区间调度的策略分配工作,下面四个工作需要分配三个工人,但实际最少只需要两个工人即可。问题出在最多区间调度采用的是贪心算法,只要是下一个工作和目前的最大结束时间不重叠就选择该工作,这就导致在判断I3时将该工作分配给了第一个工人。
    这里写图片描述

    图10 按照最多区间调度的策略实现最少工人调度

    这是否意味着上述策略就彻底不行呢?只要稍微改改选择工人的策略还是可以的。当我们在判断一个工作该分配给哪个工人时,我们需要选择可以接受该工作同时完成之前的工作最晚的工人。例如,图十中判断I3该分配哪个工人。这时前两个工人都可以选择该工作,但是第二个工人完成之前的工作更晚,所以需要将I3分配给第二个工人,而不是第一个工人。这样分配工作的目的是让结束时间早的工人能处理后面未知的工作,而不是浪费在一个已知工作上。上述思路需要我们保存每个工人的上一个工作结束时间,也即下一个工作可以开始的时间。由于工作都按照结束时间排序,所以在添加新的工人时,我们会产生一个非递减的序列。但是当可以将新的工作分配给现有工人时,我们需要在有序序列中找到合适的位置,并修改该工人的可工作时间。为了维持序列的单调性,我们需要移动不少元素。按这种策略实现的java代码如下:

    public int getMaxIntervalOverlapCount(List<Interval> intervals) {
            int maxWorkers = 0;
    
            Collections.sort(intervals, new EndTimeComparator());
    
            int[] endTime=new int[intervals.size()];        
            for(int i=0;i<intervals.size();i++)
            {
                int startTime=intervals.get(i).getBeginMinuteUnit();
                int pos=below_lower_bound(endTime, maxWorkers, startTime);
    
                if(pos==-1)
                {
                    endTime[maxWorkers++]=intervals.get(i).getEndMinuteUnit();
                }
                else
                {
                    for(int j=pos;j<maxWorkers-1;j++)
                    {
                        endTime[j]=endTime[j+1];
                    }
                    endTime[maxWorkers-1]=intervals.get(i).getEndMinuteUnit();
                }
            }
    
            return maxWorkers;
        }
    
        public int below_lower_bound(int[] a,int n,int k) {
            int lb = -1, ub = n;
    
            while (ub - lb > 1) {
                int mid = (ub + lb) >> 1;
                if (a[mid] >= k)
                    ub = mid;
                else
                    lb = mid;
            }
            return lb;
        }
    
        class EndTimeComparator implements Comparator<Object> {
            public int compare(Object arg0, Object arg1) {
                Interval i1 = (Interval) arg0;
                Interval i2 = (Interval) arg1;
    
                return i1.getEndHour() != i2.getEndHour() ? i1.getEndHour()
                        - i2.getEndHour() : i1.getEndMinute() - i2.getEndMinute();
            }
        }

    上述算法可以获得最优解,复杂度为:排序 O(nlogn) +查找 O(nlogn) +扫描 O(n2)=O(n2) 。上述算法虽然可以获得最优解,但是复杂度和其他问题相比显然上升了一个量级,导致复杂度为 O(n2) 的关键在于采用数组这种数据结构,找到合适的位置之后进行插入操作需要移动元素。如果采用平衡二叉树则会进一步降低复杂度到 O(nlogn) ,具体的实现大家可以自己尝试。

    4.1.2 解法二

    前面的解法按照结束时间排序,我们再看看按照开始时间排序是否可行。如图十一,四个工作已按照开始时间排序,我们看看如何将其分配给工人。既然按照开始时间排序,我们就从开始时间最小的工作开始分配。前三个工作肯定需要三个工人,关键是第四个工作该分配给谁。按照之前的策略,我们最好将I4和I2分配给同一个工人,这样分配I1工作的工人就可以分配其他未知的工作。如果采用这种策略,我们还是需要选择可以接受该工作同时完成之前的工作最晚的工人,这就意味着我们还是需要 O(n2) 的复杂度来解决问题。事实上,由于我们按照开始时间排序,所以后面未知工作的开始时间肯定会越来越晚,所以我们就不用担心该选择哪个工人的问题了,直接选择完成之前的工作结束时间最早的工人即可,也即将I1和I4分配给同一个工人。这样有什么好处呢?由于每次都是选择结束时间最早的工人,所以我们就可以选择一个最小堆来加速工人的寻找,从而降低整个算法的复杂度。
    这里写图片描述

    图11 按照开始时间排序实现最少工人调度

    具体的流程如下。我们用最小堆来维护一个工人完成之前工作的时间。当给新工作分配工人时,我们只需要将该工作的开始时间和堆顶的元素进行比较:如果堆顶的元素小于给定工作的开始时间,则可以将该工作分配给之前已经分配工作的工人,同时将堆顶元素修改成新工作的结束时间并重新调整堆;如果堆顶元素大于给定工作的开始时间,则表明目前分配工作的工人没有一个可以接受这个新工作,我们需要增加一个新的工人才行,同时往堆中增加该新工作的结束时间。按照这个思路实现的代码如下:

    public int getMaxIntervalOverlapCount(List<Interval> intervals) {
        int maxWorkers = 0;
        /*
        * 1 check the parameter validity
        */
    
        /*
         * 2 sort the jobs(intervals) based on the start time
        */
        Collections.sort(intervals, new StartTimeComparator());
    
        /*
        * 3 check the least number of needed workers
        */
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(intervals.size());
    
        // add the first job to the heap
        pq.add(intervals.get(0).getEndMinuteUnit());
        maxWorkers++;
    
        for (int i = 1; i < intervals.size(); i++) {
            // no allocated workers can do the next job
            if (pq.peek() >= intervals.get(i).getBeginMinuteUnit()) {
                maxWorkers++;
            } else {
                pq.poll();
            }
            pq.add(intervals.get(i).getEndMinuteUnit());
        }
    
        return maxWorkers;
    }
    
    class StartTimeComparator implements Comparator<Object> {
        public int compare(Object arg0, Object arg1) {
            Interval i1 = (Interval) arg0;
            Interval i2 = (Interval) arg1;
    
            return i1.getBeginHour() != i2.getBeginHour() ? i1.getBeginHour()
                        - i2.getBeginHour() : i1.getBeginMinute()
                        - i2.getBeginMinute();
        }
    }

    上述算法可以获得最优解,复杂度为:排序 O(nlogn) +扫描 O(nlogn)=O(nlogn) 。和按照结束时间排序相比,复杂度并没有变化,但是理解上更容易了,所以往后遇到该问题如果对复杂度没有进一步的要求,解决方案就是:开始时间排序+最小堆。

    4.1.3 解法三

    算法的优化是永无止境的,该问题还有一个复杂度更低的解法,可以在排序之后将扫描的复杂度降到 O(n) 。核心的思想是将区间的开始和结束时间分开考虑,然后采用顺序扫描的方法即可获得最优解。具体的步骤为:将每个区间拆成两个事件点,按坐标从小到大排序,顺序处理每个区间。记录一个值 ,表示当前点被包含次数。每次遇到区间的左端点就+1,遇到右端点就-1。需要工人的数量就是在该过程中 的最大值。时间复杂度为排序 O(nlogn) +扫描 O(n)=O(nlogn) 。这种解法的思路其实是从最大区间重叠的角度来考虑问题的,就介绍这么多,请自己实现代码。
    上面的三种解法都可以处理工人数没有限制的情况,但是如果限定工人的数目,然后看能选择多少区间(工作),则按照解法一会更方便。因为当只有一个工人的时候,该问题等价于最多区间调度,所以按照最多区间调度的思路去解决该问题会更容易。

    5. 综合区间调度

    在此我们简单介绍一下机器调度问题。机器调度问题和前面的区间调度问题很不一样。之前的调度问题中,给定的区间有一个固定的开始和结束时间,但是在机器调度中,每个区间或者叫任务都只包含一段执行时间,但是没有固定的开始时间。具体的问题描述如下:机器调度是指有m台机器需要处理n个作业,设作业i的处理时间为ti,则对n个作业进行机器分配,使得:
    - 一台机器在同一时间内只能处理一个作业;
    - 一个作业不能同时在两台机器上处理;
    - 作业i一旦运行,则需要ti个连续时间单位。
    设计算法进行合理调度,使得在m台机器上处理n个作业所需要的处理时间最短。如图十二,有三台机器,七个作业所需时间分别为(2,14,4,16,6,5,3),给出的调度最少需要17个单位时间。
    这里写图片描述

    图12 三台机器的调度

    机器调度问题是一个NP-复杂问题,我们可以认为不存在多项式复杂度的解法获得最优解。如果非要获得最优解,我们必须要采用深搜策略遍历解空间,机器调度的解空间是一个k叉树,表示某个作业分配给哪一个机器;树共有n层,每一个叶节点表示一个可能的任务分配,最小的叶节点即是最优解,算法复杂度是 O(kn)
    针对NP复杂的问题,一般也不会让我们获得最优解,求个近似最优就好了。在机器调度中,采用一个称为最长处理时间优先(longest processing time first, LPT)的调度策略会获得较理想的调度方案。在LPT算法中,作业按照它们所需处理时间的递减顺序排序。在分配一个作业时,总是将其分配给最先变为空闲的机器。具体实现比较简单,就是先排序,然后采用最小堆维护一个最小开始时间即可,和最大区间重叠的方法二比较相似,具体不再赘述。
    采用LPT策略有个定理:
    F(I) 为在m台机器上执行作业集合I的最佳调度完成时间,F(I)为采用LPT调度策略所得到的调度完成时间,则

    F(I)F(I)4313m

    可以看出,LPT策略和最优解很相近,是种比较好的近似策略。

    6. 总结

    本博客详细介绍了几类区间调度问题,给出了最优解的思路和代码。虽然并没有完全覆盖区间调度问题,但是已足以让大家应对各种笔试面试。关于尚未触及的区间调度问题及相关例题,大家可进一步参考算法合集之《浅谈信息学竞赛中的区间问题》。下表给出了每个问题的最优解法以及复杂度(由于所有的问题都要先进行排序,所以我们只关注扫描的复杂度)。
    这里写图片描述

    展开全文
  • 【MySQL】MySQL有几种

    千次阅读 多人点赞 2020-03-29 22:48:11
    即(6,10] 2 表级锁 (1) 描述 表级锁是mysql中锁定粒度最大的一锁,表示对当前操作的整张表加锁,它实现简单,资源消耗较少,被大部分mysql引擎支持。最常使用的MyISAM与InnoDB都支持表级锁定。表级锁定分为表共享...

    目录

    一、按照对数据操作的锁粒度来分:行级锁、表级锁、页级锁、间隙锁

    1 行级锁

    2 表级锁

    3 页级锁

    二、按照锁的共享策略来分:共享锁、排他锁、意向共享锁、意向排他锁

    innodb的意向锁有什么作用?

    三、从加锁策略上分:乐观锁和悲观锁

    四、其他:自增锁

    自增锁(AUTO-INC锁)

    外键检测的加锁策略


    一、按照对数据操作的锁粒度来分:行级锁表级锁页级锁、间隙锁

    MyISAM和MEMORY采用表级锁(table-level locking)

    BDB采用页面锁(page-level locking)或表级锁,默认为页面锁

    InnoDB支持行级锁(row-level locking)和表级锁,默认为行级锁

     

    1 行级锁

    (1) 描述

    行级锁是mysql中锁定粒度最细的一种锁。表示只针对当前操作的行进行加锁。行级锁能大大减少数据库操作的冲突,其加锁粒度最小,但加锁的开销也最大。行级锁分为共享锁和排他锁

    (2) 特点

    开销大,加锁慢,会出现死锁。发生锁冲突的概率最低,并发度也最高。

     

    其实行级锁和页级锁之间还有其他锁粒度的锁,就是间隙锁临键锁

    InnoDB有三种行锁的算法:

    1,Record Lock(记录锁):单个行记录上的锁。这个也是我们日常认为的行锁。

    2,Gap Lock(间隙锁):间隙锁,锁定一个范围,但不包括记录本身(只不过它的锁粒度比记录锁的锁整行更大一些,他是锁住了某个范围内的多个行,包括根本不存在的数据)。GAP锁的目的,是为了防止同一事务的两次当前读,出现幻读的情况。该锁只会在隔离级别是RR或者以上的级别内存在。间隙锁的目的是为了让其他事务无法在间隙中新增数据。

    3,Next-Key Lock(临键锁)它是记录锁和间隙锁的结合,锁定一个范围,并且锁定记录本身。对于行的查询,都是采用该方法,主要目的是解决幻读的问题。next-key锁是InnoDB默认的锁

    上面这三种锁都是排它锁(X锁)

     

    next-key lock的效果相当于一个记录锁加一个间隙锁。当next-key lock加在某索引上,则该记录和它前面的区间都被锁定。

    假设有记录1, 3, 5, 7,现在记录5上加next-key lock,则会锁定区间(3, 5],任何试图插入到这个区间的记录都会阻塞。

     

    注意,由于其效果相当于(3, 5)上的gap lock加5上的record lock,而且gap lock是可重入的相互不阻塞的(上文讲过),当其它事务试图获取(3, 5)的gap lock时,不会被阻塞;但如果要获取5上的record lock,就会阻塞;如果要获取5上的next-key lock,同样会阻塞。

     

    record lock、gap lock、next-key lock,都是加在索引上的。假设有记录1,3,5,7,则5上的记录锁会锁住5,5上的gap lock会锁住(3,5),5上的next-key lock会锁住(3,5]。

     

    注意,next-Key锁规定是左开右闭区间

    以这个图为例,插入id=10,它加的next-key其实就是一个左开右闭,id=6本身没有加锁,所以是开区间,id=10本身加锁了,所以是闭区间。即(6,10]

     

    2 表级锁

    (1) 描述

    表级锁是mysql中锁定粒度最大的一种锁,表示对当前操作的整张表加锁,它实现简单,资源消耗较少,被大部分mysql引擎支持。最常使用的MyISAM与InnoDB都支持表级锁定。表级锁定分为表共享读锁(共享锁)与表独占写锁(排他锁)

    (2) 特点

    开销小,加锁快,不会出现死锁。发生锁冲突的概率最高,并发度也最低。

    • LOCK TABLE my_table_name READ;  用读锁锁表,会阻塞其他事务修改表数据。
    • LOCK TABLE my_table_name WRITE; 用写锁锁表,会阻塞其他事务读和写。

    MyISAM在执行查询语句(SELECT)前,会自动给涉及的所有表加读锁,在执行更新操作(UPDATE、DELETE、INSERT等)前,会自动给涉及的表加写锁,这个过程并不需要用户干预,因此,用户一般不需要直接用LOCK TABLE命令给MyISAM表显式加锁。

    但是在InnoDB中如果需要表锁就需要显式地声明了。

     

    3 页级锁

    (1) 描述

    页级锁是 MySQL 中锁定粒度介于行级锁和表级锁中间的一种锁。表级锁速度快,但冲突多,行级冲突少,但速度慢。因此,采取了折中的页级锁,一次锁定相邻的一组记录。BDB 支持页级锁。

    (2) 特点

    开销和加锁时间界于表锁和行锁之间;会出现死锁;锁定粒度界于表锁和行锁之间,并发度一般。

     

    二、按照锁的共享策略来分:共享锁、排他锁、意向共享锁、意向排他锁

    共享锁和排他锁在MySQL中具体的实现就是读锁和写锁:

    • 读锁(共享锁):Shared Locks(S锁),针对同一份数据,多个读操作可以同时进行而不会互相影响
    • 写锁(排它锁):Exclusive Locks(X锁),当前写操作没有完成前,它会阻断其他写锁和读锁
    • IS锁:意向共享锁、Intention Shared Lock。当事务准备在某条记录上加S锁时,需要先在表级别加一个IS锁。
    • IX锁:意向排他锁、Intention Exclusive Lock。当事务准备在某条记录上加X锁时,需要先在表级别加一个IX锁。

    IS、IX锁是表级锁,它们的提出仅仅为了在之后加表级别的S锁和X锁时可以快速判断表中的记录是否被上锁,以避免用遍历的方式来查看表中有没有上锁的记录。就是说当对一个行加锁之后,如果有打算给行所在的表加一个表锁,必须先看看该表的行有没有被加锁,否则就会出现冲突。IS锁和IX锁就避免了判断表中行有没有加锁时对每一行的遍历。直接查看表有没有意向锁就可以知道表中有没有行锁。

    注意:如果一个表中有多个行锁,他们都会给表加上意向锁,意向锁和意向锁之间是不会冲突的。

     

    innodb的意向锁有什么作用?

    mysql官网上对于意向锁的解释中有这么一句话

    “The main purpose of IX and IS locks is to show that someone is locking a row, or going to lock a row in the table.”

    意思是说加意向锁的目的是为了表明某个事务正在锁定一行或者将要锁定一行。

    那么,意向锁的作用就是“表明”加锁的意图,可是为什么要表明这个 意图呢?

    如果仅仅锁定一行仅仅需要加一个锁,那么就直接加锁就好了,这里要表明加锁意图的原因是因为要锁定一行不仅仅是要加一个锁,而是要做一系列操作吗?

     

    我最近也在看这个,我说一下我的理解

    ①在mysql中有表锁,LOCK TABLE my_tabl_name READ;  用读锁锁表,会阻塞其他事务修改表数据。LOCK TABLE my_table_name WRITe; 用写锁锁表,会阻塞其他事务读和写。

    ②Innodb引擎又支持行锁,行锁分为共享锁,一个事务对一行的共享只读锁。排它锁,一个事务对一行的排他读写锁。

    ③这两中类型的锁共存的问题考虑这个例子:

    事务A锁住了表中的一行,让这一行只能读,不能写。之后,事务B申请整个表的写锁。如果事务B申请成功,那么理论上它就能修改表中的任意一行,这与A持有的行锁是冲突的。

    数据库需要避免这种冲突,就是说要让B的申请被阻塞,直到A释放了行锁。

     

    数据库要怎么判断这个冲突呢?

    step1:判断表是否已被其他事务用表锁锁表

    step2:判断表中的每一行是否已被行锁锁住

    注意step2,这样的判断方法效率实在不高,因为需要遍历整个表。

    于是就有了意向锁。在意向锁存在的情况下,事务A必须先申请表的意向共享锁,成功后再申请一行的行锁。在意向锁存在的情况下,

    上面的判断可以改成

    step1:不变

    step2:发现表上有意向共享锁,说明表中有些行被共享行锁锁住了,因此,事务B申请表的写锁会被阻塞。

     

    注意:申请意向锁的动作是数据库完成的,就是说,事务A申请一行的行锁的时候,数据库会自动先开始申请表的意向锁,不需要我们程序员使用代码来申请。

     

    总结:为了实现多粒度锁机制(白话:为了表锁和行锁都能用)

     

    当然,这四种锁都属于悲观锁

    意向锁之间都不会发生冲突,排他锁跟谁都冲突

     

     

    三、从加锁策略上分:乐观锁和悲观锁

    悲观锁认为对于同一个数据的并发操作,一定是会发生修改的(或者增删改多,查少),哪怕没有修改,也会认为修改。因此对于同一个数据的并发操作,悲观锁采取加锁的形式。悲观的认为,不加锁的并发操作一定会出问题

    乐观锁则认为对于同一个数据的并发操作,是不会发生修改的(或者增删改少,查多)。在更新数据的时候,会采用不断尝试更新的方式来修改数据。也就是先不管资源有没有被别的线程占用,直接取申请操作,如果没有产生冲突,那就操作成功,如果产生冲突,有其他线程已经在使用了,那么就不断地轮询。乐观的认为,不加锁的并发操作是没有事情的。就是通过记录一个数据历史记录的多个版本,如果修改完之后发现有冲突再将版本返回到没修改的样子,乐观锁就是不加锁。好处就是减少上下文切换,坏处是浪费CPU时间。

     

    四、其他:自增锁

    自增锁(AUTO-INC锁)

    自增锁是一种特殊的表级锁,主要用于事务中插入自增字段,也就是我们最常用的自增主键id。通过innodb_autoinc_lock_mode参数可以设置自增主键的生成策略。防止并发插入数据的时候自增id出现异常

    当一张表的某个字段是自增列时,innodb会在该索引的末位加一个排它锁。为了访问这个自增的数值,需要加一个表级锁,不过这个表级锁的持续时间只有当前sql,而不是整个事务,即当前sql执行完,该表级锁就释放了。其他session无法在这个表级锁持有时插入任何记录。


    相关文章:【MySQL】MySQL的锁与事务隔离级别详解
                      【MySQL】InnoDB行格式、数据页结构以及索引底层原理分析

    展开全文
  • 设连续随机变量X的一切可能值充满一个有限区间[a,b],且在该区间内任意 点概率的密度相同,即密度函数f(x)在区间[a,b]上为常量,称此分布为均匀分布 ,记作U(a,b) 当X在[a,b]上服从分布U(a,b)时,记为X~U(a,b). 二....
  • 测试常见几种方法

    千次阅读 2019-12-14 00:12:07
    顾名思义,顾名思义,等价类划分,就是将测试的范围划分成个互不相交的子集,他们的并集是全集,从每个子集选出若干个有代表性的值作为测试用例。  例如,我们要测试一个用户名是否合法,用户名的定义为:8位数字...
  • 机器学习模型的几种常用评估方法

    千次阅读 2020-06-03 18:40:21
    评估结果以模型评估报告的形式呈现,在报告中通过AUC值、模型准确率、模型召回率等一系列评估指标将帮助判断模型是否可行以及是否满足业务目标。 模型评估之 — 混淆矩阵 T——true,F——false,P——positive,N...
  • 一般分为两情况,第一类,是比例型数据,一般以XX率的形式出现,用来指示某项指标的达成情况,例如达成率,完成率等;第二类,是数值型数据,会根据具体业务的进行区间段划分,并和一些定性指标进行对应,例如台风...
  • 说明 ...目录说明1 前情提要1.1 参数设定1.2 数据集生成2 模型构建2.1 总体构建2.1.1 搭建模型2.1.2 获取注意力2.1.3 训练模型并可视化注意力3 注意力机制实现3.1 Baseline3.2 第一Attention机制
  • 区间覆盖问题

    千次阅读 2019-01-12 13:34:31
    一、设计题目 ★问题描述: 设x1,x2,…,xn是实直线上的n个点。用固定长度的闭区间覆盖这n个点,至少需要多少个这样的固定长度闭区间?...第1行有2个正整数n和k,表示有n个点,且固定长度闭区间的长度为k...
  • 随机变量及其分布和几种常见分布

    万次阅读 2018-05-27 21:47:09
    分布律也可以用表格的形式表示 ( I ) ( I ) (I) (0-1)分布 (离散型) 设随机变量 X X X 只可能取 0 0 0 与 1 1 1 两个值,它的分布律是 P { X = k } = p k ( 1 − p ) 1 − k , k = 0 , 1 ( 0 < p < ...
  • 大数定律以严格的数学形式表现了随机事件在足够的广度上的频率稳定性。利用这一性质,我们可以基于抽样样本中的均值来估计整体的均值。 它具有以下个变形: 切比雪夫大数定律 设相互独立的随机变量...
  • LSTM的基本架构以及几种变形LSTM

    千次阅读 2018-08-05 15:27:36
    本文内容及图片主要参考: Understanding LSTM ...有人专门比较总结过LSTM的变种,并比较了其效果,结果显示这些变种表现差不多,具体参见 Greff, et al. (2015) 及 Jozefowicz, et al. (2015) 。
  • 几种激活函数的比较

    万次阅读 2017-04-14 17:21:30
    激活函数:用来加入非线性因素的,因为线性模型的表达能力不够 比如下图的数据比较简单是线性可分的,一条直线就可以对样本进行...下面介绍个常用的激活函数: 1.sigmoid函数:用于隐层神经元输出 函数图像为:
  • 但中心极限定理也分表现形式,以下是常见的四中心极限定理 1.辛钦中心极限定理 当 X 1 X_1 X 1 ​ , X 2 X_2 X 2 ​ , X 3 X_3 X 3 ​ , ⋯ \cdots ⋯ , X n X_n X n ​ 为独立同分布的随机变量,有限...
  • 计算机编程中几种数据类型

    千次阅读 2020-02-17 15:06:01
    INT型: ...1、有符号记为int型,其中还包括short、long等也可以表达整型,有符号int型的存储形式为补码形式。 2、无符号记为unsigned int型,数据范围为[0~2^32-1] 当将int型与unsigned int型的混...
  • 数据预处理的几种方法

    千次阅读 2020-02-08 08:30:00
    #参数missing_value为缺失值的表示形式,默认为NaN #参数strategy为缺失值填充方式,默认为mean(均值) Imputer().fit_transform(vstack((array([nan, nan, nan, nan]), iris.data))) 2、异常值 2.1 处理方法...
  • MySQL 面试题

    万次阅读 多人点赞 2019-09-02 16:03:33
    当年,我们记着个一定要掌握的重心: 重点的题目添加了【重点】前缀。 索引。 锁。 事务和隔离级别。 因为 MySQL 还会有部分内容和运维相关度比较高,所以本文我们分成两部分【开发】【运维】两部分。 对于...
  • 九九乘法表的几种Python算法

    千次阅读 多人点赞 2019-03-19 16:29:20
    首先可以看成是两个1到10的for循环的嵌套,两个10到10的数组的笛卡尔集,去除掉重复的部分,就是第二个循环range返回变成从1取到i(外层循环)但是这里要注意,range是一个半开半闭的区间,所以右边最后一个数取不到...
  • ubuntu使用教程

    万次阅读 多人点赞 2020-01-15 17:53:05
    Ubuntu(乌班图)是一个基于Debian的以桌面应用为主的Linux操作系统,据说其名称来自非洲南部祖鲁语或科萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一价值观。 Ubuntu的...
  • 模糊PID算法及其MATLAB仿真(1)

    万次阅读 多人点赞 2019-04-15 20:34:35
    最常见的运算方法有以下几种: (1)最小运算法 最小运算法也称 Mamdani 方法,即取隶属度函数极小值。 (2)积运算 积运算也称 Larsen 方法,故名思意,就是取隶属度函数的乘积。 (3)算数运算 算数运算也称 Zadeh...
  • 导入matplotlib库 # 第一导入方式 import matplotlib.pyplot as plot # 第二导入方式 from matplotlib import pyplot as plt 科学计算库 import numpy as np ...# 产生[1,1.9]区间内步长为0...
  • 天在做有关dp的题,看到一个石子合并的问题,本来以为是个贪心,后来仔细一想压根不是贪心。贪心算法的思路是每次都取最大的,然而石子合并问题有个限制条件就是每次只能取相邻的,这就决定了它不是个贪心… ...
  • 这一篇是阐述如何选择可视化图表的最后一部分,主要是以下类数据的可视化: 区间型数据:区间型数据一般是用来显示数据当前的进度情况,数据格式一般为...通过阅读资料可知,区间型数据大致分为两: 比例型...
  • CNN的几种经典模型

    千次阅读 2019-04-01 12:53:43
    本文主要介绍一下CNN的几种经典模型比较。之前自己也用过AlexNet和GoogleNet,网络上关于各种模型的介绍更是形形色色,自己就想着整理一下,以备自己以后查阅方便 LeNet5 先放一张图,我感觉凡是对深度学习有涉猎...
  • 测试用例的几种常见设计方法

    万次阅读 多人点赞 2018-04-28 14:56:27
    等价类划分法 顾名思义,等价类划分,就是将测试的范围划分成个互不相交的子集,他们的并集是全集,从每个子集选出若干个有代表性的值作为测试用例。 例如,我们要测试一个用户名是否合法,用户名的定义为:8位...
  • 查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译...本文简单概括性的介绍了常见的七查找算法,说是七,其实二分查找、插值查找以及斐波那契查找都可以归
  • Google Guava 8-区间

    2017-11-17 10:20:16
    [Google Guava] 8-区间 原文链接 译文链接 译文:沈义扬 范例 1 List scores; 2 Iterable belowMedian =Iterables.filter(scores,Range.lessThan(median)); ...
  • 卡尔曼滤波系列——(二)扩展卡尔曼滤波

    万次阅读 多人点赞 2019-04-06 16:33:48
    扩展卡尔曼滤波(Extended Kalman Filter,EKF)是标准卡尔曼滤波在非线性情形下的一扩展形式,它是一高效率的递归滤波器(自回归滤波器)。 EKF的基本思想是利用泰勒级数展开将非线性系统线性化,然后采用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,730
精华内容 22,692
关键字:

区间的几种表示形式