Skip to content

Instantly share code, notes, and snippets.

@dreamer2q
Last active May 9, 2020 14:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dreamer2q/075a594a7500867b5b14bcda782e282a to your computer and use it in GitHub Desktop.
Save dreamer2q/075a594a7500867b5b14bcda782e282a to your computer and use it in GitHub Desktop.
Data structure study and write up

搜索算法

宽度优先搜索(BFS)

  • 介绍

宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra 单源最短路径算法和 Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

  • 遍历二叉树

一颗完全二叉树

//伪代码

bfs(){
   queue<int> q;
   //从根节点开始搜索
   q.push(Start);
   while(!q.Empty()){
       //从队列头部弹出一个元素
       ele = q.front();
       q.top();
       //输出元素
       //print ele
       //有左节点,就加入到队列中,右节点同理
       if(q.left != NULL){
           q.push(q.left);
       }
       if(q.right != NULL){
           q.push(q.right);
       }
   }
}
  • 遍历图

图的遍历

//TODO
  • 更一般的搜索

这一点我们和遍历二叉树的时候进行对比可以发现,二叉树每遍历一个节点最多可以在遍历下一层的时候产生两个子节点, 而对于普适情况是,我们每遍历一个节点,可以产生任意个子节点个数,这也是我们需要一个队列的原因。

更进一步,如果我们维护一个优先队列,可能更有效的寻找到答案。

//伪代码描述
    创建一个队列q
    根节点入队
    while q不为空 {
        取出一个元素elem

        对元素elem进行处理

        while elem有子节点p {
            if 需要剪子p {
                continue
            }
            将p加入到队列q中
        }
    }

实际应用的注意事项

  • 去重(修枝)

状态转移的时候可能转移到之前的状态,这样就形成了一个环,我们需要一个容器来保存已经搜索过的状态,这样我们可以把这一个节点的枝叶全部去掉。

深度搜索优先

搜索

在我们遇到的一些问题当中,有些问题我们不能够确切的找出数学模型,即找不出一种直接求解的方法,解决这一类问题,我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探,按照一定的顺序、规则,不断去试探,直到找到问题的解,试完了也没有找到解,那就是无解,试探时一定要试探完所有的情况(实际上就是穷举)

  • 对于问题的第一个状态,叫初始状态,要求的状态叫目标状态。
  • 搜索就是把规则应用于实始状态,在其产生的状态中,直到得到一个目标状态为止。
  • 产生新的状态的过程叫扩展(由一个状态,应用规则,产生新状态的过程)

要点

  • (1)初始状态
  • (2)重复产生新状态
  • (3)检查新状态是否为目标,是结束,否转(2)

区分

  • 如果搜索是以接近起始状态的程序依次扩展状态的,叫宽度优先搜索。
  • 如果扩展是首先扩展新产生的状态,则叫深度优先搜索。

深度搜索优先(DFS)

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过,搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

思路

深度优先搜索用一个数组存放产生的所有状态。

  • (1) 把初始状态放入数组中,设为当前状态;
  • (2) 扩展当前的状态,产生一个新的状态放入数组中,同时把新产生的状态设为当前状态;
  • (3) 判断当前状态是否和前面的重复,如果重复则回到上一个状态,产生它的另一状态;
  • (4) 判断当前状态是否为目标状态,如果是目标,则找到一个解答,结束算法。
  • (5) 如果数组为空,说明无解。

伪代码

  1. 首先将根节点放入stack中。

  2. stack中取出第一个节点,并检验它是否为目标。

    • 如果找到目标,则结束搜寻并回传结果。
    • 否则将它某一个尚未检验过的直接子节点加入stack中。
  3. 重复步骤 2。

  4. 如果不存在未检测过的直接子节点。

    • 将上一级节点加入stack中。
    • 重复步骤 2。
  5. 重复步骤 4。

    • stack为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

示例

  • 输入一个正整数 n,请按照字典序输出 1-n 的全排列,每个排列输出一行,每个数字后面跟一个空格
#include <bits/stdc++.h>
using namespace std;

int n;
int num[10],vis[10];
void dfs(int step);

int main(){
     while(scanf("%d",&n)==1){
	    memset(vis,0,sizeof(vis));
	    dfs(1);
     }
     return 0;
}

void dfs(int step){ //思考:参数step的含义是?
        if(step == n+1){
               for(int i = 1; i <= n; i++)
                        printf("%d ", num[i]);
                printf("\n");
                return;
        }
        for(int i = 1; i <= n; i++){
                if(vis[i] == 0){
                        num[step] = i;
                        vis[i] = 1;
                        dfs(step+1);
                        // 思考:下面一句如果注销会是什么结果?
                        vis[i] = 0; //回溯,难点
                }
        }
}
//思考:如果是求任意n个数的全排列,怎么办?

应用

//todo

Disjoint Set 并查集

Description

将编号分别为 1…N 的 N 个对象划分为不相交集合, 在每个集合中,选择其中某个元素代表所在集合。

ADT

  • 初始化(MakeSet)
  • 合并(Merge)
  • 查找(Find)

Implementation

