说说弗洛伊德算法(Floyd-Warshall)

弗洛伊德算法,是当时集训的时候学最短路问题的第一个算法(去年寒假),当时学长直说这个算法好写、时间复杂度高,至于这个算法是什么原理却没有讲。学长说,照着敲就可以,循环敲对了,就那么神奇的对了,循环顺序错了,就神奇的 WA 了。

今年寒假,我也是学长了,逗比硕把最短路这一课给我了,这一周我要给学弟学妹们讲搜索和最短路。

搜索有 BFS 和 DFS 两个算法,或者说是搜索思想,而最短路有 4 个算法。最近也重点看了搜索和最短路,翻来覆去好几遍。然后对搜索和走最短路的各个算法都有了进一步的理解,终于对这几种东西不再是仅限于会用模板了。

在与学弟的交流并解决学弟的疑问的同时,也让我看到的搜索和最短路那些只抄模板很容易忽略的地方。以及之前自己没有注意到的东西。

之前最短路的总结就写过弗洛伊德。但没有解释弗洛伊德,这篇文章主要解释弗洛伊德原理。

首先要明确,弗洛伊德是求任意两点之间的最短路。此处记录任意两点之间的距离是靠一个二维数组(示例里的 G数组)实现的。

摆出弗洛伊德的示例代码:

int fld (int n,int s,int e)
{
    int d[200][200];
    int i,j,k;
    // G 是一个存储了整张图的邻接矩阵
    memcpy(d,G,sizeof(G));

    for (k = 1;k <= n;k++)
        for (i = 1;i <= n;i++)
            for (j = 1;j <= n;j++)
                d[i][j] = qmin (d[i][j],d[i][k] + d[k][j]);

    return d[s][e];
}

然后说弗洛伊德是怎么实现的。

初始化时,有个 d数组(见上方代码),是 G 数据的一个复制,我们可以认为,这个 d 开始的时候是和 G 的含义一致即任意两个点之间相连的距离。换句话说,就是如果两个点 p1 和 p2 有相连的边,d[p1][p2] 就是一个描述两点距离的值,否则就是正无穷(这里用 int 最大值表示)。

然后进入循环,从k = 1开始,也就是从 1号点 开始,对于任意两个点做一个尝试:能不能把1号点放入他们中间。

如果说一开始 d数组 表示的是任意两点直连路径,那经过第一次循环之后,d数组 所代表的含义已经变了,现在的 d数组 可以理解为任意两点之间中间点不超过1个点的最短路径。

为什么是不超过一个点的最短路径呢?因为刚才把 1号点 尝试放入任意两个点中间,如果发现放入就会更新最短路,那么便会更新 d数组。换句话说,如果 A 到 B 的距离大于 A 到 C 然后到 B 的距离,那么这个 C 点就可以放入最短路。与此相同,如果有的可以放入 1号点,有的放入对最短路没有改善,那么 d 数组就是存储的任意两个点之间不超过1个点的最短路。

然后循环继续 k=2,那么,又开始在任意两个点之间尝试把 2号点 放入最短路中,依然是部分可以优化最短路,部分不可以。而且经过第一次循环之后,d数组 是任意两点中间点不超过 1 个点的最短路。而尝试把 2号点 放入则会让 d数组 变成任意两个点的中间点不超过 2 个点的最短路。

以此类推,把所有点循环完后,就认为 d数组 是存储的任意两个点之间中间点不超过 n 个点的最短路,实际上,这时候的 d 已经是站在全局上考虑的解了,而且对于一个 n 个点的图来说,他的最短路的中间点一定小于 n,那么我们就认为,这时候的任意两个点的最短路实际上就是 d数组 所描述的解。

算法的魅力不在于用这个算法A掉了一个或更多的题目,而是这个算法本身!

2015/02/01 13:02 下午 posted in  算法&数据结构

再说并查集

上一次写并查集是在看《数据结构》的时候写了树模型的拓展,当时那一章讲到了并查集,并提出了基本的思想。

并查集是我在第一次寒假集训学到的,当时学完写了总结月球美容计划之并查集

今天在看生成树的时候,图论那本书又讲到了并查集。

经过各种资料的查阅,确定并查集并没有特别深入的应用,并查集只不过就是一种判断集合属性的方法,说白了,就是有若干种关系,判断谁和谁是同一种关系。

并查集算法是由3个函数组成的,就三个函数:

初始化函数

根据初始化的不同,并查集有两种写法,这两种写法没有优劣差异,就是初始化不同而已。

初始化为-1

int bc[100];

int UFset1()
{
    for(int i = 0;i < 100;i++)
        bc[i] = -1;
}

初始化为-1是《数据结构》和《图论》都采取的方法,但我学的时候是使用的第二种初始化

