算法课大作业

2018年04月22日 162点热度 0人点赞 0条评论

概述

TSP问题又称为旅行商问题,是指旅行家要旅行个城市,要求每个城市都经历且仅经历一次后回到出发城市,要求所走的总路程最短。TSP问题具有NPC计算复杂性,目前比较常用的算法有蛮力法、动态规划法、回溯法以及分支限界法。由于两个城市来和回的距离不一定一样,因此TSP问题又可以分为有向图和无向图这两种情况,OJ上1813题和1814题分别对应了这两种情况。问题和起点的选择无关,因此下面讲述的算法均以0点作为出发点,方便说明。

蛮力法

算法分析

蛮力法算是最容易想到的方法了,通过穷举出除起点外其余所有点的全排列,依次计算每一种排列下的总路径,再求出其最小值即可,其实现方法最为简单,但同时,其时间复杂度也比较大,为$O(n!)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 21;	//n最大不超过21
const int DEFAULT = 0x3f3f3f3f;	//无穷大值
int N;
int maze[MAX_SIZE][MAX_SIZE];
int a[MAX_SIZE];
int minLength = DEFAULT;
int main() {
    scanf("%d", &N);	
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j < N; ++j) 
            if (i != j)
                scanf("%d", &maze[i][j]);	//输入
    for (int i = 0; i < N - 1; ++i) {
        a[i] = i + 1;	//生成(1,2,3……n)个数
    }
    do{
        int len = 0;
        len += maze[0][a[0]];		
        for (int i = 0; i < N - 2; ++i) {
            len += maze[a[i]][a[i + 1]];	//计算路径长度
        }
        len += maze[a[N - 2]][0];
        minLength = min(len, minLength);	//取最短的路径
    }while(next_permutation(a, a + N - 1));	//STL生成对应的全排列
    cout << minLength << endl;	//输出路径
    return 0;
}

运行结果

显然,蛮力法的时间复杂度太大,1814这个题由于$n$最大也不会超过10,因此用蛮力法还是可以AC的。然而,到了1813这个题,$n$最大变成了15,直接用蛮力交题导致的结果就是TLE。

回溯法

算法分析

回溯法也是比较容易想到的一种算法,这里我进行了一些优化。首先通过贪心算法算出一种路径上界$up$,创建一个$visited$数组用于标志访问过的点,然后从0起点开始DFS,每次放入一个点都将其$visited$标志位置1,同时每放入一个点计算当前的路径值,如果当前路径值已经大于上界$up$,则对其进行剪枝,不再对其子节点进行访问,当DFS深度满足城市点$n$的个数时,即为一种可行解,此时计算其路径值,若路径值比上界$up$小,则更新上界$up$的值。求出一种可行解后,再回溯到其父节点,不断重复。

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 21;
const int INF = 0x3f3f3f3f;
int N;
int maze[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE];	//标志数组
int minLength = 0;
void solve(int depth, int previous, int len) {	//分别传入递归深度、前一个点和当前路径
    if (depth == N) {	//若递归深度等于N
        minLength = min(minLength, len + maze[previous][0]);
        return;	//则更新当前最小路径(上界)
    }
    for (int i = 1; i < N; ++i) {
        if (visited[i] == 0) {	//如果没有被访问过
            visited[i] = 1;	//则标志位置1
            int Len = len + maze[previous][i];	
      //路径值=到上一个点的路径值+上一个点到当前点的距离
            if (Len > minLength) {	//如果当前已经超过上界
                visited[i] = 0;	//则标志位置0
                continue;	//继续访问下一个节点
            } else {
                solve(depth + 1, i, Len);	//否则递归下去
                visited[i] = 0;	//递归完后标志位也要置0
            }
        }
    }
}
void tanxin(int depth, int previous) {	//贪心算法
  //从0开始每次选取最短的距离,加入到路径中,当作一种可行解,其路径值作为剪枝的上界
    if (depth == N) {
        minLength += maze[previous][0];
        return;
    }
    int Min = INF;
    int index = 0;
    for (int i = 1; i < N; ++i) {
        if (previous == i || visited[i] == 1)	
    //不访问自身和访问过的点
            continue;
        if (maze[previous][i] < Min) {	//求解与上一个点距离最近的点
            Min = maze[previous][i];
            index = i;	//记录该点
        }
    }
    minLength += Min;	
    visited[index] = 1;	
    tanxin(depth + 1, index);	//求解与当前点距离最近的点
}
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j < N; ++j) 
            if (i != j)
                scanf("%d", &maze[i][j]);
    memset(visited, 0, sizeof(visited));	//初始化数组
    tanxin(1, 0);
    memset(visited, 0, sizeof(visited));
    solve(1, 0, 0);
    cout << minLength << endl;
    return 0;
}