Method 1

  • 用编号最小的元素标记所在集合
  • 定义一个数组set[1..n],其中set[i]表示元素i所在的集合
#define N 100
int set[N];
int find(int x){
    return set[x];
}
void merge(int a,int b){
    int i=a,j=b;
    if(a>b) i=b,j=a;
    for(int z=1;z<=N;z++){
        if(set[z] == j)
            set[z] = i;
    }
}

这里的查找操作是非常快速的,但是合并操作需要遍历所有的元素,效率不高。

Method 2

  • 每个集合用一颗有根树表示
  • 定义数组set[1..n]
    • set[i] == i, 则 i 表示本集合,并是集合对于的根
    • set[i] != ji!=j, 则表示ji的父节点
#define N 100
int set[N];
int find(int x){
    int r=x;
    while(set[r] != r)
        r = set[r];
}
void merge(int a,int b){
    set[a] = b;
}

这里注意,虽然合并的操作效率很高,但是查找的最坏情况是O(N)

Optimization

  • 避免最坏的情况
    • 将深度小的树合并到深度大的树
    • 假设两个两棵树的深度分别是h1,h2,则合并后高的h
      • max(h1,h2) # h1 != h2
      • h1+1 # h1 == h2
    • 包含k个节点的树,最大高度不超过lgk
int find(int x){
    int r = x;
    while(set[r] != r)
        r = set[r];
    return r;
}
void merge(int a,int b){
    if(H(a) == H(b)){
        H(a)++;
        set[b] = a;
    }else if(H(a) < H(b)){
        set[a] = b;
    }else{
        set[b] = a;
    }
}
  • 路径压缩
    • 每次查找的时候,如果路径较长,则修改路径信息,以便下次查找的时候速度更快
    • 找到根节点,修改查找路径上的所有节点,将它们都指向根节点
int find(int x){
    int r = x;
    while(set[r]!=r) //寻找根节点
        r = set[r];

    int i = x;
    while(i != r){  //修改路径所有节点信息
        int j = set[i];
        set[i] = r;
        i = j;
    }
    return r;
}

Application

  • 最小生成树

组合博弈入门

简单取子游戏 (组合游戏一种)

  • 组合游戏

    1. 有两个玩家

    2. 游戏的操作状态是一个有限的集合(比如:限定大小的棋盘)

    3. 游戏双方轮流操作

    4. 双方的每次操作必须符合游戏规定

    5. 当一方不能将游戏继续进行的时候,游戏结束,同时,对方为获胜方

    6. 无论如何操作,游戏总能在有限次操作后结束

概念

  • 必败点(P 点): 前一个选手(Previous player)将取胜的位置称为必败点。

  • 必胜点(N 点): 下一个选手(Next player)将取胜的位置称为必胜点。

属性

  • (1) 所有终结点是必败点(P 点)

  • (2) 从任何必胜点(N 点)操作,至少有一种方法可以进入必败点(P 点)

  • (3) 无论如何操作, 从必败点(P 点)都只能进入必胜点(N 点)

算法实现(自然语言)

  1. 将所有终结位置标记为必败点(P 点)

  2. 将所有一步操作能进入必败点(P 点)的位置标记为必胜点(N 点)

  3. 如果从某个点开始的所有一步操作都只能进入必胜点(N 点) ,则将该点标记为必败点(P 点)

  4. 如果在步骤 3 未能找到新的必败(P 点),则算法终止;否则,返回到步骤 2。

示例

  • 取子游戏: S = {1, 3, 4}
剩余 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
状态 P N P N N N N P N P N N N N P

Nim 游戏

简介

  • 有两个玩家
  • 有三堆扑克牌(比如:分别是 5, 7, 9 张)
  • 游戏双方轮流操作
  • 玩家的每次操作是选择其中某一堆牌,然后从中取走任意张
  • 最后一次取牌的一方为获胜方

nim-sum

nim-sum定义

定理

对于 nim 游戏的某个位置(x1,x2,x3),当且仅当它各部分的 nim-sum 等于 0 时(即 x1⊕x2⊕x3=0),则当前位于必败点。

Graph Games & Sprague-Grundy Function

nim-game的状态转移图

SG 函数

sg

也就是说,X 节点的 SG 值是去除 X 的后继节点的 SG 值后的最小的非负整数

sg应用

SG 示例

若 S={1,2,3} (S 代表,每次能取数的集合),请计算简单取子游戏的 SG 值

SG计算

组合游戏的并

有时,一个游戏可以有多个小的游戏组成,这时SG函数仍然适用。

SG计算

SG 函数的实现

int k,a[100],f[10001];

//这里使用递归,还可以优化
int sg(int p){//p是所求节点
    int i,t;
    bool g[101]={0};
    for(i=0;i<k;i++){
        t=p-a[i]; //这里要求a已经是升序
        if(t<0)
            break;
        if(f[t]==-1)  //f需要初始化为-1
            f[t]=sg(t);
        g[f[t]]=1;
    }
    for(i=0;;i++){//从0开始寻找最小的满足值即为SG函数值
        if(!g[i])
            return i;
    }
}

TODO 优化 SG 函数

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment