小奥的学习笔记

  • 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. 正文

算法笔记之分支限界法(2)

2019年3月3日 1293点热度 0人点赞 0条评论

旅行商问题

问题分析

带权邻接矩阵g[][]如下所示,空表示为无穷,即没有路径。

15 30 5
15 6 12
30 6 3
5 12 3

算法设计

可以使用优先队列分支限界法,加快搜索速度。
设置优先级:当前已走过的城市所有的路径长度cl。cl越小,优先级越高。
从根节点开始,以广度优先的方式进行搜索。根节点首先成为活结点,也是当前的扩展结点。一次性生成所有的孩子结点,判断孩子结点是否满足约束条件和限界条件,如果满足,将其加入到队列中,反之,舍弃。然后再从队列中取出一个元素,作为当前扩展结点,搜索过程队列为空时为止。

代码实现

struct Node//定义结点,记录当前结点的解信息
{
    double cl; //当前已走过的路径长度
    int id; //景点序号
    int x[N];//记录当前路径
    Node() {}
    Node(double _cl,int _id)
    {
        cl = _cl;
        id = _id;
    }
};

//定义队列的优先级。 以cl为优先级,cl值越小,越优先
bool operator <(const Node &a, const Node &b)
{
    return a.cl>b.cl;
}

//Travelingbfs 为优先队列式分支限界法搜索
double Travelingbfs()
{
    int t; //当前处理的景点序号t
    Node livenode,newnode;//定义当前扩展结点livenode,生成新结点newnode
    priority_queue<Node> q; //创建一个优先队列,优先级为已经走过的路径长度cl,cl值越小,越优先
    newnode=Node(0,2);//创建根节点
    for(int i=1;i<=n;i++)
    {
       newnode.x[i]=i;//初时化根结点的解向量
    }
    q.push(newnode);//根结点加入优先队列
    cout<<"按优先级出队顺序:"<<endl;//用于调试
    while(!q.empty())
    {
        livenode=q.top();//取出队头元素作为当前扩展结点livenode
        q.pop(); //队头元素出队
        //用于调试
        cout<<"当前结点的id值:"<<livenode.id<<"当前结点的cl值:"<<livenode.cl<<endl;
        cout<<"当前结点的解向量:";
        for(int i=1; i<=n; i++)
        {
            cout<<livenode.x[i];
        }
        cout<<endl;
        t=livenode.id;//当前处理的景点序号
        // 搜到倒数第2个结点时个景点的时候不需要往下搜索
        if(t==n)  //立即判断是否更新最优解,
            //例如当前找到一个路径(1243),到达4号结点时,立即判断g[4][3]和g[3][1]是否有边相连,
            //如果有边则判断当前路径长度cl+g[4][3]+g[3][1]<bestl,满足则更新最优值和最优解
        {
           //说明找到了一条更好的路径,记录相关信息
           if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF)
             if(livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]<bestl)
             {
                bestl=livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1];
                cout<<endl;
                cout<<"当前最优的解向量:";
                for(int i=1;i<=n;i++)
                {
                  bestx[i]=livenode.x[i];
                  cout<<bestx[i];
                }
                cout<<endl;
                cout<<endl;
              }
            continue;
        }
        //判断当前结点是否满足限界条件,如果不满足不再扩展
       if(livenode.cl>=bestl)
          continue;
        //扩展
        //没有到达叶子结点
        for(int j=t; j<=n; j++)//搜索扩展结点的所有分支
        {
            if(g[livenode.x[t-1]][livenode.x[j]]!=INF)//如果x[t-1]景点与x[j]景点有边相连
            {
                double cl=livenode.cl+g[livenode.x[t-1]][livenode.x[j]];
                if(cl<bestl)//有可能得到更短的路线
                {
                    newnode=Node(cl,t+1);
                    for(int i=1;i<=n;i++)
                    {
                      newnode.x[i]=livenode.x[i];//复制以前的解向量
                    }
                    swap(newnode.x[t], newnode.x[j]);//交换x[t]、x[j]两个元素的值
                    q.push(newnode);//新结点入队
                }
            }
        }
    }
    return bestl;//返回最优值。
}

(1)时间复杂度:O(n!)。空间复杂度:O(n*n!)。

算法优化拓展

  1. 算法开始时创建一个用于表示活结点优先队列。每个结点的费用下界zl=cl+rl值作为优先级。cl表示已经走过的路径长度,rl表示剩余路径长度的下界,rl用剩余每个结点的最小出边之和来计算。初始时先计算图中每个顶点i的最小出边,并用minout[i]数组记录,minsum记录所有结点的最小出边之和。如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法立即结束。
    • 限界条件:zl<bestl,zl<cl+rl。
  2. 优先级:zl指已经走过的路径长度+剩余路径长度的下界。zl越小,优先级越高。

算法优化代码实现

1.定义节点结构体