初始化为下标

int UFset2()
{
    for(int i = 0;i < 100;i++)
        bc[i] = i;
}

初始化的不同,在剩下两个函数直接造成细节上的差异,但是并没有造成时间复杂度和空间复杂度的差异。

查找函数

查找函数便是用来查找任一元素的根结点(祖先),而在并查集算法中,唯一的优化便是对查找函数的优化。

未优化的查找函数

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    return r;
}

因为并查集数组bc[],存储的是当前结点的父结点,溯流而上,就能找到根结点,找到之后便返回根结点。

对查找函数的优化

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

因为bc数组是记录前驱(父结点)的一棵多叉树,那么如果存在最坏情况(整棵树是线形存在),那么每次查找将最高消耗O(n),也就是说,如果树的深度越低,那么,查找效率越高。因此对其优化、压缩路径。

合并函数

我们可以用查找函数来判断是非属于同一个集合,用合并函数来把两个集合合并成一个集合。

对于合并集合,函数,初始化成什么对其没有影响。

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    bc[fa] = fb;
}

 进一步优化

在图论这本书了提到了一个灰常奇妙的优化。

原理很简单,这个并查集浪费时间在查找上,因为如果树长的很奇葩(线形),那么查找时间将灰常壮观,因此,在查找函数中对其压缩路径,来解决这个问题,那么压缩完路径之后,深度不超过3,那么,查找的时间复杂度解决了,但是还有一个东西浪费时间,就是压缩路径本身。

这样想,如果我们在建树的过程中就尽量让树平衡(相关概念参考:数据结构之二叉树),那么在压缩路径的时候,也会节省一些时间。

至于怎么实现,书中给出的解决方案是靠根结点来记录这个根结点下有多少子节点。

首现,要选择初始化为-1的那种方案,然后对查找进行修改

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (bc[r] >= 0)  //在这里修改了,
        r = bc[r];      //因为如果是根结点,其值为负数而不仅为-1

    while (r != bc[a])  //优化,压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

然后对合并函数进行修改:

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    int tmp = bc[fa] + bc[fb];  //结点个数、负数

    if(bc[fa] > bc[fb])    //加权法则
    {
        bc[fa] = fb;
        bc[fb] = tmp;
    }else
    {
        bc[fb] = fa;
        bc[fa] = tmp;
    }
}
2015/01/22 13:00 下午 posted in  算法&数据结构

深度优先搜索(DFS)的奇偶剪枝

今天进行到DFS&&BFS&&活动网络问题。BFS和DFS可以解决很多有趣的问题,而BFS和DFS本身就有很多优化、变形。对于对于优化最常见的莫过于剪枝了,而对于搜索剪枝,最常见的也就是奇偶剪枝。

对于DFS,详情见数据结构之图的遍历

对于DFS剪枝,那ZOJ2110作为例子:Tempter of the Bone

先看没有剪枝和剪枝之后的效果:

为什么剪枝

因为DFS和BFS可以是认为树形搜索的。因此,他们的搜索轨迹可以生成出深度优先生成树和广度优先生成树,详情见: 图的连通性

如果我们在生成树的过程中(就是查找过程中),发现并确定一个分支不可能找到解,那么我们就把这个分支剪掉,以节省时间。这就是剪枝。

奇偶剪枝

首先我们要知道一个前提:

奇数 + 偶数 = 奇数
偶数 + 偶数 = 偶数

那么,也就可以推出:

偶数 = 奇数 - 奇数

偶数 = 偶数 - 偶数

假设有这么一个地图:

我们可以发现一个规律,从其中任意一个0到任意一个0需要偶数步,而其中任意一个1到任意一个0需要奇数步。

如果我们每一步的消耗时间是相同的,那么,需要用时和最短的步数必须需要同奇偶才能到达,否者不会到达。

为了方便描述,我们假设我们在(sx,sy)的位置,需要消耗t时到达(ex,ey)。

那么不管我们怎么绕圈,如果 t-[abs(ex-sx)+abs(ey-sy)] 结果为非偶数(奇数),则无法在t步恰好到达。

因此,这样我们就可以在搜索过程中,实时判断现在剩下的时间和现在位置到目的地最短距离是否同奇偶,如果不是,那么就没有必要搜索下去了。

骨头问题

再回到ZOJ2110,这个题用到了奇偶剪枝,并且还有一种搜索前优化,就是如果所有狗狗能走的位置(所有的地图位置的个数减去障碍物的个数)小于规定时间,直接打印NO(就是狗狗根本跑不开,就不用搜索了)。

代码:

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

