小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. 正文

算法笔记之回溯法(3)

2019年2月27日 1079点热度 0人点赞 0条评论

最优加工顺序

问题描述

现在有3个机器零件{J1,J2,J3},在第一台机器上的加工时间分别为2、5、4,在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序,使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成,所需的总加工时间最短?

问题分析

我们通过分析可以发现,第一台机器可以连续加工,而第二台机器开始加工的时间是当前第一台机器的下线时间和第二台机器下线时间的最大值。
实际上就是找到n个机器零件的一个排列,使总的加工时间最短。

算法设计

  1. 定义问题的解空间。解的形式为n元组:{x1,x2,...,xi,...,xn},分量xi表示第i个加工的零件号,n个零件组成的集合为S={1,2,...,n},xi取值为S-{x1,x2,...,xi-1}。
  2. 解空间的组织形式为一颗排列数,深度为n。
  3. 搜索解空间。
    • 约束条件:无约束条件。
    • 限界条件:用f2表示当前已完成的零件在第二台机器加工结束所用的时间,用bestf表示当前找到的最优加工方案的完成时间。显然,继续向深处搜索时,f2不会减少,只会增加。因此,当f2≥bestf时,没有继续向深处搜索的必要。限界条件可以描述为:f2<bestf。f2初值为0,bestf的初值为无穷大。
  4. 搜索过程。扩展结点沿着某个分支扩展时需要判断限界条件,如果满足,则进入深一层继续搜索;如果不满足,则剪掉该分支。搜索到叶子结点的时候,即找到当前最优解。搜索直到全部活结变成死结点为止。

代码实现

1.数据结构

struct node
{
    //机器零件在第一台机器上的加工时间x和第二胎机器上的加工时间y
    int x,y;
}T[MAX];

2.按限界条件进行搜索求解:t表示当前扩展结点在第t层,f1表示当前第一台机器上加工的完成时间,f2表示当前第二台机器上加工的完成时间。如果t>n表示已经到达叶子结点,记录最优值和最优解,返回。否则,分别判断每个分支是否满足约束条件,若满足则进入下一层backtrack(t+1);如果不满足则反操作复位,考察下一个分支(兄弟结点)。

void Backtrack(int t)
{
    if(t>n)
    {
        for(int i=1;i<=n;i++)
            bestx[i]=x[i];//记录最优队列
        bestf=f2;//更新最优值
        return ;
    }
    for(int i=t;i<=n;i++)
    {
        f1+=T[x[i].x;
        int temp=f2;
        f2=max(f1,f2)+T[x[i]].y;
        if(f2<bestf)//满足限界条件
        {
            swap(x[t],x[i]);//交换
            Backtrack(t+1);//继续搜索
            swap(x[t],x[i]);//复位,反操作
        }
        f1-=T[x[i]].x;//复位,反操作
        f2=temp;//复位,反操作
    }
}

算法复杂度分析

时间复杂度为O(nn!)≈O((n+1)!),空间复杂度为O(n)。

算法优化改进

新的算法的时间复杂度为O(nlogn),空间复杂度为O(n)。利用贝尔曼规则,代码如下:

#include<iostream>
#include<algorithm>
using namespace std ;
const int MX=10000+5 ;
int n;
struct node
{
    int id;
    int x,y;
}T[MX] ;
bool cmp(node a,node b)
{
    return min(b.x,a.y)>=min(b.y,a.x);//按照贝尔曼规则排序
}
int main()
{
    cout<<"请输入机器零件的个数 n:";
    cin>>n;
    cout<<"请依次输入每个机器零件在第一台机器上的加工时间x和第二台机器上的加工时间y:";
    for(int i=0;i<n;i++)
    {
        cin>>T[i].x>>T[i].y;
        T[i].id=i+1;
    }
    sort(T,T+n,cmp);   //排序
    int f1=0,f2=0;
    for(int i=0;i<n;i++)  //计算总时间
    {
       f1+=T[i].x;
       f2=max(f1,f2)+T[i].y;
     }
    cout<<"最优的机器零件加工顺序为:";
     for(int i=0;i<n;i++) //输出最优加工顺序
       cout<<T[i].id<<" ";
    cout<<endl;
    cout<<"最优的机器零件加工的时间为:";
    cout<<f2<<endl;
    return 0 ;
}

旅行商问题

问题描述

假设有5个点,这五个点之间是用无向边来连接的,但是每一个边是有权重的,这实际上是一个无向带权图。我们希望在最小权重的情况下走过这5个点,且不重复,那应该怎样来实现呢?

旅行商问题无权图举例

算法设计

  1. 定义问题的解空间:问题解的形式为n元组{x1,x2,...,xi,...,xn},分量xi表示第i个要去的旅游景点编号,景点的集合为S={1,2,...,N}。因为景点不可重复走,因此在确定xi时,前面走过的景点{x1,x2,...,xi,...,xi-1}不能再走。xi的取值为S-{x1,x2,...,xi,...,xi-1}。
  2. 解空间的组织形式:解空间是一颗排列树,树的深度为n=5。除了开始结点1之外,一共有24种排列方式。
  3. 搜索解空间:约束条件:用二维数组g[][]储存无向带权图的邻接矩阵,如果g[i][j]≠无穷表示城市i和城市j又边相连,能走通。限界条件:cl<bestl。cl的初始值为0,表示当前已经走过的城市所用的路径长度;bestl初始值为无穷,表示当前找到的最短路径的路径长度。
  4. 搜索过程:扩展结点沿着某个分支扩展时需要判断约束条件和限界条件,如果满足,则进入深一层继续搜索,如果不满足,则剪掉该分支。搜索到叶子结点时,即找到了当前最优解。搜索直到全部的活结点变成死结点为止。

完美图解

(1)数据结构:如下表所示的邻接矩阵。

3 8 9
3 3 10 5
3 4 3
8 10 4 20
9 5 3 20

(图中未填的就是无穷)

(2)初始化:cl=0,bestl=无穷,解分量x[i]和最优解bestx[i]初始化为:

i 1 2 3 4 5
x[i] 1 2 3 4 5
i 1 2 3 4 5
bestx[i] 0 0 0 0 0

(3)开始搜索第一层(t=1)

扩展A0结点,因为我们是从1号结点出发,所以x[1]=1,生成A结点。

(4)扩展A结点(t=2)
沿着x[2]=2分支扩展,因为1号结点和2号结点有边相连,且cl+g[1][2]=0+3<bestl,满足限界条件,生成B结点。

(5)扩展B结点(t=3)
沿着x[3]=3分支扩展,因为2号结点和3号结点有边相连,且cl+g[2][3]=3+3=6<bestl,满足限界条件,生成C结点。

(6)扩展C结点(t=4)
沿着x[4]=4分支扩展,因为3号结点和4号结点有边相连,且cl+g[3][4]=6+4=10<bestl,满足限界条件,生成D结点。

(7)扩展D结点(t=5)
沿着x[5]=5分支扩展,因为4号结点和5号结点有边相连,且cl+g[3][4]=10+20=30<bestl,满足限界条件,生成E结点。

(8)扩展E结点(t=6)
t>n,判断5号结点是否和1号结点相连,确认有,且cl+g[5][1]=30+9=39<bestl,找到一个当前最优解(1,2,3,4,5,1),更新bestl=39。

(9)向上回溯到D,D的孩子已经生成完毕,成为死结点,继续回溯到C,C结点还有一个孩子未生成。
(10)重新扩展C结点(t=4)。沿着x[4]=5分支扩展,因为3号结点和5号结点有边相连,且cl+g[3][5]=6+3=9<bestl=39,满足限界条件,生成F结点。

(11)扩展F结点(t=5)。
沿着x[5]=4分支扩展,因为5号结点和4号结点有边相连,且cl+g[5][4]=9+20=29<bestl=39,满足限界条件,生成G结点。

(12)扩展G结点(t=6)。t>n,判断4号结点是否和1号结点相连,确认有,且cl+g[4][1]=29+8=37<bestl=39,找到一个当前最优解(1,2,3,5,4,1),更新bestl=37。

不断搜索下去,到最后有以下组合和其值。

i 1 2 3 4 5 权值
结点组合 1 2 3 4 5 39
结点组合 1 2 3 5 4 37
结点组合 1 2 4 3 5 29
结点组合 1 2 5 3 4 23
结点组合 1 4 3 2 5 29
结点组合 1 4 3 5 2 23
结点组合 1 5 2 3 4 29

综上所述,bestl=23,路径为1-2-5-3-4-1。

代码实现

//初始化
void init()
{
    bestl = INF;
    cl = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            g[i][j] = g[j][i] = INF;
    for (int i = 0; i <= n; i++)
    {
        x[i] = i;
        bestx[i] = 0;
    }
}
//邻接矩阵赋值
void createMatrix()
{
    int u, v, w;//结点u和v,权值w
    cout << "请依次输入两个结点u和v之间的权值w。" << endl;
    cout << "格式:结点u 结点v 距离w" << endl;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
}
//回溯法核心
void backTrack(int t)
{
    if (t > n)
        //到达叶子结点
        //最后一个结点与第一个结点有边相连且路径长度比当前最优值最小
        //说明找到了一条更优路径,记录相关信息
    {
        if (g[n][1] != INF && (cl + g[x[n]][1] < bestl))
        {
            for (int j = 1; j <= n; j++)
                bestx[j] = x[j];
            bestl = cl + g[x[n]][1];
        }

    }
    else
    {
        //没有到达叶子结点
        for (int j = t; j <= n; j++)
        {
            //搜索扩展结点的所有分支
            //如果第t-1个结点与第t个结点有边相连且可以得到更短路径
            if (g[x[t - 1]][x[j]] != INF && (cl + g[x[t - 1]][x[j]] < bestl))
            {
                //保存第t个结点到x[t]中,进入第t+1个
                swap(x[t], x[j]);//交换两个元素的值
                cl = cl + g[x[t - 1]][x[t]];
                backTrack(t + 1);
                cl = cl - g[x[t - 1]][x[t]];
                swap(x[t], x[j]);
            }
        }
    }
}

//打印路径
void print()
{
    cout << "最短路径:" << endl;
    for (int i = 1; i <= n; i++)
        cout << bestx[i] << "--->";
    cout << "1" << endl;
    cout << "最短路径长度:" << bestl << endl;
}

算法复杂度分析

  1. 时间复杂度:除了最后一层外,有1+(n-1)+...+(n-1)(n-2)...2<=n(n-1)!个结点需要判断约束函数和限界函数,判断两个函数需要O(1)的时间,因此耗时O(n!)。在叶子节点处记录当前最优解需要耗时O(n),在最坏情况下回搜索到每一个叶子结点,叶子数为(n-1)!,所以时间复杂度为O(n!)。
  2. 空间复杂度:O(n)。
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: C++ 回溯法 算法
最后更新:2019年2月27日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
Linux第八天:共享存储映射、匿名映射 训练神经网络的基本步骤 C++ Primer Plus(第五版)第11章编程题答案 “裹脚布”飘扬 Python语言程序设计(第7周)知识点整理 [leetcode]题目解析(190610)
标签聚合
linux 鸟哥的linux私房菜 Python Java 高中 生活 学习 算法 python学习 leetcode
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号