//定义结点,记录当前结点的解信息
struct Node
{
    double cl; //当前已走过的路径长度
    double rl; //剩余路径长度的下界
    double zl; //当前路径长度的下界zl=rl+cl
    int id; //景点序号
    int x[N];//记录当前解向量
    Node() {}
    Node(double _cl,double _rl,double _zl,int _id)
    {
        cl = _cl;
        rl = _rl;
        zl = _zl;
        id = _id;
    }
};

2.定义队列优先级

bool operator <(const Node &a, const Node &b)
{
    return a.zl>b.zl;
}

3.计算下界

bool Bound()//计算下界(即每个景点最小出边权值之和)
{
    for(int i=1;i<=n;i++)
    {
       double minl=INF;//初时化景点点出边最小值
       for(int j=1;j<=n;j++)//找每个景点的最小出边
         if(g[i][j]!=INF&&g[i][j]<minl)
            minl=g[i][j];
       if(minl==INF)
          return false;//表示无回路
       minout[i]=minl;//记录每个景点的最少出边
       cout<<"第"<<i<<"个景点的最少出边:"<<minout[i]<<" "<<endl;
       minsum+=minl;//记录所有景点的最少出边之和
    }
    cout<<"每个景点的最少出边之和:""minsum= "<<minsum<<endl;
    return true;
}

4.Travelingbfsopt 为优化的优先队列式分支限界法

double Travelingbfsopt()
{
    if(!Bound())
        return -1;//表示无回路
    Node livenode,newnode;//定义当前扩展结点livenode,生成新结点newnode
    priority_queue<Node> q; //创建一个优先队列,优先级为当前路径长度的下界zl=rl+cl,zl值越小,越优先
    newnode=Node(0,minsum,minsum,2);//创建根节点
    for(int i=1;i<=n;i++)
    {
       newnode.x[i]=i;//初时化根结点的解向量
    }
    q.push(newnode);//根结点加入优先队列
    while(!q.empty())
    {
        livenode=q.top();//取出队头元素作为当前扩展结点livenode
        q.pop(); //队头元素出队
        cout<<"当前结点的id值:"<<livenode.id<<"当前结点的zl值:"<<livenode.zl<<endl;
        cout<<"当前结点的解向量:";
        for(int i=1; i<=n; i++)
        {
            cout<<livenode.x[i];
        }
        cout<<endl;
        int t=livenode.id;//当前处理的景点序号
        // 搜到倒数第2个结点时个景点的时候不需要往下搜索
        if(t==n)  //立即判断是否更新最优解,
            //例如当前找到一个路径(1243),到达4号结点时,立即判断g[4][3]和g[3][1]是否有边相连,
            //如果有边则判断当前路径长度cl+g[4][3]+g[3][1]<bestl,满足则更新最优值和最优解
        {
           //说明找到了一条更好的路径,记录相关信息
           if(g[livenode.x[n-1]][livenode.x[n]]!=INF&&g[livenode.x[n]][1]!=INF)
             if(livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1]<bestl)
             {
                bestl=livenode.cl+g[livenode.x[n-1]][livenode.x[n]]+g[livenode.x[n]][1];
                cout<<endl;
                cout<<"当前最优的解向量:";
                for(int i=1;i<=n;i++)
                {
                  bestx[i]=livenode.x[i];
                  cout<<bestx[i];
                }
                cout<<endl;
                cout<<endl;
              }
            continue;
        }
        //判断当前结点是否满足限界条件,如果不满足不再扩展
       if(livenode.cl>=bestl)
          continue;
        //扩展
        //没有到达叶子结点
        for(int j=t; j<=n; j++)//搜索扩展结点的所有分支
        {
            if(g[livenode.x[t-1]][livenode.x[j]]!=INF)//如果x[t-1]景点与x[j]景点有边相连
            {
                double cl=livenode.cl+g[livenode.x[t-1]][livenode.x[j]];
                double rl=livenode.rl-minout[livenode.x[j]];
                double zl=cl+rl;
                if(zl<bestl)//有可能得到更短的路线
                {
                    newnode=Node(cl,rl,zl,t+1);
                    for(int i=1;i<=n;i++)
                    {
                      newnode.x[i]=livenode.x[i];//复制以前的解向量
                    }
                    swap(newnode.x[t], newnode.x[j]);//交换两个元素的值
                    q.push(newnode);//新结点入队
                }
            }
        }
    }
    return bestl;//返回最优值。
}

算法复杂度分析

时间复杂度最坏为O(nn!),空间复杂度为O(n2*(n+1)!)。

最优工程布线问题

问题描述

在3×3的方格阵列,灰色表示封锁,不能通过。将每个方格抽象为一个结点,方格和相邻4个方向(上下左右)中能通过的方格用一条线连接起来,不能通过的方格不连线。这样,可以把问题的解空间定义为一个图,如下图所示。

该问题是特殊的最短路径问题,特殊之处在于用布线走过的方格数代表布线的长度,布线时每一个方格,布线长度累加1.我们可以看出,从a到b有多种布线方案,最短的布线长度即从a到b的最短路径长度为4。
既然只能朝四个方向布线,也就是说如果从树型搜索的角度来看,我们可以把它看做为m叉树,那么问题的解空间就变成了一颗m叉树。

算法设计

(1)定义问题的解空间。可以把最优工程布线问题解的形式为n元组{x1,x2,...,xi,...,xn},分量xi表示最优布线方案经过的第i个方格,而方格也可以用(x,y)表示第x行第y列。因为方格不可重复布线,所以在确定xi的时候,前面走过的方格{x1,x2,...,xi-1}都不可以再走,xi的取值范围为S-{x1,x2,...,xi-1}。
注意:和前面问题不同,因为不知道最优布线长度,所以n是未知的。

(2)解空间的组织结构:一颗m叉树,m=4,树的深度n未知。

(3)搜索解空间。搜索从起始结点a开始,到目标节点b结束。
- 约束条件:非障碍物或边界未曾布线。
- 限界条件:最先碰到的一定是距离最短的,因此无限界条件。
- 搜索过程:从a开始将其作为第一个扩展结点,沿a的右、下、左、上4个方向的相邻结点扩展。判断约束条件是否成立,若成立,则放入活结点中,并将这个方格标记为1。接着从活结点队列中取出队首结点作为下一个扩展结点,并沿当前扩展结点的右、下、左、上四个方向的相邻结点扩展,将满足约束条件的方格记为2,依此类推,一直继续搜索到目标方格或活结点为空为止,目标方格里的数据就是最优的布线长度。

构造最优解过程从目标节点开始,沿着右、下、左、上四个方向。判断如果某个方向方格里的数据比扩展结点方格的数据小1,则进入该方向方格,使其成为当前的扩展结点。以此类推,搜索过程一直持续到起始结点结束。

算法实现

//定义结构体position
typedef struct
{
    int x;
    int y;
} Position;//位置
int grid[100][100];//地图
bool findpath(Position s, Position e, Position *&path, int &PathLen)
{
    if ((s.x == e.x) && (s.y == e.y))//开始位置就是结束位置
    {
        PathLen = 0;
        return true;
    }
    Position DIR[4], here, next;
    //定义方向数组DIR[4],当前位置here,下一个位置next
    DIR[0].x = 0;
    DIR[0].y = 1;
    DIR[1].x = 1;
    DIR[1].y = 0;
    DIR[2].x = 0;
    DIR[2].y = -1;
    DIR[3].x = -1;
    DIR[3].y = 0;
    here = s;
    grid[s.x][s.y] = 0;//标记初始为0,未布线为-1,墙壁为-2
    queue<Position> Q;//所使用队列
    //按四个方向进行搜索
    for (;;)
    {
        for (int i = 0; i < 4; i++)//四个方向前进,右下左上
        {
            next.x = here.x + DIR[i].x;
            next.y = here.y + DIR[i].y;
            if (grid[next.x][next.y] == -1)//未布线
            {
                grid[next.x][next.y] = grid[here.x][here.y] + 1;
                Q.push(next);
            }
            if ((next.x == e.x) && (next.y == e.y))
                break;//找到了我们需要的目标
        }
        if ((next.x == e.x) && (next.y == e.y))
            break;//找到了我们需要的目标
        if (Q.empty())
            return false;
        else
        {
            here = Q.front();
            Q.pop();//把Q队头的元素弹出
        }
    }
    //逆向找回最短布线方案
    PathLen = grid[e.x][e.y];//最短的长度
    path = new Position[PathLen];
    here = e;
    for (int j = PathLen - 1; j >= 0; j--)
    {
        path[j] = here;
        //沿着四个方向寻找,右下左上
        for (int i = 0; i < 4; i++)
        {
            next.x = here.x + DIR[i].x;
            next.y = here.y + DIR[i].y;
            if (grid[next.x][next.y] == j)
                break;
        }
        here = next;
    }
    return true;
}
//初始化地图,标记大于0表示已经布线,-1未布线,-2墙壁
void init(int m, int n)
{
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            grid[i][j] = -1;
    //上面是先将所有的格子都初始化为-1
    //然后把本问题为了方便加上的第0行和第0列都设置为墙
    for (int i = 0; i <= n + 1; i++)
        grid[0][i] = grid[m + 1][i] = -2;
    for (int i = 0; i <= m + 1; i++)
        grid[i][0] = grid[i][n + 1] = -2;
}

复杂度分析

时间复杂度O(nm),构造最短布线需要O(L),空间复杂度O(n)。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: C++ 分支限界法 算法
最后更新:2019年3月3日

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
凌源高中——鬼娃娃的传说TXT下载 C++必读书籍推荐 玩转你的Gravatar全球通用头像 吴恩达深度学习课程DeepLearning.ai笔记(5-3) 2009-08-17:日记 C++:实现“鱼额宝”
标签聚合
Java Python python学习 鸟哥的linux私房菜 linux 学习 算法 生活 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 发布于 8 个月前(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号