F1rry's blog
首页
时间轴
标签
分类
友链
avatar
文章
20
标签
12
首页
时间轴
标签
分类
友链
目录
  1. 1. 图论算法
    1. 1.1. 一些概念和数据结构
      1. 1.1.1. 一些概念的简单理解
      2. 1.1.2. 一些表示图的数据结构
    2. 1.2. 拓扑排序
      1. 1.2.1. 实现算法
    3. 1.3. 最短路径算法
      1. 1.3.1. 无权最短路径
      2. 1.3.2. 有权最短路径
      3. 1.3.3. 具有负边值的单源最短路径问题（无负值圈）
      4. 1.3.4. 无权图的单元最短路径问题
    4. 1.4. 网络流问题
      1. 1.4.1. 一种简单算法的实现
    5. 1.5. 最小生成树问题
      1. 1.5.1. Prim 算法
      2. 1.5.2. Kruskal 算法
    6. 1.6. 深度优先搜索的应用
      1. 1.6.1. 判断无向图是否连通以及生成深度优先生成树
      2. 1.6.2. 判断有向图是否连通且是否为无圈图
      3. 1.6.3. 查找无向连通图的所有割点
      4. 1.6.4. 查找强分支
      5. 1.6.5. 欧拉回路
    7. 1.7. NP-完全性介绍
      1. 1.7.1. NP类
      2. 1.7.2. NP-完全问题
图论算法
字数总计:7.2k|阅读时长: 22 分钟
|阅读量:

图论算法

一些概念和数据结构

一些概念的简单理解

  • 简单路径
    一条路径上的点均互异（起点和终点可以一样）

  • 圈
    一条路径上起点与终点一样，且路径长至少为1的路径

  • 无向图
    点与点之间的边没有方向

  • 有向图
    点与点之间的边具有方向

  • 连通性
    无向图中每个顶点到其他顶点都存在至少一条路径，那么该无向图就是连通的

  • 强连通性
    有向图中每个顶点到其他顶点都存在至少一条路径，那么该有向图就是强连通的

  • 弱连通性
    如果一个有向图不是强连通的，但它的基础图(有向图上的边去掉方向形成的)是连通的，那么该有向图就是弱连通的

  • 完全图
    每一对顶点都存在一条边的图

一些表示图的数据结构

  • 邻接矩阵
    它是一个二维数组，对于每条边 $(u,v)$ ，置$A[u][v]$为 $true$ 或置为 $k$ ($k$为该边的权值)，不存在的边则置为 $false$ 或置为$-\infty$ 或 $\infty$

    其缺点在于只能表示顶点较少的图，因为其占用空间为 $\Theta(|V|^2)$，一旦顶点较多，其占用内存将很大

    该数据结构对于稠密图比较适用，对于稀疏图就采取下面的数据结构即邻接表

  • 邻接表
    该数据结构对于 稀疏图 以及 顶点数较多 的图比较适用，因为它的空间需求仅为 $O(|E|+|V|)$

    邻接表是表示图的标准方法。
    该表首先将图上的各个顶点映射为该邻接表上的具体位置，例如 $v_1$ 就映射在该邻接表的第二个位置上。
    而存储在该位置上的信息则是与该顶点存在一条边的其他顶点所对应的位置的集合，例如，顶点1与顶点2,3,4有边连接，那么 $V[1] = [2,3,4]$
    具体如下图所示

    QQ截图20200212174907.jpg

    而无向图也可以类似的表示，只不过一条边会出现在两个表项之中（因为是无向的）

拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从 $v_i$ 到 $v_j$ 的路径，那么在排序中 $v_j$ 就出现在 $v_i$ 的后面

实现算法

