精华内容
下载资源
问答
  • 算法】分治法所能解决问题的特征总结
    千次阅读
    2020-08-18 15:45:07

    分治法的设计思想:

    将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。**

    任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排。n=2时,只要作一次比较即可排好序。n=3时序问题,当n=1时,不需任何计算只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

    分治法所能解决的问题一般具有以下几个特征:

    1.可缩性。问题的规模缩小到一定的程度就可以容易地解决;

    2.最有子结构性。问题可以分解为若干个规模较小的相同问题;

    3.可合性。利用该问题分解出的子问题的解可以合并为该问题的解;

    4.独立性。该问题所分解出的各个子问题是相互独立的,即子问 题之间不包含公共的子子问题。## 标题

    分治思想与递归就像一对孪生兄弟,经常同时应用在算法设计中,并由此产生高效的算法!


    设计递归的思路

    最小子结构
    子结构
    最小子结构与子结构之间的关系

    寻找这三个问题的答案时,可以先手算前几个情况的答案,然后找规律。
    如果能回答上来这三个问题,题目便迎刃而解了


    什么时候考虑递归

    具有以下特征的问题可考虑递归求解:

    当问题和子问题具有递推关系,比如杨辉三角、计算阶乘(后文讨论)。
    具有递归性质的数据结构,比如链表、树、图。
    反向性问题,比如取反。
    总结下来,最根本的还是要抓住问题本身是否可以通过层层拆解到最小粒度来得解。
    若有兴趣,请点击->递归的详细解释


    头递归与尾递归

    通过下面的例子来体会头递归与尾递归的区别

    //#incldue<链表定义>                 偷懒:)
    void print1(LinkList L){
        if(L==NULL) return;
        print1(L->next);  //先递归到链表最尾部 再逆序输出
        printf("%d ",L->data);
        //输出结果 10 9 8 7 6 5 4 3 2 1
    }
    void print1(LinkList L){
        if(L==NULL) return;
        printf("%d ",L->data);
        print1(L->next);  //输出一个值后 再向下递归
        //输出结果 10 9 8 7 6 5 4 3 2 1
    }
    

    for循环内嵌递归

    递归的思路是:
    (1)存在一个问题
    (2)这个问题可以通过分解形成一个小一点的相同的问题
    (3)小一点的问题继续可以分解成更小的问题
    (4)最后得出一个最小的问题,最小问题不是问题
    例如:计算n的排列的问题,我们可以将它分解成计算(n−1)!,(n−1)!继续分解(n−1−1)!
    最后必定会得出一个最小的问题:0!
    而for循环嵌套递归用于
    当问题不只一个时,就是说存在一个大的问题,里面有N个同等的中问题,而这N个同等的中问题都可以按递归思路解题,这时候就需要用for来将N个问题遍历了。、

    为什么for堪套递归的次数是2的n次方?那是因为每一次for都需要调用两次函数,其中for执行一次,for调用递归又需要再执行一次,又根据乘法定理:如果一个过程分成两个阶段,第一阶段有m种可能的结果,并且对于这个阶段的结果,第二阶段都有n种可能的结果,则按指定的次数序完成整个过程一共有mn种方法。这样就可以得出2的n次方。
    //递归调用完,for循环还要继续调用,假设for循环n次,递归执行m次,则一共要调用nm次!
    //也就是说,每for循环一次,要调用所有的递归一遍;for循环n次,要调用所有的递归n遍。而如果所有的递归有m次,则总共就是n*m次

    一个例子分析下执行过程
    for嵌套递归生成树:

    #include<stdio.h>
    #include<iostream>
    using namespace std;
    void rec(int n){
        if(n==2) return;
        for(int i=1;i<=2;i++){        
            cout<<i<<" "; rec(n+1);
        }
    }
    int main(){
        rec(0);
        return 0;
    }
    

    运行结果:
    在这里插入图片描述
    运行结果分析:
    在这里插入图片描述

    例子:
    求全排列问题
    代码:

    #include<iostream>
    using namespace std;
    const int N=10;
    int n;
    int path[N];
    bool st[N];
    void dfs(int u){
        if(u==n){
            for(int i=0;i<n;i++)
                printf("%d",path[i]);
            puts("");
            return;
        }
        for(int i=1;i<=n;i++){
            if(!st[i]){
                path[u]=i;
                st[i]=true;
                dfs(u+1);
                st[i]=false;
            }
        }
    }
    int main(){
        cin>>n;
        dfs(0);
        return 0;
    }
    

    在这里插入图片描述


    例题

    FJ的字符串串.
    通过这个题目,我们可以发现最小的子问题是A1,子问题与最小子问题的递推关系如图。这个问题便迎刃而解。在这里插入图片描述

    汉诺塔求最少移动次数
    移动3个盘子的过程:
    A → C
    A → B
    C → B
    A → C
    B → A
    B → C
    A → C
    总共移动了7次

    解析:
    1个圆盘的时候 2的1次方减1     2个圆盘的时候 2的2次方减1
    3个圆盘的时候 2的3次方减1     4个圆盘的时候 2的4次方减1
    5个圆盘的时候 2的5次方减1
    …………
    n个圆盘的时候 2的n次方减1!

    nclude<stdio.h>
    int h(int m)
    {
    	int s;
    	if(m==1)      // 确定初始条件
    		s=1;
    	else
    		s=2*h(m-1)+1;
    	return s;
    }
    int main()
    {   
    	int n;
    	scanf("%d",&n);
    	printf("%ld",h(n));
    }
    

    更多练习

    递归的十个例子(带详尽输入输出)

    更多相关内容
  • 宽度优先搜索算法解决八数码问题

    万次阅读 多人点赞 2020-05-19 23:44:41
    宽度优先搜索算法解决八数码问题 实验原理 1、宽度优先搜索是指在一个搜索树中,搜索以同层邻近节点依次扩展节点。这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。 宽度优先...

    宽度优先搜索算法解决八数码问题

    原理

    1、宽度优先搜索是指在一个搜索树中,搜索以同层邻近节点依次扩展节点。这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。
    宽度优先搜索算法主要步骤可描述如下:
    ①令N为一个由初始状态构成的表。
    ②若N为空退出,标志失败。
    ③令n为N中第一个节点,将n从N中删除。
    ④若n是目标,则退出,标志成功。
    ⑤若n不是目标,将n的后继节点加入到N表的末端,转第②步。

    宽度优先搜索算法流程图下图所示:
    在这里插入图片描述
    2、八数码问题知识表示方法(状态空间法)分析:
    1.定义状态空间:根据八数码问题定义出状态空间。然后通过对象给出问题的初始状态、目标状态,给出状态的一般表示。
    2.定义操作规则:规定一组算子,作用于一个状态后过渡到另一个状态。
    3.定义搜索策略:使用宽度优先搜索,使得能够从初始状态出发,沿某个路径达到目标状态。搜索过程为:沿着4个方向,如果可行都前进一步看是否达到位置。如果没有达到,则依次从新的位置为起点,沿4个方向继续前进一步,直到搜索到目标位置或者找不到未搜索的位置为止。

    3、八数码问题判断有无解
    对于棋子数列中任何一个棋子c[i],如果有j>i且c[j]<c[i],那么 c[j]是c[i]的一个逆序,或者c i]和c[j]构成一个逆序对。定义棋子c[i]的逆序数为c[i]的逆序个数;棋子数列的逆序数为该数列所有棋子的逆序数总和。
    定理:如果棋子数列经过n次相邻棋子交换后,若n为偶数,则数列逆序数奇偶性不变;若n为奇数,则数列逆序数将发生奇偶性互变。
    推广:
    (1)当初始状态棋局的棋子数列的逆序数是奇数时,八数码问题无解;
    (2)当初始状态棋局的棋子数列的逆序数是偶数时,八数码问题有解。

    设计思路

    1、设计状态空间表示方式
    空格定义为0,将数字按行存入列表中,用列表sample存储八数码问题的初始状态,例如[2,8,3,1,6,4,7,0,5];用goal存储八数码问题的目标状态,例如[1,2,3,8,0,4,7,6,5],八数码问题中数字的移动就看做是空格(0)的移动,在列表中直接完成,同时把操作记录存储在列表的末端,如第一步空格向上移动,则移动后的列表变为[2,8,3,1,0,4,7,6,5,‘up’]。
    初始节点为[2,8,3,1,6,4,7,0,5],它是搜索树的根节点,而目标状态为[1,2,3,8,0,4,7,6,5],我们做的,就是找出一条或者多条从根节点通往[1,2,3,8,0,4,7,6,5]节点的路径。

    2、设计一组算子
    用来求解该问题的算子可以用4条规则来描述
    ①空格(0)向上移动(注意:要满足前提条件,即空格移动方向有数字且移动后的状态为初次生成状态,以下规则也一样)
    ②空格(0)向下移动
    ③空格(0)向左移动
    ④空格(0)向右移动
    这四条规则,事实上就是搜索树上从当前节点生成下一个节点的方法。

    3、移动方法以及可移动的条件
    向上移动和向下移动:假设初始状态 在这里插入图片描述 中,0(空格)所在的位置为中心,存储为[2,8,3,1,0,4,7,6,5]。0所在位置的下标为4,若0要向上移动或向下移动,则实质为与8或6交换位置,则交换操作为:

    temp[flag], temp[flag - 3] = temp[flag - 3], temp[flag](向上移动)
    temp[flag], temp[flag + 3] = temp[flag + 3], temp[flag](向下移动)
    

    若0所在的位置已经在边界,即无法向上或向下移动,则判断条件为:

    flag - 3 >= 0(向上) 
    flag + 3 <= 8(向下)
    

    向左移动和向右移动:假设初始状态如上面相同,0所在的位置为中心,存储为[2,8,3,1,0,4,7,6,5],若0要向左向右移动,则实质为与1或4交换位置,交换操作为:

    temp[flag], temp[flag - 1] = temp[flag - 1], temp[flag](向左移动)
    temp[flag], temp[flag + 1] = temp[flag + 1], temp[flag](向右移动)
    

    若0已经在边界,即无法向左或向右移动,则判断条件为:

    flag % 3 != 0(向左) 
    (flag + 1) % 3 != 0(向右)
    

    4、判断有无解实现方法
    通过双重循环,将列表逆序循环,逐一比较,计算逆序对的个数,遇到0则跳过。最后判断奇偶,偶数有解,奇数无解。

    5、宽度优先搜索实现方法
    ①把起始节点放到OPEN表中,如果该起始节点为一目标节点,则求得一个解答。
    ②若OPEN是空表,则没有解,失败退出;否则继续。
    ③把第一个节点(节点死)从OPEN表移出,并把它放入CLOSED的扩展节点表中。
    ④扩展n。如果没有后继节点,则转向步骤②。
    ⑤把n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。
    ⑥如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向步骤②;

    完整代码:

    import time
    class QNode(object):#定义队列的数据结构
        def __init__(self, elem, next=None):
            self.elem = elem
            self.next = next
    
    class Queue(object):  # 队列
        def __init__(self):
            self.head = None
            self.rear = None
    
        def is_empty(self):#判断队列是否为空
            return self.head is None
    
        def enqueue(self, elem):  # 往队列中添加一个elem元素
            p = QNode(elem)
            if self.is_empty():
                self.head = p
                self.rear = p
            else:
                self.rear.next = p
                self.rear = p
    
        def dequeue(self):  # 从队列的头部删除一个元素
            result = self.head.elem
            self.head = self.head.next
            return result
    
        def Search(self,elem):#搜索队列中是否有与elem相同的元素
            temp = self.head
            while temp is not None:
                if elem[:9] == temp.elem[:9]:
                    return False
                temp = temp.next
            return True
    
    def jugde(open,closed,temp,i,creatpoint):#判断是否重复
        if open.Search(temp) and closed.Search(temp):
            temp.append(operato[i])
            Open.enqueue(temp)
            creatpoint += 1
        return creatpoint
    
    def  Jugde(sample):#判断有无解
        flag = 0
        for i in sample[::-1]:
            if i != '0':
                this = sample.index(i)
                for x in sample[:this]:
                    if x > i:
                        flag += 1
        if flag % 2 ==0 :
            return 0
        return 1
    
    if __name__ == '__main__':
        sample = list(input('请输入初始状态:').split())#存储8数码问题的初始状态
        goal = list(input('请输入目标状态:').split(' '))#存储8数码问题的目标状态
        m = Jugde(sample)
        n = Jugde(goal)
        if m != n:#通过求逆序数判断有无解
            print('无解!')
            exit()
        operato = ['up','down','left','right']
        k = creatpoint = 0 # k 为搜索的节点数 creatpoint 为生成节点数
        Open = Queue()#创建open表
        Closed = Queue()#创建closed表
        Open.enqueue(sample)
        Max = input("请输入最大搜索深度:")
        start = time.time()
        while(1):
            if(sample == goal ):
                print("起始节点为目标结点!")
                break
            if Open.is_empty():
                print("没有解!")
                break
            else:
                p = Open.dequeue()#从Open表中取出
                if len(p)-9 >= int(Max)+1:#判断是否超过设置的最大深度
                    print('已达最大深度,未找到解!')
                    exit()
                Closed.enqueue(p)#放入Closed表中
                if p[:9] == goal:#判断是否相等
                    k += 1
                    print('当前层次:{},已搜索节点数:{},已生成结点数{}\n查找成功!'.format(len(p)-9,k,creatpoint))
                    print("空格的移动路径依次为:",end = '')
                    for i in p[9:]:
                        print(i,end='->')
                    end = time.time()
                    print('完成\nRunning time:{} Seconds'.format(end - start))
                    exit()
                k += 1
                flag = p.index('0')# 返回列表中0的索引  flag = p.index('0')
                if flag - 3 >= 0 :#空格向上移动
                    temp = p.copy()
                    temp[flag], temp[flag - 3] = temp[flag - 3], temp[flag]
                    creatpoint = jugde(Open,Closed,temp,0,creatpoint)
                if flag + 3 <= 8:#空格向下移动
                    temp = p.copy()
                    temp[flag], temp[flag + 3] = temp[flag + 3], temp[flag]
                    creatpoint = jugde(Open, Closed, temp, 1, creatpoint)
                if flag % 3 != 0 :#空格向左移动
                    temp = p.copy()
                    temp[flag], temp[flag - 1] = temp[flag - 1], temp[flag]
                    creatpoint = jugde(Open, Closed, temp, 2, creatpoint)
                if (flag + 1) % 3 != 0:#空格向右移动
                    temp = p.copy()
                    temp[flag], temp[flag + 1] = temp[flag + 1], temp[flag]
                    creatpoint = jugde(Open, Closed, temp, 3, creatpoint)
    

    运行结果

    参数设置方案:
    初始状态:2 8 3 1 6 4 7 0 5
    目标状态:1 2 3 8 0 4 7 6 5
    最大搜索深度:10
    在这里插入图片描述

    结果讨论:

    对于一些简单的八数码问题,宽度优先算法可以比较快得找到目标,但是对于一些复杂的步数较多的问题,宽度优先搜索的的效率很低
    比如当初始状态为:[2,4 8,6,0,3,1,7,5],目标状态为:[1,2,3,8,0,4,7,6,5]的八数码问题,当最大深度设置为10时,宽度优先搜索无法找到目标状态
    在这里插入图片描述
    当设置最大深度为15时,找到了目标状态。
    在这里插入图片描述

    展开全文
  • 遗传算法解决TSP问题MATLAB实现(详细)

    万次阅读 多人点赞 2019-02-01 15:49:05
    问题定义:巡回旅行商问题 给定一组n个城市和俩俩之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。 TSP问题也称为货郎担问题,是一个古老... 近年来,有很多解决问题的较为有效...

    问题定义:巡回旅行商问题
    给定一组n个城市和俩俩之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。
    TSP问题也称为货郎担问题,是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年,由美国兰德公司推动,TSP成为近代组合优化领域的典型难题。
    TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。 近年来,有很多解决该问题的较为有效的算法不断被推出,例如Hopfield神经网络方法,模拟退火方法以及遗传算法方法等。
    TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解,对于常规方法和现有的计算工具而言,存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题,是很自然的想法。
    基本遗传算法可定义为一个8元组:
    (SGA)=(C,E,P0,M,Φ,Г,Ψ,Τ)
    C ——个体的编码方法,SGA使用固定长度二进制符号串编码方法;
    E ——个体的适应度评价函数;
    P0——初始群体;
    M ——群体大小,一般取20—100;
    Ф——选择算子,SGA使用比例算子;
    Г——交叉算子,SGA使用单点交叉算子;
    Ψ——变异算子,SGA使用基本位变异算子;
    Т——算法终止条件,一般终止进化代数为100—500;
    问题的表示
    对于一个实际的待优化问题,首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP,一个旅程很自然的表示为n个城市的排列,但基于二进制编码的交叉和变异操作不能适用。
    路径表示是表示旅程对应的基因编码的最自然,最简单的表示方法。它在编码,解码,存储过程中相对容易理解和实现。例如:旅程(5-1-7-8-9-4-6-2-3)可以直接表示为(5 1 7 8 9 4 6 2 3)
    产生初始种群
    一是完全随机产生,它适合于对问题的解无任何先验知识的情况。随机性较强,因而也较公正
    二是某些先验知识可转变为必须满足的一组要求,然后在满足这些要求的解中在随机地选取样本。这样选择初始种群可使遗传算法更快的达到最优解。种群有一定的目标性和代表性,但取例不如完全随机的广泛,而且先验知识是否可靠也是一个问题
    适应度函数
    遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。TSP的目标是路径总长度为最短,路径总长度的倒数就可以为TSP的适应度函数:
    在这里插入图片描述

    选择
    一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制,令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额fi/Σfi。
    交叉
    基于路径表示的编码方法,要求一个个体的染色体编码中不允许有重复的基因码,也就是说要满足任意一个城市必须而且只能访问一次的约束。基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件。
    部分匹配交叉操作要求随机选取两个交叉点,以便确定一个匹配段,根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体。
    在这里插入图片描述
    变异
    遗传算法解决TSP 问题基于二进值编码的变异操作不能适用,不能够由简单的变量的翻转来实现
    在TSP问题中个体的编码是一批城市的序列,随机的在这个序列抽取两个城市,然后交换他们的位置。这样就实现了个体编码的变异,算法如下:
    产生两个0到1之间的随机实数;
    将这两个随机实数转化为0到n(城市数)-1之间的随机整数;
    将这两个随机整数指代的城市进行交换;
    流程图
    在这里插入图片描述
    代码
    完整代码参考我的网站:http://www.omegaxyz.com/2019/01/21/matlab-tsp-all/

    主函数代码:

    clear;
    clc;
    tStart = tic; % 算法计时器
    %%%%%%%%%%%%自定义参数%%%%%%%%%%%%%
    [cityNum,cities] = Read('dsj1000.tsp');
    cities = cities';
    %cityNum = 100;
    maxGEN = 1000;
    popSize = 100; % 遗传算法种群大小
    crossoverProbabilty = 0.9; %交叉概率
    mutationProbabilty = 0.1; %变异概率
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    gbest = Inf;
    % 随机生成城市位置
    %cities = rand(2,cityNum) * 100;%100是最远距离
    % 计算上述生成的城市距离
    distances = calculateDistance(cities);
    % 生成种群,每个个体代表一个路径
    pop = zeros(popSize, cityNum);
    for i=1:popSize
    pop(i,:) = randperm(cityNum); 
    end
    offspring = zeros(popSize,cityNum);
    %保存每代的最小路劲便于画图
    minPathes = zeros(maxGEN,1);
    % GA算法
    for  gen=1:maxGEN
    % 计算适应度的值,即路径总距离
    [fval, sumDistance, minPath, maxPath] = fitness(distances, pop);
    % 轮盘赌选择
    tournamentSize=4; %设置大小
    for k=1:popSize
    % 选择父代进行交叉
    tourPopDistances=zeros( tournamentSize,1);
    for i=1:tournamentSize
    randomRow = randi(popSize);
    tourPopDistances(i,1) = sumDistance(randomRow,1);
    end
    % 选择最好的,即距离最小的
    parent1  = min(tourPopDistances);
    [parent1X,parent1Y] = find(sumDistance==parent1,1, 'first');
    parent1Path = pop(parent1X(1,1),:);
    for i=1:tournamentSize
    randomRow = randi(popSize);
    tourPopDistances(i,1) = sumDistance(randomRow,1);
    end
    parent2  = min(tourPopDistances);
    [parent2X,parent2Y] = find(sumDistance==parent2,1, 'first');
    parent2Path = pop(parent2X(1,1),:);
    subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉
    subPath = mutate(subPath, mutationProbabilty);%变异
    offspring(k,:) = subPath(1,:);
    minPathes(gen,1) = minPath; 
    end
    fprintf('代数:%d   最短路径:%.2fKM \n', gen,minPath);
    % 更新
    pop = offspring;
    % 画出当前状态下的最短路径
    if minPath < gbest
    gbest = minPath;
    paint(cities, pop, gbest, sumDistance,gen);
    end
    end
    figure 
    plot(minPathes, 'MarkerFaceColor', 'red','LineWidth',1);
    title('收敛曲线图(每一代的最短路径)');
    set(gca,'ytick',500:100:5000); 
    ylabel('路径长度');
    xlabel('迭代次数');
    grid on
    tEnd = toc(tStart);
    fprintf('时间:%d 分  %f 秒.\n', floor(tEnd/60), rem(tEnd,60));
    

    完整代码参考我的网站:http://www.omegaxyz.com/2019/01/21/matlab-tsp-all/

    结果

    测试数据:
    在这里插入图片描述
    初始状态:
    在这里插入图片描述
    最终状态:
    在这里插入图片描述

    收敛曲线图:
    在这里插入图片描述
    总结与观点

    难点是交叉算法的设计,由于TSP问题和一般的NP问题不一样,每个个体的每个维度具有唯一性,因此在交叉的时候要注意不能有重复的值。本次实验采用的是部分匹配交叉,先从第一个父代选出一个偏移量,从偏移量后的部分点加入到子代,接下来从第二个父代选择第一代没有选择的部分点移到子代中。
    当城市数量较多时,大于50个城市,迭代多次,GA仍然不收敛,可能的问题是陷入了局部最优解,因此对GA算法进行改进怡跳出局部最优解,可以采用类似于PSO或者蚁群算法的思想。

    更多内容访问 omegaxyz.com
    网站所有代码采用Apache 2.0授权
    网站文章采用知识共享许可协议BY-NC-SA4.0授权
    © 2020 • OmegaXYZ-版权所有 转载请注明出处

    展开全文
  • 改进的雪花算法——解决时钟回拨问题 原创公众号:软件设计活跃区2020年5月3日 改进的雪花算法——姑且称为梨花算法吧(忽如一夜春风来,千树万树梨花开)。 改进目标:解决雪花算法的时钟回拨问题;部分避免...

    改进的雪花算法——解决时钟回拨问题

    原创 公众号: 软件设计活跃区

    改进的雪花算法——姑且称为梨花算法吧(忽如一夜春风来,千树万树梨花开)。

    改进目标:解决雪花算法的时钟回拨问题;部分避免机器id重复时,号码冲突问题。

                          

    分布式唯一ID的方案有很多,雪花算法,组成结构大致分为为符号位、时间位、机器位和序列号位。其特点是趋势递增、有序、纯数字组成查询效率高且不依赖于数据库。适合在分布式的场景中应用,可根据需求调整具体实现细节。

     

    snowflake算法

    这种方案把64-bit分别划分成多段,分开来标示机器、时间等,比如在snowflake中的64-bit分别表示如下图(图片来自网络)所示:

     

     

    snowflake算法得到的ID是分段组成的:

    •     1bit:符号位,固定是0,表示全部ID都是正整数

    •     与指定日期的时间差(毫秒级),41位,够用69年

    •     集群ID 机器ID, 10位,最多支持1024台机器

    •     序列,12位,每台机器每毫秒内最多产生4096个序列号

     

    41-bit的时间可以表示(1L<<41)/(1000L*3600*24*365)=69年的时间,10-bit机器可以分别表示1024台机器。如果我们对IDC划分有需求,还可以将10-bit分5-bit给IDC,分5-bit给工作机器。这样就可以表示32个IDC,每个IDC下可以有32台机器,可以根据自身需求定义。12个自增序列号可以表示2^12个ID,理论上snowflake方案的QPS约为409.6w/s,这种分配方式可以保证在任何一个IDC的任何一台机器在任意毫秒内生成的ID都是不同的。

    这种方式的优缺点是:

    优点:

    •   毫秒数在高位,自增序列在低位,整个ID都是趋势递增的。

    作为DB表的主键,索引效率高。

    •   不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的。

    高性能高可用:生成时不依赖于数据库,完全在内存中生成。

    容量大:每秒中能生成数百万的自增ID。

    •   可以根据自身业务特性分配bit位,非常灵活。

     

    缺点:

    •     强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。

    •     可能会出现不是全局递增的情况。

     

    改进的雪花算法——姑且称为梨花算法吧(忽如一夜春风来,千树万树梨花开)。

    改进目标:解决雪花算法的时钟回拨问题;部分避免机器id重复时,号码冲突问题。

     

    long型的64位分成以下几个部分组成:

    符号位:1位

    时间:31位   (精确到秒)够用68年

    段号(批次号):3位    每秒可分为8个段

    机器id号:10位   最多支持1024台机器

    序列号:19位   可表示:0--524287

     

    如下图所示:

     

     

    注:根据情况,机器id号可以放到最后部分。

     

    (一)

    经过调整,时间只对秒灵敏,成功回避了服务器间几百毫秒的时间误差引起的时间回拨问题;若第59秒的8个段号没有用完,则当润秒来临时,还可继续使用。另外具体实现上,可设置一定的秒数(如3秒)内提前消费。比如第10秒的号码,在800毫秒用完了,可以继续使用第11秒的号码。这样,下1秒用的号码不是很多时,就可以借给上1秒使用。

           以上的方案是与时间强相关的。若某一段时间内的号码没用使用,也会浪费掉。当在分布式DB的表主键这种应用场景时,只需要全局id不重复,且是递增的。类似这种场景,可以设计成时间不相关的。

    (二)

    供分布式DB表主键等类似场景使用的,不浪费号码的方案。long型的64位分配还是一样。只不过,取号时,是取上一个号码加1,而不用管现在的时间是什么时候。当突然down机时,重启又获取当前的时间,重新开始分派号码;这时之前节省下的号码就被浪费掉了。为解决这个问题,可以在一段时间或分派一定数量的号(如10000),就将当前分派的号码记录到日志,或同步到DB表,等重启时,可以设置初始值。实现上,还是要控制分派的速度,若每秒几百万的号不够用,可用表名分隔命名空间,每个表单独取自己的号;即使号码够用,也可以这样做,因为这样得到的号在同一张表里就比较连续,而不只是递增而矣。当各个机器分派的id速度相差太大时,各机器得到的id大小就比较乱;这种问题,可以设置负载均衡,让每台机器轮流出号。

    (三)

    机器id重复的问题。当两台机器的id一样时,分派的号就会重复。若0-7八个段号(段号3位),每次都是从0-3随机获取一个开始的段号,比方说获取到2,那重复机器id的服务要是获取到0或1的段号就可以避免号码重复的冲突。当然了,这都是基于每秒用不完号码的情况下的。可以循环使用段号,如获取到3,那就从3-7,0,1,2这样使用段号,后面0,1,2这几个段号要是分派出去,号码就不递增了。具体怎么用,还是要根据自己的情况做取舍。

     

       Java版的梨花算法实现,期待下期与你一起讨论!   

    (  已实现, 有三种方式.

    #1:SerialUniqueId  ,2:OneTimeSnowflakeId  ,3:PearFlowerId. default is 1.
    bee.distribution.genid.idGenerator=1

    源码地址:

    https://github.com/automvc/bee

    https://gitee.com/automvc/bee

    https://github.com/automvc/bee/blob/master/src/main/java/org/teasoft/bee/distribution/GenId.java

    )

       欢迎关注微信公众号!

      长按二维码可关注(公众号: AiTeaSoft)

            更多重磅文章等着你!

     

    QQ群:   992650213

    微信群:    IT软件设计交流群3

     

    相关:

    教你如何避开雪花算法的坑

    https://blog.csdn.net/abckingaa/article/details/108653637

    展开全文
  • 算法复杂度与NP问题

    千次阅读 2019-05-02 19:14:51
    美剧《基本演绎法》S2E2中,两位研究 NP 问题的数学家被谋杀了,凶手是同行,因为被害者即将证明“P=NP 问题”。假设人类证明了P=NP 是真的,那么就会有一个算法,能够很快算出某个帐号的密码。《基本演绎法》里面所...
  • A*算法解决八数码难题

    千次阅读 2021-01-21 23:01:47
    基于状态空间表示法的搜索算法解决八数码难题 本文的pdf文件链接:link 一、问题重述 1.1 背景介绍        如今处于人工智能和大数据时代,每天都有成千上万的数据产生,而我们...
  • 贪心算法求解 TSP 旅行商问题及其实现

    千次阅读 多人点赞 2020-07-09 21:54:54
    贪心算法求解 TSP 问题得到局部最优解的具体实现,数据集来自 TSPLIB 的 att48 数据集。旅行商问题即 TSP(Traveling Salesman Problem),又称为货郎担问题,是数学领域中著名问题之一。
  • A* 算法解决八数码问题 matlab

    万次阅读 多人点赞 2017-05-17 20:34:22
    A* 算法使用matlab 解决 八数码问题 张旺华 这个算法值得注意和思考的问题就是 评估函数 ,评估函数直接影响到你的A*算法的效率,刚开始我选取的h(n)为p(n)------(每一个将牌与其目标位置之间的距离总和)运行...
  • 蚁群算法解决TSP问题

    万次阅读 2017-01-05 23:23:57
    蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理,根据昆虫学家的观察,发现自然界的蚂蚁虽然视觉不发达,但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径,并且在环境发生变化(如原有路径上...
  • 0-1 背包问题的 4 种解决方法&&算法策略

    万次阅读 多人点赞 2018-11-01 15:39:54
    现在将0-1背包问题解决方法整理出来,这样不仅区分不同的算法思想,还加深对0-1背包问题的理解。虽然有的算法思想并不能解决这一问题,但是为了对算法策略有一个较为整体的了解,所以在这里做一下简单的介绍。...
  • 最短路径问题---Dijkstra算法详解

    万次阅读 多人点赞 2017-03-08 16:42:46
    前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ending. Name:Willam Time:2017/3/8 1、最短路径问题介绍 问题解释: ...解决问题算法:...
  • Butterfly 简介 ...框架通过引入多种新的方案不仅解决了雪花算法存在的所有问题,而且还能够提供比雪花算法更高的性能。在单机版QPS理论值为51.2(w/s)这种情况下,新的方案在一些机器上可达 1200(w/s) 甚
  • 彻底解决汉诺塔问题——递归算法

    千次阅读 多人点赞 2019-05-18 11:23:52
    并且规定,任何时候,在小圆盘上都不放大圆盘,且在三根柱子之间一次只能移动一个圆盘。问应该如何操作? 下面我们来写递归函数。 首先,题目要求求的是如何操作,那么我们就必须写一个输出操作语句的函数。...
  • 数据结构核心原理与算法应用

    千人学习 2019-09-03 17:50:03
    “程序设计  =  算法  +  数据结构”,编程者如果没有掌握数据结构与算法,就说明没有真正掌握程序设计的能力,也就是不没有真正的...让学员真正的掌握数据结构与算法的精髓,灵活的解决实际问题
  • NP完全问题&贪婪算法

    千次阅读 2019-09-24 18:33:35
    算法导论中这样描述NP完全问题:在多项式时间内可解的问题是易处理的问题,在超多项式时间内解决问题是不易处理的问题。NP完全问题就是后者。通俗说就是:以难解著称的问题,比如旅行商问题和集合覆盖问题,人们...
  • 生活中的算法

    千次阅读 2020-12-24 12:06:31
    这人不紧不慢,伸出手来说道:“神仙大人,我别的什么也...而对于问题解决的方法来说,我们还应当进一步关注产生方法的方法,也就是算法。这是在中、小学教育的信息科技课程中强调生活算法的理由之一。所谓算法,...
  • 念念不忘,必有回响! 关于遗传算法的解释有很多。建立简单的叙述一下,不明白的...遗传算法(Genetic Algorithm,GA)是Holland教授于20世纪60年代提出,它主要借用了生物进化中“物竞天择,适者生存”的自然机理,.
  • 汉诺塔问题解决思路及算法

    万次阅读 2017-12-31 21:25:27
    关于汉诺塔问题,好多时候当时理解了过段时间可能又会忘,其实这个代码很简单,主要还是分治思想理解不够透彻。...假设当我们在数目为n-1的时候已经解决了移动问题可以成功移动至C,如果又多了一个呢,即
  • 测试使用K-最近邻(kNN)算法的30个问题

    千次阅读 多人点赞 2020-09-25 22:57:20
    如果你要问我机器学习中2种最直观的算法——那就是k最近邻(kNN)和基于树的算法。两者都易于理解,易于解释,并且很容易向人们展示。有趣的是,上个月我们对这两种算法进行了技能测试。 如果你不熟悉机器学习,请...
  • 旅行商问题之遗传算法

    千次阅读 2018-11-14 21:07:52
    问题描述 行商问题(Travelling Salesman Problem, 简记TSP,亦称货郎担问题):设有n个城市和距离矩阵,其中表示城市i到城市j的距离,i,j=1,2 … n,则问题是要找出遍访每个城市恰好一次的一条回路并使其路径长度为...
  • 随机算法

    千次阅读 2018-05-17 08:35:26
    较之那些我们所知的解决同一问题最好的确定性算法,随机算法所需的运行时间或空间通常小一些。 随机算法比较易于理解和实现(呵,站着说话不腰疼)。 随机算法的基本特征:对所求解问题的同一实例用同一随机算法.....
  • ACO蚁群算法解决TSP旅行商问题

    万次阅读 2015-04-30 15:31:45
    蚁群算法也是一种利用了大自然规律的启发式算法,与之前学习过的GA遗传算法类似,遗传算法是用了生物进行理论,把更具适应性的基因传给下一代,最后就得到一个最优解,常常用来寻找问题的最优解。当然,本篇文章...
  • 基于Matlab的遗传算法程序设计及优化问题求解

    万次阅读 多人点赞 2020-10-21 17:23:50
    在科学和生产实践中表现为在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法即找出一个最优解. 这种算法是1960年由Holland提出来的其最初的目的是研究自然系统的自适应行为并设计具有自适应功能的软件...
  • 完美解决方案-雪花算法ID到前端之后精度丢失问题

    千次阅读 多人点赞 2020-08-25 07:11:05
    最近公司的一个项目组要把以前的单体应用进行为服务拆分,表的ID主键使用Mybatis plus默认 的雪花算法来生成。 快下班的时候,小伙伴跑过来找我,:“快给我看看这问题,卡这卡了小半天了!”。连拉带拽,连哄带骗的...
  • 算法和数据结构》学习路线指引

    万次阅读 多人点赞 2021-07-01 11:16:15
    前 WorldFinal 选手对学习算法的一点总结。五张思维导图解决你的困惑
  • 拉斯维加斯算法和N皇后问题

    千次阅读 2016-12-21 22:47:06
    拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。因此通常用一个bool型函数... // 反复调用拉斯维加斯算法LV(x, y),直到找到问题的一个解 bool success= false; while (!success)
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...
  • 用动态规划算法解决0-1背包问题

    万次阅读 2016-04-30 21:44:25
    用动态规划算法解决0-1背包问题需要了解以下基本概念和原理: 1.使用动态规划算法必须具备两个基本要素:最优子结构性质和重叠子问题性质 2.动态规划算法常以自底向上的方式计算最优值,也就是说,从最小的子问题...
  • 2020.1.7(配送问题:路径优化 算法的学习)

    千次阅读 多人点赞 2020-01-07 14:56:48
    车辆路径问题(Vehicle Routing Problem, VRP):它是指一定数量的客户(或配送点),各自有不同数量的货物需求,配送中心向客户提供货物,由一个车队负责分送货物,组织适当的行车路线,目标是使得客户的需求得到...
  • 解决算法问题的五种通用方法

    千次阅读 2013-10-21 20:56:23
    毫无疑问,解决算法问题一定不止5种方法,但是下面的五种方法可能更加有用。但是还是要记住,算法靠的是不停的练习,练习越多,很多问题就迎刃而解! 同样也必须记住,这五种方法不是单独的组成,它们可以混合在一起...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 627,008
精华内容 250,803
关键字:

算法能解决任何问题吗