运行结果

回溯法也是比较容易想到的一种算法,在搜索的过程中不断压榨上界值,同时不断将超过上界值的分支剪去,越到后期,上界值越小,剪枝越多,在$n$值较大的时候可以很明显看出,回溯法的速度较蛮力法有了很大的提升。

动态规划法

算法分析

动态规划算是求解TSP问题上比较高效的一种算法了,设$s,s_1,s_2,s_3……s_p,s$是从$s$出发的一条路径长度最短的回路,假设从$s$到下一个城市$s_1$已经求出,则问题转化为从$s_1$到$s$的最短路径,显然$s_1,s_2……s_p,s$一定构成一条从$s1$到$s$的最短路。

子问题的定义,对于图$G=(V,E)$,假设从顶点$i$出发,令$V’=V-i$,则$d(i,V’)$表示从顶点$i$出发,经过$V’$中每个顶且一次且仅一次,最后回到出发点$i$的最短路径的长度,显然,初始子问题为$d(k,\{\})$,即从定点i出发只经过定点$k$回到定点$i$,现在$d(k,V’-{k})$表示从顶点$k$出发经过$V’-{k}$中各个顶点一次且仅一次,最后回到出发点i的最短路径的长度,则有递推式如下:

$$
\begin{equation}
\begin{cases}
d(k,\{\})=c_{ki}\\
d(i,V')=min\{c_{ik}+d(k,V'-\{k\})\}(k\in V')
\end{cases}
\end{equation}
$$

对于$n$个点,其子集的个数为$2^n$个,这里我们需要用到状态压缩,将每一个子集用一个对应的二进制数来表示,第$i$个点在子集中则将对应的二进制位置为1,举个例子,若点1和4在子集中,则用二进制数0000……1001($n$位数)来表示该集合,在具体的代码实现上可用左移运算符$1<<(i-1)$,当需要判断点$i$是否在集合$k$中时候,需要用到逻辑运算符来判断$k\&(1<<(i-1))$。用动态规划解决$TSP$问题,需要对其每一个子集进行操作,子集内部要对起点和中间点进行操作,因此其时间复杂度位$O(2^nn^2)$,当$n$比较大时,其优势相较蛮力和回溯法十分明显。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 21;
int N;
int maze[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][1 << MAX_SIZE];
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j < N; ++j) 
            if (i != j)
                scanf("%d", &maze[i][j]);
    for (int i = 1; i < N; ++i)
        dp[i][0] = maze[i][0];	//初始子问题
    int len = 1 << (N - 1);	//子集个数
    for (int i = 1; i < len; ++i) { 	//遍历所有子集
        for (int j = 0; j < N; ++j) {  	//从j出发经过子集i中的点后回到0
            if (j != 0 && (i & (1 << (j - 1))))	
      //若子集中包含当前j,则跳过
                continue;
            for (int k = 1; k < N; ++k) {
                if (j == k)    //k和j不能为同一点
                    continue;
                if (i & (1 << (k - 1))) {  //若k在当前子集中
                    if (dp[j][i] == 0)	//若dp没有初始值
                        dp[j][i] = maze[j][k] + dp[k][i - (1 << (k - 1))];  //从j出发先经过k在经过剩余不包括k点的子集点
                    else
                        dp[j][i] = min(dp[j][i], maze[j][k] + dp[k][i - (1 << (k - 1))]);	//否则求解最小值
                }
            }
        }
    }
    printf("%d", dp[0][len - 1]);	
  //从0点出发遍历完其余所有点再回到0点的最小路径
    return 0;
}

分支界限法

算法分析

分支限界法通过限界函数来进行剪枝,对于$TSP$问题,目标函数的上界$up$可以用贪心算法来求解,下界$down$可以将领接矩阵中每一行最小的两个元素相加再除以2得到。由于书上的目标函数只针对无向图有效,因此对于OJ上的1813题,需要将书上的目标函数稍作变换,假设现在确定的路径为$U=\{s_0,s_1,s_2......s_k\}$ ,则当前的目标函数值的计算方法如下:

$$lb=(2\sum_{i=0}^{k-1}c[s_i][s_{i+1}]+\sum_{i=0,k}min_1\{s_i\}(s_i\notin U)+\sum_{s_j\notin U}min_2\{s_j\})/2$$

$lb$的第一项即为当前确定路径长度的两倍,第二项为进起点的最短路径和出当前终点的最短路径之和,第三项为不在当前路径的点的最短入路径和出路径之和。