其基本思路为每次找到一个入度为0且尚未编号的顶点，删除它，并更新邻接顶点的入度，重复这个操作，直到没有尚未编号的顶点。
它可以有两种实现

  • 基于顺序扫描邻接表的实现
    该算法的主要缺点在于运行时间过长，由于是顺序扫描邻接表来找到入度为0且尚未编号的顶点的，所以它的一趟查找需要 $O(|V|)$ 的时间，而又需要执行 $|V|$ 趟排序，所以总共需要 $O(|V|^2)$ 的运行时间

  • 基于栈或队列的实现
    为了优化上述简单算法，才有了基于栈或队列的实现，如果使用邻接表，执行这个算法使用的时间为$O(|E|+|V|)$
    首先，对每个顶点计算它的入度，把入度为0的顶点放入队列中
    每次操作，如果队列非空，则从队列中取出队首元素，为其编号，并更新邻接顶点的入度，同时把更新过后入度为0的顶点放入队列中。如果队列为空，则拓扑排序完成，其拓扑排序就是元素出队的顺序

最短路径算法

首先明确两种路径长

  • 赋权路径长
    对于有权图，我们设边 $(v_i,v_j)$ 的权值为 $c_{i,j}$，一条路径 $v_1v_2v_3…v_n$ 的赋权路径长为 $\sum_{i=1}^{N-1}c_{i,i+1}$

  • 无权路径长
    对于无权图，它的路径长即为无权路径长

而最短路径算法可以分为

  • 单源最短路径算法

  • 所有点对最短路径算法

其中所有点对最短路径算法可以通过对每个点执行一次单元最短路径算法来完成

所有下面我们要介绍的是都是 单源最短路径问题 ，它值的是给定一个赋权图 $G=(V,E)$ 和一个特定顶点 $s$ 作为输入，找出从 $s$ 到 $G$ 中每一个其他顶点的最短赋权路径
ps: 当遇到负值圈时（含有负值边的圈），最短路径问题就是不确定的，因为我们可以重复结果该负值圈来使得整条路径的权值降低。

以下是 单源最短路径问题 的各个子问题

无权最短路径

显然，这是赋权最短路径问题的特殊情况，因为我们可以为所有的边都赋权值为1，此时我们只关注路径长，即经过的边数。

解决 无权最短路径问题 的一个好的思路是使用 广度优先搜索 ，该方法按层处理：距离起始点最近的顶点最先被处理（即将该顶点标记为已访问，且记录起始点到该顶点的最短路径），最远的顶点最后被处理。

而实现 广度优先搜素 也有两种实现

  • 基于顺序扫描邻接表的实现
    我们设置一个变量 $d$ 来记录路径长

    1. 初始化 $d$ 为 $0$ ，初始化所有顶点，使它们都表示未标记，且最短路径均为 $\infty$ （除起始点设置为已标记，且最短路径为 $0$ ）

    2. 遍历所有顶点，取出每个顶点 $v$ ，检查它是否已被标记且最短路径为 $d$，

      • 如果是，则遍历他的邻接点，判断它们的最短路径长是否为 $\infty$

        • 如果是，则更新邻接点的最短路径长为 $d + 1$，以及更新邻接点在最短路径中前一个顶点为 $v$

        • 如果不是就忽略

      • 如果不是就忽略

    3. 更新 $d$ 为 $d+1$ ，重新执行步骤2，直到所有顶点设置为已标记。

      该算法的主要缺点也在于运行时间，在步骤2中我们不仅遍历了所有顶点，还遍历了与未标记顶点相邻的邻接点，这导致了运行时间变为了 $O(|V|^2)$

  • 基于栈或队列的实现
    该实现基于一种这样的想法。假设我们有两个盒子，第一个盒子装有最短路径为 $d$ 的顶点，第二个盒子装有最短路径为 $d+1$的顶点，每次我们从第一个盒子中取出一个顶点，然后将与该顶点相邻且未标记的邻接点放入第二个盒子，直到第一个盒子取完，我们用第二个盒子取代第一个盒子，循环往复，直到所有顶点均被标记。

    1. 初始化 $d = 0$，将起始点的最短路径设置为 $d$ ，并放入一个空队列中
    2. 取出队列中的队首元素，并根据邻接表分别取出他们的邻接点，如果它们的最短路径为 $\infty$ ，则将它们的最短路径设置为 $d + 1$,并更新它的前置元素，放入队列中

    3. 重复步骤2，直到队列为空

      使用与对拓扑排序一样的分析，我们可以得到如果使用邻接表那么他的运行时间即为 $O(|E|+|V|)$

有权最短路径

解决 有权最短路径 的一个好思路是使用 $Dijkstra$ 算法（迪杰斯特拉算法），它是贪婪算法中的一个经典算法，即分阶段处理问题，且在每个阶段它都把出现的当做是最好的去处理。

在 $Dijkstra$ 算法解决有权最短路径问题时，它每次取出当前最短路径长最小的顶点$v$，标记该顶点为已访问，然后取出该顶点的邻接点$w$，如果$d_v+c_{v,w}$路径长 < 该邻接点的最短路径长且该顶点未被标记为已访问，那么更新该邻接点最短路径长为 $d_v+c_{v,w}$。

同样它也有两种实现

  • 基于顺序扫描邻接表的实现
    其实现思路跟上述无权最短路径的基于顺序扫描邻接表的实现大同小异，不同点只不过是每次取得都是最短路径长最小的顶点 $v$ 。

    由于每次查找最小值需要花费 $O(|V|)$ 的运行时间，因此整个算法过程中查找最小值需要花费的总时间为 $O(|V|^2)$，而更新 $d_w$ 需要花费常数时间，每条边最多更新一次，所有用于更新 $d_w$ 的总时间为 $O(|E|)$，所以算法总运行时间为 $O(|E|+|V|^2)=O(|V|^2)$

    对于稠密图来说 $E = \Theta(|V|^2)$，则该算法不仅简单而且基本上是最优的，而对于稀疏图，可以采用基于优先队列的实现。

  • 基于优先队列（堆）的实现
    其实现思路如下

    1. 将起始点设置为最短路径长为0的点，其他顶点最大路径长为 $\infty$，他们一同构造一个最小堆（按照最短路径长来构造），此时起始点在根部。

    2. 执行一次 deleteMin 操作取出根元素，并用 decreaseKey 操作更新根元素的邻接顶点的最短路径长（如果新值比旧值要小的话）和它的前置元素，此时需要重构一次堆。

    3. 重复执行步骤2，直到堆空为止。

      由于每次 deleteMin 所花时间为 $O(log|V|)$ ,且每条边也最多更新一次。故其运行时间为 $O(|E|log|V|+|V|log|V|) = O(|E|log|V|)$

具有负边值的单源最短路径问题（无负值圈）

其算法思路如下

  1. 将起始点最短路径$d_v$初始化为$0$，并将它放入队列中
  2. 取出队首元素，并遍历队首元素的邻接点$w$，如果$d_w + c_{v,w} < d_w$，则更新 $d_w = d_w + c_{v,w}$ 和它的前置元素，如果此时 $w$ 不在队列中，则将其插入队列
  3. 重复步骤二直到队列为空

由于每个顶点最多可以出队$|V|$次，而每次出队遍历邻接点的次数为 $|E|$ 次，所以其使用邻接表时的运行时间为 $O(|E||V|)$。

为了防止出现负值圈的情况，可以把出队次数限定在 $|V|+1$ 次内来解决

无权图的单元最短路径问题

如果知道图是无圈的，那么我们可以通过改变顶点选择的方法来改进迪杰斯特拉算法。新的顶点选择法用以拓扑顺序选择顶点。由于选择和更新可以在拓扑排序执行的时候进行，因此算法能够一趟完成。这种方法不需要优先队列，且运行时间为 $O(|E|+|V|)$

无圈图的一个重要应用是 关键路径分析法