char mp[10][10];
int bj[10][10];
int chx[] = {0,1,0,-1};
int chy[] = {1,0,-1,0};
int n,m,t;
int ex,ey;
int tf;

void dfs(int x,int y,int tim)
{
    if(x < 0 || y < 0 || x >= n || y >= m)
        return ;

    if(tim == t && x == ex && y == ey)
    {
        cout << "YES" << endl;
        tf = 1;
        return ;
    }

    int tmp = (t - tim) - fabs(x - ex) - fabs(y - ey);

    if(tmp < 0 || tmp % 2)
        return ;

    for(int i = 0; i < 4;i++)
    {
        if(mp[x + chx[i]][y + chy[i]] != 'X')
        {
            mp[x + chx[i]][y + chy[i]] = 'X';
            dfs(x + chx[i],y + chy[i],tim + 1);
            if(tf)
                return ;
            mp[x + chx[i]][y + chy[i]] = '.';
        }
    }
}

int main()
{
    while(cin >> n >> m >> t,n)
    {
        tf = 0;
        memset(bj,-1,sizeof(bj));
        for(int i = 0;i < n;i++)
            cin >> mp[i];

        int x,y;

        for(int i = 0;i < n;i++)
        {
            int j;
            for(j = 0;j < m;j++)
                if(mp[i][j] == 'S')
                {
                    x = i;
                    y = j;
                    break;
                }
            if(j < m)
                break;
        }

        for(int i = 0;i < n;i++)
        {
            int j;
            for(j = 0;j < m;j++)
                if(mp[i][j] == 'D')
                {
                    ex = i;
                    ey = j;
                    break;
                }
            if(j < m)
                break;
        }

        mp[x][y] = 'X';
        dfs(x,y,0);

        if(!tf)
            cout << "NO" << endl;
    }
    return 0;
}
2015/01/21 12:57 下午 posted in  算法&数据结构

可图和Havel-Hakimi定理

可图(Graphic)

什么是可图,那需要先说一下度序列。

度序列是把图的多有顶点度数排列成一个序列s,则称s为图G的度序列。

度序列可以是按照顶点的顺序排列,也可以按照递增、递减的顺序排列。所谓的可图,是建立在度序列的基础上的。

序列是可图的:一个非负整数组成的有限序列如果是某个无向图的度序列,则称这个序列是可图的。

说白了,就是如果一串度序列可以逆向生成出图,就是可图的。而判断一个序列是否是可图的,则由Havel-Hakimi定理判断。

Havel-Hakimi定理

由非负整数组成的非增序列s:d1,d2,...,dn(n>=2,d1>=1)是可图的,当且仅当序列:

s1:d2 - 1,d3 - 1,...,dd1+1 - 1,dd1+2,...,dn

是可图的。序列s1中有n-1个非负整数,s序列中d1后的前d1个度数(即d2~dd1+1)减1后构成s1中的前d1个数。

说白了就是先把第一个点(度数为d1)连线到后面d1个点,保证第一个点度数满足,然后再以此类推考虑后面的点。如果后面所有顶点满足并且度数不多不少(最后不剩,过程中没有度数为负数),即可认为,度序列是可图的。

青蛙邻居问题

POJ1659 Frogs' Neighborhood

Description

未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ iN)。如果湖泊LiLj之间有水路相连,则青蛙FiFj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ...,xn,请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行,第一行是整数N(2 1, x2,..., xn(0 ≤ xiN)。

Output

对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int G[20][20];
struct Node
{
    int dnum;
    int no;
}d[20];

int cmp(Node a,Node b)
{
    return a.dnum > b.dnum;
}

int main()
{
    int N;
    cin >> N;

    while(N--)
    {
        bool flag = 1;
        memset(G,0,sizeof(G));

        int n;
        cin >> n;

        for(int i = 0;i < n;i++)
        {
            cin >> d[i].dnum;
            d[i].no = i;
        }

        for(int i = 0;i < n;i++)
        {
            sort(&d[i],&d[i] + n - i,cmp);
            int last = d[i].dnum;
            d[i].dnum = 0;
            if(last > n - i)
            {
                flag = 0;
                break;
            }

            for(int j = i + 1;j <= i + last;j++)
            {
                if(d[j].dnum - 1 >= 0)
                {
                    G[d[i].no][d[j].no] = 1;
                    G[d[j].no][d[i].no] = 1;
                    d[j].dnum -= 1;
                }else
                {
                    flag = 0;
                }
                if(!flag)
                    break;
            }
            if(!flag)
                break;
        }

        if(flag)
        {
            for(int i = 0;i < n;i++)
                if(d[i].dnum > 0)
                    flag = 0;
        }

        if(!flag)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;

            for(int i = 0;i < n;i++)
                for(int j = 0;j < n;j++)
                    cout << G[i][j] << (j < n - 1 ? ' ' : 'n');
        }

        if(N)
            cout << endl;
    }
    return 0;
}

 注意