首先扩展根节点的所有子节点,计算其目标函数值,凡是小于上界值的一律放入活结点表中,大于上界值的直接丢弃,接着取出目标函数值最小的结点,扩展其所有子节点,重复上述过程,直到叶子结点的路径小于活结点表中所有的目标函数值。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 21;
const int INF = 0x3f3f3f3f;
int N;
int up = 0;
int down = 0;
int maze[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE];
int minLength = INF;
struct Node {
    int e;	//结点终点
    int lb;	//结点目标函数值
    int dis;	//当前走过的距离
    int cnt;	//当前走过的点的个数
    long long visited;
    bool operator < (const Node& p) const {
        return p.lb < lb;
    }
};
void getup(int depth, int pre) {	//贪心求上界
    if (depth == N) {
        up += maze[pre][0];
        return;
    }
    int Min = INF;
    int index = 0;
    for (int i = 1; i < N; ++i) {
        if (pre == i || visited[i] == 1) 
            continue;
        if (maze[pre][i] < Min) {
            Min = maze[pre][i];
            index = i;
        }
    }
    up += Min;
    visited[index] = 1;
    getup(depth + 1, index);
}
void getdown() {	//求下届
    int sum = 0;
    for (int i = 0; i < N; ++i) {	//求每一行最小两个数的和
        priority_queue<int, vector<int>, greater<int> >p;
        for (int j = 0; j < N; ++j) {
            if (i != j) {
                p.push(maze[i][j]);
            }
        }
        sum += p.top();
        p.pop();
        sum += p.top();
    }
    down = (sum % 2 == 0) ? (sum / 2) : (sum / 2 + 1);
}
void getlb(Node& node) {	//求目标函数值
    int sum1 = 0;
    for (int i = 1; i < N; ++i) {
        if ((node.visited & (1 << i)) == 0) {
            int Min1 = INF;
            int Min2 = INF;
            for (int j = 1; j < N; ++j) {
                Min1 = min(Min1, maze[i][j]);	//i点最短出距离
                Min2 = min(Min2, maze[j][i]);	//i点最短入距离
            }
            sum1 += Min1 + Min2;	//i点的最短出入之和
        }
    }
    int sum2 = INF;
    int sum3 = INF;
    for (int i = 1; i < N; ++i) {
        sum2 = min(sum2, maze[i][0]);	//所有点到起点的最短距离
        sum3 = min(sum3 ,maze[node.e][i]);	//终点到所有点的最短距离

    }
    int lb = 2 * node.dis + sum1 + sum2 + sum3;
    node.lb = (lb % 2 == 0 ) ? (lb / 2) : (lb / 2 + 1);//向上取整
}
priority_queue<Node> q;
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i != j) {
                scanf("%d", &maze[i][j]);
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    getup(1, 0);
    getdown();
    for(int i = 1; i < N; ++i) {	//生成与起点相邻的子节点
        Node new_node;
        new_node.visited = 1 + (1 << i);	//标志位置1(状态压缩)
        new_node.dis = maze[0][i];	//初始距离
        new_node.e = i;	//当前路径终点
        new_node.cnt = 1;	//当前路径点个数(不包括起点)
        getlb(new_node);	//计算目标函数值
        if (new_node.lb <= up) {	//若小于上界
            q.push(new_node);	//放入优先队列中
        }
    }
    while (!q.empty()) {	//循环条件为优先队列非空
        Node head = q.top();	//取出目标函数值最小的结点
        q.pop();
        if (head.cnt == N - 2) {	//若当前路径长度为N-2
            int last;
            for (int i = 1; i < N; ++i) {//找出最后一个没被访问的结点
                if ((head.visited & (1 << i)) == 0) {
                    last = i;
                    break;
                }
            }
            int len = head.dis + maze[head.e][last] + maze[last][0];		//计算回路的路径长度
            minLength = min(minLength, len);	//更新最小路径长度
            up = min(up, minLength);	//压榨上界
            Node judge = q.top();		
            if (minLength <= judge.lb) {	
    //若最小路径小于活结点表中的所有目标函数值
                break;	//则找到最优解,结束搜索
            }
        }
        Node new_node;	
        for (int i = 1; i < N; ++i) {
            if ((head.visited & (1 << i)) == 0) {	
      //否则生成当前路径宁下未被访问过的结点
                new_node.visited = head.visited + (1 << i);
      //标志位置1
                new_node.dis = head.dis + maze[head.e][i];
      //路径增加
                new_node.e = i;	//当前路径终点变为i
                new_node.cnt = head.cnt + 1;	//路径点的个数+1
                getlb(new_node);
                if (new_node.lb <= up) {	//目标函数之小于上界
                   q.push(new_node);	//放入优先队列
                }
            }
        }
    }
    cout << minLength << endl;	//输出结果
    return 0;
}

运行时间比较

根据上面的几组样例,为计算了一下每组样例的运行时间作为参考,取3组求平均值,单位均为ms,其中大于10000ms的不做统计。

Plus

Think Different

文章评论