当给出一个动作节点图时，我们首先将它转换为一个事件节点图。
为了找出方案的最早完成时间$EC_i$，我们只要找到从第一个事件到最后一个事件的最长路径的长。其中

  • $EC_1 = 0$
  • $EC_i = max_{(v,w) \in E}(EC_v + c_{v,w})$

而我们也可以计算事件的最晚完成时间$LC_i$为

  • $LC_n = EC_n$
  • $LC_v = min_{(v,w) \in E}(LC_w - c_{v,w})$

事件节点图中每条边（对应于动作节点的每个动作）的松弛时间 $Slack_{v,w} = LC_w - EC_v - c_{v,w}$

松弛时间为0的一些动作称为关键动作。至少存在一条完全由关键动作组成的路径，我们称为 关键路径

网络流问题

设给定有向图 $G = (V,E)$,其边容量为 $c_{v,w}$。这些容量可以代表通过该边的流量。同时有两个顶点，一个叫发点(顶点$s$)，一个叫收点(顶点$t$)。在既不是发点，又不是接点的其他顶点 $v$ ，总的进入的流必须等于总的发出的流。
而最大流问题就是确定从发点到接点可以通过的最大流量

一种简单算法的实现

我们通过给定的有向图 $G$ ，构造一个流图 $G_f$ ，一个残余图 $G_r$。

其中残余图表示对于每条边它还能再添加上多少流，它可以通过 $G - G_f$ 得到。同时，为了让算法能改变它的意向，对于流图中具有容量 $f_{v,w}$的每一边 $(v,w)$，我们在残余图上添加容量同为 $f_{v,w}$ 但方向相反的残余边 $(w,v)$

下面是这三种图的例子(注意红色箭头所指出的方向相反的残余边)

QQ截图20200212233333.jpg

现在开始算法思路的描述

  1. 寻找图 $G_r$ 从 $s$ 到 $t$ 的一条路径，这条路径叫增长通路。这条路径上的最小边值 $f_{min}$ 就是可以添加到路径每一条边上的流量。

  2. 使用 $f_{min}$ 更新流图中这条路径上的所有边，即$f_{v,w} = f_{origin} + f_{min}$，同时更新残余图中对应的残余边，如果更新后某一残余边 $f_{v,w} = 0$ ，那么删除该残余边

  3. 重复步骤二，直到没有一条从 $s$ 到 $t$ 的路径，结束算法

如果容量都是整数，且最大容量为 $f$ ，那么由于每条增长通路使流的值至少增1，故 $f$ 个阶段足以，又因为通过无权最短路径算法找到一个增长通路的运行时间为 $O(|E|)$，从而总的运行时间为 $O(f|E|)$

而这个运行时间是坏的，例如下图，如果增长通路通过由 $a$ 和 $b$ 连接的边的路径而连续增长，那么他就需要 $2000000$ 条增长通路

QQ截图20200213000151.jpg

为了避免这种情况，有两种方法

  • 总选择容许在流中最大增长的增长通路
    可以通过类似迪杰斯特拉算法的思路来实现
    如果 $cap_{max}$ 为最大边容量。那么对于通路的每一次计算都需要 $O(|E|\log cap_{max})$ ,所以总的运行时间为 $O(|E|^2 \log |V| \log cap_{max})$ ,如果最大边容量为小整数时，则可以将运行时间减为 $O(|E|\log |V|)$

  • 总选择具有最少边数的路径
    运行时间界为 $O(|E|^2|V|)$

最小生成树问题

一个无向图$G$的最小生成树就是该图的那些连接 $G$ 的所有顶点的边构成的树，且其总价值最低。
最小生成树是无圈的，且它的边数为 $|V|-1$
对于解决最小生成树问题，有两种解法

Prim 算法

Prim 算法的简单描述如下
在算法的开始我们选取一条权值最小的边，然后将该边连接的两个顶点添加到树上，然后执行下面的操作
每次选取一条边 $(u,v)$ ，该边需要满足的条件如下

  • 顶点 $u$ 在树上
  • 顶点 $v$ 不在树上
  • 边 $(u,v)$ 在未被添加到树上的所有边中权值最小

当选中该边时，就将顶点 $v$ 添加到树上，重复以上步骤，直到所有顶点被添加到树上。

其具体实现如下

我们规定 $d_v$ 表示顶点距离树的最短距离， $p_v$ 表示使得 $d_v$ 最后一次改变的顶点

  1. 初始化，将所有顶点都标记为未访问，且所有边距离树的最短距离 $d_v$ 都设为 $\infty$

  2. 选取一条最短边，将该边的两个顶点标记为已访问，且设置他们距离树的最短距离 $d_v$ 为 $0$，然后更新他们邻接点中 $d_v$ 为 该连接边的权值$c_{v,u}$ ,以及更新他们的 $p_v$

  3. 选取 $d_v$ 最小的点，把它标记为已访问，并且如果它邻接点的 $d_v$ 值为 $min{d_v,d_v+c_{v,u}}$,并更新他们的 $p_v$

  4. 重复执行步骤三直到所有点被标记完成

倘若不使用堆的数据结构，它对稠密图来说是个好算法，其运行时间为 $O(|V|^2)$ ，如果使用堆结构，则适用于稀疏图，其运行时间为 $O(|E| \log |V|)$

Kruskal 算法

其算法的简单描述如下
我们每次选取权值最短的边，如果该选取的边不会使现有的数变成有圈图，那么我们就接受它，否则放弃它，进行下一轮选择，直到所有的顶点构成一颗树。

可想而知，该算法处理的是一个森林——树的集合，在这里，我们可以使用不相交集合的数据结构，即等价类。当两个顶点在同一颗树时，他们便是等价的。

我们可以使用 find 操作来判断它们是否处于同一颗树，而使用 union 操作来让两个顶点处于同一颗树。

我们可以用最小堆来存储各个边，这样该算法的最坏情形运行时间为 $O(|E|\log|E|)$，由于 $|E| = O(|V|^2)$，所以该算法的最坏情形运行时间也为 $O(|E|\log|V|)$

深度优先搜索的应用

深度优先搜索是对先序遍历的一种推广，用简单的话来说，深度优先搜索每次选取的顶点是更深一层次的顶点（子节点），它不同于广度优先搜索（每次选取的顶点是同一层次的顶点（兄弟节点））

对于深度优先搜索，我们可以通过递归调用来实现。

因为该方法保证每条边只访问一次，因此总共需要访问 $|E|$ 次调用，但不能保证图是连通的，故最坏情况是有|V|个连通分图（即每个点都不相连），因此我们需要保证执行 $|V|$ 次遍历，所以只要使用邻接表，则执行遍历的总时间就是 $O(|E|+|V|)$

判断无向图是否连通以及生成深度优先生成树

深度优先搜索在无向图中的一种应用是可以判断无向图是否是连通的。
无向图是连通的，当且仅当从任一节点开始的深度优先搜索访问到每一个节点。
无向图的深度优先搜索($dfs()$)实现算法也很简单：
遍历每个节点，对每个节点判断它是否已被访问

  • 若未被访问，则将该节点 $w$ 标记为已被访问，其前置顶点为传进来的顶点 $v$，传递给 $dfs(w)$ 函数，即递归调用深度优先搜索
  • 若已被访问，则跳过

该算法直到所有顶点被访问为止。
可想而知，如果无向图是连通的，那么他将会生成一棵树，我们叫做深度优先生成树
而如果无向图是不连通的，那么他将会生成一个由深度优先生成树组成的深度优先生成森林

由于我们在实行深度优先搜索的时候，我们会遇到这样一种情况，在调用 $dfs(v)$ 的时候，我们发现其邻接点 $w$ 已被访问，此时边 $(v,w)$ 在深度优先生成树中就被称为 背向边

判断有向图是否连通且是否为无圈图

