算法笔记之分支限界法（2）

2019年3月3日 comment

旅行商问题

问题分析

带权邻接矩阵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)。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注