这个题目是Special Judge,也就是说这个题的答案是有多种的。这个是由Havel-Hakimi定理导致的,由于可图是由度数重构图,这个过程构建的图可能不是唯一的

2015/01/20 12:56 下午 posted in  算法&数据结构

关键路径

AOE网

与AOV网相对应的是AOE网,即边表示活动的网。AOE网是一个带权的有向无环图,其中,定点表示事件,弧表示活动,权表示活动持续的时间。通常,AOE网可以用来估算工程的完成时间。

关键路径

设一个工程有11项活动,9个事件,事件 V1表示整个工程开始,事件V9——表示整个工程结束,问题:

  • 完成整项工程至少需要多少时间?
  • 哪些活动是影响工程进度的关键?

关键路径的几个术语

  • 路径长度:路径上各活动持续时间之和。
  • 关键路径:路径长度最长的路径。
  • 关键活动:关键路径上的活动,即这些活动的时间延迟或提前会影 响整个工程工期的延迟或提前。

我们可以说,我们可以对一个工程计划,先从头开始保证每个任务尽快完成,那么就可以计算出每个点的最短完成时间。

如果我们从尾开始,以尾的最快完成时间为期限,再逆推每个点最迟完成时间且保证不耽误尾节点的完成,那么就可以计算出每个点的最晚完成时间。

那么一个节点完成时间是在最早完成时间到最晚完成时间的区间内则不会影响整个工程的进度,如果一个节点最早完成时间和最晚完成时间相同,就意味着,如果这个节点延误了,整个工程将被延误。那么,这就是关键活动

换句话,如果找到关键活动,如果加快关键活动的完成,整个工程将更快完成。

Ve(j):表示事件Vj的最早发生时间。

Vl(j):表示事件Vj的最迟发生时间。

e(i):表示活动ai的最早开始时间。

l(i):表示活动ai的最迟开始时间。

l(i)-e(i):表示完成活动ai的时间余量。

若时间余量为0,则该活动为关键活动,所在的路径为关键路径。

设活动ai用弧表示,其持续时间记为:dut() 则有:

  • e(i)=Ve(j)
  • l(i)=Vl(k)-dut()

求Ve(j)和Vl(j)需分两步进行:

  1. 从Ve(0)=0开始向前推进:Ve(j)=Max{Ve(i) + dut()(每条指向j的边)}
  2. 从Vl(n-1)=Ve(n-1)起向后推进:Vl(i)=Min{Vl(j)-dut()(每条指向j的边)}

这样,就能找到每个关键活动。

因此,可以提炼算法:

  1. 输入e条弧建立AOE网的存储结构
  2. 从源点v0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中各顶点数n,则说明网中存在环,不能求关键路径,算法终止,否者执行第3步
  3. 从汇点vn出发,令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]
  4. 根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足e(s)=l(s),则为关键活动

伪代码:

Status TopologicalOrder(ALGraph G, Stack &T) {
  // 有向网G采用邻接表存储结构,求各顶点事件的最早发生时间ve(全局变量)。
  // T为拓扑序列定点栈,S为零入度顶点栈。
  // 若G无回路,则用栈T返回G的一个拓扑序列,且函数值为OK,否则为ERROR。
  Stack S;int count=0,k;
  char indegree[40];
  ArcNode *p;
  InitStack(S);
  FindInDegree(G, indegree);  // 对各顶点求入度indegree[0..vernum-1]
  for (int j=0; jnextarc) {
      k = p->adjvex;            // 对j号顶点的每个邻接点的入度减1
      if (--indegree[k] == 0) Push(S, k);   // 若入度减为0,则入栈
      if (ve[j]+p->info > ve[k])  ve[k] = ve[j]+p->info;
    }//for  *(p->info)=dut()
  }//while
  if (countnextarc) {
      k=p->adjvex;  dut=p->info;     //dut
      if (vl[k]-dut nextarc) {
      k=p->adjvex;dut=p->info;
      ee = ve[j];  el = vl[k]-dut;
      tag = (ee==el) ? '*' : ' ';
      printf(j, k, dut, ee, el, tag);   // 输出关键活动
    }
  return OK;
} // CriticalPath

 关键路径分析

  • 求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;
  • 只有缩短关键活动的工期才有可能缩短工期;
  • 关键路径可能不只一条,要同时提高所有的关键路径,才能缩短整个工期;
  • 若一个关键活动不在所有的关键路径上,减少它并不能减少工期;
  • 只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。
2014/12/23 12:54 下午 posted in  算法&数据结构