其实现算法与无向图的相同
但还是有所区别，即无向图中只有一种类型的边——背向边不通向于新的顶点，但有向图存在三种不同类型的边不通向于新的顶点，他们分别是

  • 背向边

  • 前向边
    他们从树的一个节点通向它的一个后裔（至少为孙子节点）

  • 交叉边
    他们把不直接相关的两个树节点连接起来

三种边的示例图如下

QQ截图20200213221609.jpg

而深度优先搜索在有向图中的一种应用就是检查是否是无圈图，如果它是无圈图，那么它就不存在背向边

查找无向连通图的所有割点

一个连通的 无向图 如果不存在被删除之后使得剩下的图不再连通的顶点，那么这样的无向连通图就称为双连通的
如果存在这样的顶点，那么该顶点叫做割点。
而深度优先搜索提供一种找出连通图中所有割点的线性时间算法。
它主要分为三个步骤：

  1. 计算 $Num$ ，通过生成一个深度优先生成树得到
  2. 计算 $Low$
  3. 检验哪些顶点满足割点的标准

其算法的简单描述如下所示，它是基于深度优先生成树而来的

计算 $Num$
从任一一点开始，执行深度优先搜索算法并在顶点被访问时给他们编号，对于每一个顶点 $v$ 我们称其先序编号为 $Num(v)$。

计算 $Low$
对于深度优先生成树上的每个顶点$v$，我们计算编号最低的顶点$w$，我们称之为 $Low(v)$
该 $w$ 是这样的：我们可以从顶点 $v$ 开始经过数的 $0$ 条或多条边，且可能还经过至多一条背向边，到达某个顶点，而$w$是满足这些条件中编号最小的顶点

根据 $Low(v)$ 的定义可知 $Low(v)$ 是以下三者中的最小者

  • $Num(v)$
    不选取任何边

  • 所有背向边 $(v,w)$ 中的最低 $Num(w)$
    不选取树的任何边，而只选取一条背向边

  • 树的所有边 $(v,w)$ 的最低 $Low(w)$
    选取树的某些边，包括一条背向边，它可以通过递归调用来实现

由于我们需要对 $v$ 的所有儿子计算出 $Low$ 值后才能计算 $Low(v)$ ,因此这是一个后序遍历。我们只需要扫描 $v$ 的邻接表，应用适当的法则，并记住最小值。所有的计算花费 $O(|E|+|V|)$ 的运行时间。

检验哪些顶点满足割点的标准
找割点的标准，它基于这样一种判断，如果根节点只有一个儿子，那么该根节点就不是割点，如果多于一个儿子，那么删除该根，就会使得不同子树上的节点不相连。

所以我们可以这样判定一个顶点是否为割点
对于任何其他顶点 $v$ ，当且仅当它有某个儿子 $w$ 使得 $Low(w)\geq Num(v)$。注意这个条件在根节点总是满足的，所以根节点需要特殊判定

对这三个步骤的合并
我们可以用一趟先序遍历来执行步骤1，然后再用一趟后序遍历执行步骤2，最后再通过一趟遍历来执行步骤三来完成整个算法

当然我们可以通过一趟遍历来同时完成三个步骤

查找强分支

如果一个有向图不是强连通的，那么我们其实可以得到一些顶点的子集，使它们到自身是强连通的。
其实现算法如下

  1. 输入有向图$G$执行一次深度优先搜索，得到一颗深度优先生成树
  2. 对该树进行一次后序遍历将有向图 $G$ 各个顶点编号
  3. 将有向图 $G$ 各个边反向，得到 $G_r$
  4. 我们总是从编号最大且未被访问的顶点开始，将该顶点传入深度优先搜索算法中，即 $dfs(v)$
  5. 当所有的顶点被访问完毕，得到 $n$ 个子集，子集里面的各个顶点是强连通的，即每个子集是一个强分支

欧拉回路

欧拉回路类似于我们以前玩的一笔画，它需要我们找到一个圈，使得每条边恰好经过一次。
有欧拉回路的图的充分必要条件如下

  • 每个顶点的度为偶数
  • 图是连通的

