旅行商问题搜索求解

问题描述
某售货员要到若干城市去推销商品,已知各城市之间的路程(旅费),他要选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(总旅费)最小。
输入
输入第一行为一个整数n,表示图的顶点数
输入第二行为一个整数k,表示图的边数
输入第3到k+3-1行表示边的信息,每一行三个数,分别表示顶点i,顶点j,i到j的路径长度a[i][j]

4
6
1 2 30
1 3 6
1 4 4
2 3 5
2 4 10
3 4 20

输出
输出有两行
第一行为最优值,表示旅行商的最短路径长度
第二行为最优解,为旅行商的顶点遍历序列

25
1 3 2 4 1

int n;//城市的个数
double dist[N][N];//保存两城之间的距离,即有权值得边,得邻接矩阵
//path :已搜索得路径
//visited:对各城市访问与否
//currentLength:所有已检索路径得长度
//在访问得所有城市路径中,返回最短路径
double shortestPath(vector<int>&path,vector<bool>&visited,double currentLength){
    //初始化部分
    if(path.size() == n)
    return currentLength += dist[path[0]][path.back()];//还有加上把最后一个城市与第一个城市之间的距离
    double ret = INF;
    //常识所有可能得下一个访问得城市。
    for(int next = 0;next <n;++next){
        if(visited[next])continue;
        int here = path.back();
        path.push_back(next);
        visited[next] = true;
        //利用递归完成剩余的路径的检索,并得到最短路径的长度。
        double cand = shortestPath(path,visited,currentLength+dist[here][next]);
        ret += min(ret,cand);
        visited[next] = false;
        path.pop_back();
    }
    return ret;
}
上一篇:剑指offer 13. 机器人的运动范围


下一篇:基于ABP模块组件与依赖注入组件的项目插件开发