而与欧拉回路类似的还有一种叫做欧拉环游，它的路径不需要回到起点，但必须经过每一条边。

有欧拉环游的图有以下特点

  • 每个顶点的度为偶数（允许存在一种含有2个奇数度顶点的情况）
  • 图是连通的

但我们这里讲述的是欧拉回路的算法，它的思路大致如下

  1. 传入一个顶点 $v$ ，以该顶点为起点执行一次深度优先搜索（下一次找到该顶点为止），同时在执行深度优先搜索时，删除经历过的边（即在邻接表中删除对应项），此时我们得到一个圈。
  2. 大多数情况下，这个圈还不包含所有的边，所以此时我们传入顶点 $v$ 在该圈中的下一个顶点 $w$，执行第一步里面的操作
  3. 如果此时该圈还没有包含所有的边，那么我们重复执行步骤2，直到该圈包含所有的边，该圈就是我们要找的欧拉回路

使用适当的数据结构时，其运行时间为 $O(|E|+|V|)$

示例图如下

QQ截图20200213221755.jpg

NP-完全性介绍

对于上述所有问题的某些变化，将会形成新的问题，我们在这里称之为 变种问题，对于一些糟糕的变种问题，我们不仅不知道线性算法，而且不存在保证以多项式时间运行的已知算法。这些问题的一些熟知算法对于某些输入可能要花费指数时间

而我们存在大量重要问题，它们在复杂性上大体是相同的。这些问题形成一个类，叫做 NP-完全（NP-complete）问题。这些 NP-完全 问题精确的复杂度任然需要确定并且在计算机理论科学方面仍然是最重要的开放性问题。或者它们都有多项式时间解法，或者它们都没有多项式时间解法

在现实生活中，存在一类不可能解决的问题，它们叫做不可判定问题,例如停机问题
而 NP 类问题 是仅次于 不可判定问题的一类问题

NP类

NP(nondeterministic-polynomial-time) 代表非确定型多项式时间

这里有两个模型

  • 确定型机器
    每一个时刻都在执行一条指令，根据这条指令再去执行某条接下来的指令，这是唯一确定的。

  • 非确定型机器
    自我感觉它类似于人脑，它对其后的步骤是有选择的，它可以自由的进行它想要的选择。如果这些步骤中有一条导致问题的解，那么它将总是选择这个正确的步骤

检测一个问题是否属于 NP 的简单方法是将该问题转换为一个用“是/否”来描述的问题。如果我们在多项式时间内能够证明一个问题的任意“是”的实例是正确的，那么该问题就属于 NP 类。

如我们可以判断哈密尔顿圈问题是否是一个 NP 问题，其判断如下
首先将哈密尔顿问题转换为一个“是/否”来描述的问题 “图中任意一个包含所有顶点的简单的回路是否是哈密尔顿圈？”
该问题的一个“是”的实例为 图中任意一个包含所有顶点的简单的回路是哈密尔顿圈。
而验证这个实例正确是十分简单的。所以哈密尔顿圈问题时应该 NP 问题

NP-完全问题

NP-完全问题 是 NP 问题的一个子集，它包含了 NP 中最难的问题。
它有一个性质即 NP 中的任意一个问题都能以多项式时间规约成 NP-完全问题，这也使得它可以用作 NP 中任何问题的子例程
证明一个问题是否是 NP-完全问题，需要证明是否能将某个 NP-完全问题规约成为该问题，如果能，则该问题就是 NP-完全问题

文章作者: f1rry
文章链接: http://yoursite.com/2020/02/10/图论算法/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 F1rry's blog！
JAVA 数据结构
相关推荐
2020-02-03
JAVA 散列
2020-02-01
优先队列
2020-02-04
不相交集类
2020-02-07
排序算法
2019-07-20
Spring学习 AOP
2019-08-04
Spring学习 依赖注入
繁