精华内容
下载资源
问答
  • 旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线...
  • 实现3-12双调旅行售货员问题.cpp
  • 回溯算法旅行商问题代码实现。算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次,每次更新bestx需计算时间O(n),从而整个算法的计算时间复杂性为O(n!)。
  • 分支限界法思想和案例(装载问题,旅行售货员问题,0-1背包问题)。算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
  • 全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.掌握分支限界法的核心思想; 2.实现旅行售货员问题分支限界法求解; 3.分析算法的复杂性。 预览地址:
  • 回溯法思想和案例(旅行售货员问题,装载问题, 0-1背包问题,图的m着色问题)。 算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
  • 旅行售货员问题的一些特殊性质:比如,费用函数c往往具有三角不等式性质,即对任意的3个顶点u,v,w∈V,有:c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点,任意2顶点间的费用就是这2点间的欧氏距离时,费用...

    问题描述:

    给定一个完全无向图G=(V,E),其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路。

    旅行售货员问题的一些特殊性质:

    比如,费用函数c往往具有三角不等式性质,即对任意的3个顶点u,v,w∈V,有:c(u,w)≤c(u,v)+c(v,w)。当图G中的顶点就是平面上的点,任意2顶点间的费用就是这2点间的欧氏距离时,费用函数c就具有三角不等式性质。

    当费用函数c具有三角不等式性质时,可以设计出一个近似算法,其性能比为2.而对于一般情况下的旅行售货员问题则不可能设计出具有常数性能比的近似算法,除非P=NP.

    具有三角不等式性质的旅行售货员问题

    对于给定的无向图G,可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。当费用函数满足三角不等式时,算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。

    void approxTSP (Graph g)

    {

    (1)选择g的任一顶点r;

    (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T;

    (3)前序遍历树T得到的顶点表L;

    (4)将r加到表L的末尾,按表L中顶点次序组成回路H,作为计 算结果返回;

    }

    下图说明算法approxTSP运行情况:

    (b)表示找到的最小生成树T;(c)表示对T作前序遍历的次序;(d)表示L产生的哈密顿回路H;(e)是G的一个最小费用旅行售货员回路。

    当费用函数满足三角不等式时,该算法具有较好的性能比,即对于无向图G,算法具有常数性能比2.以下参考屈老师课件。

    对于一般货郎问题,换句话说,若P≠NP,则对任意常数ρ>1,不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。

    参考:北大《算法设计与分析》公开课(https://www.bilibili.com/video/BV1e4411x7Qj?p=4)

    王晓东《算法设计与分析》第二版

    展开全文
  • 旅行售货员问题分支界限法package test;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;/*** Created by saishangmingzhu on 2018/12/13.* 旅行售货...

    旅行售货员问题分支界限法

    package test;

    import java.util.ArrayList;

    import java.util.Collections;

    import java.util.Comparator;

    import java.util.List;

    /**

    * Created by saishangmingzhu on 2018/12/13.

    * 旅行售货员问题

    */

    public class TravellingSalesmanProblem {

    //图

    private int[][] pointIndex=new int[][]{

    {0,30,6,4},

    {30,0,5,10},

    {6,5,0,20},

    {4,10,20,0}};

    public static void main(String[] arg){

    new TravellingSalesmanProblem().branchAndBoundMethod();

    }

    /**

    * 分支界限法-优先队列式

    * 优先队列式求解时,到达第一个没有子结点的活结点时,即为最优解

    */

    public void branchAndBoundMethod() {

    List pointList=new ArrayList<>();

    pointList.add(new Point(0,"1"));

    pointList.add(new Point(1,"2"));

    pointList.add(new Point(2,"3"));

    pointList.add(new Point(3,"4"));

    Node root=new Node();

    root.point=pointList.get(0);

    root.childPointList.addAll(pointList);

    root.childPointList.remove(root.point);

    Node minNode=new Node();

    minNode.value=Integer.MAX_VALUE;

    List currentLiveNodeList=new ArrayList<>();

    currentLiveNodeList.add(root);

    while (currentLiveNodeList.size()>0) {

    Node liveNode = currentLiveNodeList.get(0);

    List childPointList = liveNode.childPointList;

    for (Point childPoint : childPointList) {

    int value=pointIndex[childPoint.index][liveNode.point.index];

    if (value!=0) {

    Node childNode = new Node();

    childNode.parentNode=liveNode;

    childNode.point = childPoint;

    childNode.childPointList.addAll(childPointList);

    childNode.childPointList.remove(childPoint);

    childNode.value = liveNode.value + value;

    if (childNode.childPointList.size() == 0 ) {

    if (pointIndex[0][childPoint.index] != 0) {

    childNode.value += pointIndex[0][childPoint.index];

    if (childNode.value

    minNode.value=childNode.value;

    minNode.point=childNode.point;

    minNode.parentNode=childNode.parentNode;

    }

    } else {

    continue;

    }

    }

    currentLiveNodeList.add(childNode);

    }

    }

    currentLiveNodeList.remove(liveNode);

    Collections.sort(currentLiveNodeList, new Comparator() {

    @Override

    public int compare(Node o1, Node o2) {

    return o2.value-o1.value;

    }

    });

    }

    System.out.println(minNode.value);

    getParents(minNode);

    }

    private void getParents(Node node){

    if (node==null){

    return;

    }

    getParents(node.parentNode);

    System.out.println(node.point.name);

    }

    class Node{

    private Node parentNode;

    private Point point;

    private List childNodeList=new ArrayList<>();

    private List childPointList=new ArrayList<>();

    private int value;

    }

    class Point{

    private int index;

    private String name;

    public Point(int index, String name) {

    this.index = index;

    this.name = name;

    }

    }

    }

    ©著作权归作者所有:来自51CTO博客作者塞上名猪的原创作品,如需转载,请注明出处,否则将追究法律责任

    展开全文
  • 问题描述:某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。算法描述:回溯法,序列树,假设起点为 1。算法开始时 x = [1, ...

    问题描述:

    某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。

    算法描述:

    回溯法,序列树, 假设起点为 1。

    算法开始时 x = [1, 2, 3, ..., n]

    x[1 : n]有两重含义 x[1 : i]代表前 i 步按顺序走过的城市, x[i + 1 : n]代表还未经过的城市。利用Swap函数进行交换位置。

    若当前搜索的层次i = n 时,处在排列树的叶节点的父节点上,此时算法检查图G是否存在一条从顶点x[n-1] 到顶点x[n] 有一条边,和从顶点x[n] 到顶点x[1] 也有一条边。若这两条边都存在,则发现了一个旅行售货员的回路即:新旅行路线),算法判断这条回路的费用是否优于已经找到的当前最优回路的费用bestcost,若是,则更新当前最优值bestcost和当前最优解bestx。

    若i < n 时,检查x[i - 1]至x[i]之间是否存在一条边, 若存在,则x [1 : i ] 构成了图G的一条路径,若路径x[1: i] 的耗费小于当前最优解的耗费,则算法进入排列树下一层,否则剪掉相应的子树。

    代码实现:

    #include

    using namespacestd;const int max_ = 0x3f3f3f;const int NoEdge = -1;intcitynum;intedgenum;intcurrentcost;intbestcost;int Graph[100][100];int x[100];int bestx[100];voidInPut()

    {intpos1, pos2, len;

    scanf("%d %d", &citynum, &edgenum);

    memset(Graph, NoEdge,sizeof(Graph));for(int i = 1; i <= edgenum; ++i)

    {

    scanf("%d %d %d", &pos1, &pos2, &len);

    Graph[pos1][pos2]= Graph[pos2][pos1] =len;

    }

    }voidInitilize()

    {

    currentcost= 0;

    bestcost=max_;for(int i = 1; i <= citynum; ++i)

    {

    x[i]=i;

    }

    }void Swap(int &a, int &b)

    {inttemp;

    temp=a;

    a=b;

    b=temp;

    }void BackTrack(int i) //这里的i代表第i步去的城市而不是代号为i的城市

    {if(i ==citynum)

    {if(Graph[x[i - 1]][x[i]] != NoEdge && Graph[x[i]][x[1]] != NoEdge && (currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]] < bestcost || bestcost ==max_))

    {

    bestcost= currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]];for(int j = 1; j <= citynum; ++j)

    bestx[j]=x[j];

    }

    }else{for(int j = i; j <= citynum; ++j)

    {if(Graph[x[i - 1]][x[j]] != NoEdge && (currentcost + Graph[x[i - 1]][x[j]] < bestcost || bestcost ==max_))

    {

    Swap(x[i], x[j]);//这里i 和 j的位置交换了, 所以下面的是currentcost += Graph[x[i - 1]][x[i]];

    currentcost += Graph[x[i - 1]][x[i]];

    BackTrack(i+ 1);

    currentcost-= Graph[x[i - 1]][x[i]];

    Swap(x[i], x[j]);

    }

    }

    }

    }voidOutPut()

    {

    cout<< "路线为:" <

    cout<< bestx[i] << " ";

    cout<< "1" <

    }intmain()

    {

    InPut();

    Initilize();

    BackTrack(2);

    OutPut();

    }

    View Code

    测试样例:

    实现结果:

    参考:王晓东《算法设计与分析》

    展开全文
  • 旅行售货员问题即给几个地点,相互之间有路径,有每个路径对应的消耗的费用。我们将起点设为1,其他地点设为2,3,4…n。我们起初将所有路径费用都设置成∞,然后再输入 相通路径的费用,再更新费用值。我们以下图为...

    旅行售货员问题即给几个地点,相互之间有路径,有每个路径对应的消耗的费用。我们将起点设为1,其他地点设为2,3,4…n。我们起初将所有路径费用都设置成∞,然后再输入 相通路径的费用,再更新费用值。我们以下图为例。如下图:
    在这里插入图片描述

    注意BackTrack主要是一个求排列组合函数(排列组合函数思路见“递归分治——排列组合”博客),加上了路径和费用回溯。代码如下(适用于旅行售货员问题无向图)主要代码端在BackTraack处:

    //回溯法
    //旅行售货员问题
    class TraveLing
    {
    private:
    	int n;          // 顶点个数
    	vector<vector<int>> a;       // 图的邻接矩阵
    	int* x;         // 记录当前路径
    	int* bestx;  // 最优解路径
    	int   cc;       // 当前费用
    	int   bestc;  // 最优解费用
    
    	void BackTrack(int i)//排列组合
    	{
    		if (i == n)//递归出口
    		{
    			if (a[x[n - 1]][x[n]] != INT_MAX && 
    			a[x[n][x[1]] != INT_MAX && 
    			(cc + a[x[n - 1]][x[n]] + a[x[n]][x[1]] < bestc))//当前路径比之前路径费用少
    			{
    				for (int j = 1; j < n+1; ++j)
    				{
    					bestx[j] = x[j];//更新目前最优路径 ,注意bestx和x都是从下标1开始用的,下标0我们实际不用
    				}
    				bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][x[1]];
    			}
    		}
    		else
    		{
    			for (int j = i; j <= n; ++j)
    			{
    				if (a[x[i - 1]][x[i]] != INT_MAX && 
    				cc + a[x[i - 1]][x[i]] < bestc ||
    				 bestc == INT_MAX)
    				{
    					swap(x[i], x[j]);
    					cc += a[x[i - 1]][x[i]];
    					BackTrack(i + 1);
    					cc -= a[x[i - 1]][x[i]];//递归回退就回溯
    					swap(x[i], x[j]);
    				}
    			}
    		}
    	}
    public:
    	TraveLing(int sum) :n(sum), cc(0), bestc(INT_MAX)
    	{
    		x = new int[n + 1];//多申请一个空间,我们从下标1开始用,下标0实际不用
    		bestx = new int[n + 1];//多申请一个空间,我们从下标1开始用,下标0实际不用
    		for (int i = 1; i < n+1 ; i++)
    		{
    			x[i] = i;//当前路径初始化为1,2,3...n,注意x的0下标我们实际不用
    			bestx[i] = 1;//当前最优解路径初始化为11111...
    		}
    
    		a.resize(n + 1);//初始化邻接矩阵,并且每个路径都初始化为最大值,为了逻辑清晰一点,下标0没有实际用
    		for (int i = 0; i < n + 1; i++)
    		{
    			a[i].resize(n + 1);
    		}
    		for (int i = 0; i < n + 1; i++)
    		{
    			for (int j = 0; j < n + 1; j++)
    			{
    					a[i][j] = INT_MAX;
    			}
    		}
    
    		//输入每两个地点和这两个地点消耗的费用
    		cout << "please input 'way1' to 'way1' and 
    		'cost'if way1 < 1 or way2 < 1 or cost < 0 
    		 end:\n";
    		int u = 1;
    		int v = 1;
    		int w = 0;
    		while (u >= 1 && v >= 1 && w >= 0)
    		{
    			cin >> u >> v >> w;
    			a[u][v] = w;
    			a[v][u] = w;
    		}
    
    		BackTrack(2);//传入2 是因为我们从起点1出发,只需要对地点2开始到n这些地点进行排列组合
    	}
    	
    	~TraveLing()
    	{
    		delete[] x;
    		delete[] bestx;
    	}
    
    	void PrintBestx()//打印最优解路径
    	{
    		for (int i = 1; i < n+1; i++)
    		{
    			cout << bestx[i] << " ";
    		}
    		cout << "1";//路径结束后肯定回到起点1
    		cout << endl;
    	}
    
    	int GetBestc()//获取最优解路径下的费用
    	{
    		return bestc;
    	}
    };
    
    int main()
    {
    	TraveLing tra(4);
    	tra.PrintBestx();
    	cout << tra.GetBestc() << endl;
    
    	return 0;
    }
    
    

    运行截图:
    在这里插入图片描述

    展开全文
  • 分支限界法 旅行售货员 问题 分支限界法之旅行售货员 旅行售货员问题 分支限界法之旅行售货员问题
  • /**************************************************************** 5.9 旅行售货员问题* 旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成 1, 2, 3, .., n* 的所有排列的递归算法 perm 类似。...
  • 旅行售货员问题-回溯法

    千次阅读 多人点赞 2020-06-22 16:05:12
     某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。       结果为: 1 3 2 4 1 算法描述: 回溯法,序列树, 假设...
  • 旅行售货员问题 某售货员要到若干城市去推销商品,已知各城市之间的路程(旅费),他要 选定一条从驻地出发,经过每个城市一遍,最后回到驻地的路线,使总的路程(总 旅费)最小。 求解思想: 旅行售货员问题的解...
  • 这是一个用C语言实现的旅行售货员问题,用的是分支限界法,是在Dev-C++下编写的。
  • 1 -1 -1 -1 -1 -1 1 -1 -1 9 -1 -1 -1 -1 -1 -1 output 31 //旅行售货员问题 #include #define MAXSIZE 100 using namespace std; int n; int graph[MAXSIZE][MAXSIZE]; int c=0; int bestc=0; int x[MAXSIZE]; int ...
  • 摘 要旅行售货员问题是一个古老而典型的组合优化问题。对该问题合理而有效的解法不但有重要的理论和学术意义,同时对众多工程实际中的应用提供了重要的指导意义。这篇论文首先对问题进行了大体的陈述,对其进行了...
  • TSP旅行售货员问题-回溯法 最近比较颓废,考试实在是太多了,月考简直了。对转专业的学生太不友好了。一大堆公共课简直消磨了我对编程的热情。 今天刚好去听了节一直逃课的晚课,老师找我谈了谈,没有怪我。我也...
  • 旅行售货员问题 算法分析与设计 解决实际问题
  • 旅行售货员问题一、基本介绍二、问题解法2.1 枚举法(穷举法)2.2 回溯法2.3 分支限界法2.4 旅行售货员问题近似算法三、总结 一、基本介绍 设有n个城镇,已知每两个城镇之间的距离,一个售货员从某一城镇出发巡回...
  • java编写的旅行售货员问题算法,实现不同地点之间的最短路径的选择!
  • #includeusingnamespacestd;constintINF=10000000;intn,cc=0,bestc=INF;//n表示几个点,cc表示当前的距离bestc表示最优的距离,bests//开始时赋值最大值int**g;//二维数组g中存储各点间距离int*x,*bestx;...
  • 用回溯法解决旅行售货员问题 java语言实现
  • 利用分支界限法求解旅行售货员问题(只有java代码) 下面代码采用的是一般的dfs解法(为什么会列出这个解法呢,因为我了解分支界限法之前只会这个解法,咳咳) 求出的是满足条件的所有解,然后才选取其中一种(dfs)...
  • 用枚举法实现的旅行售货员问题 NP问题 可以处理有向图的矩阵
  • #include #include using namespace std; const int noEdge=65535; class Traveling { public: void BackTrack(int i); int n;... cout旅行售货员问题的最优值为:"(vector,v,n); }
  • 回溯法求解旅行商问题回溯法和最近邻法的区别是,回溯法可以求得全局最优解,而最近邻法求得的是近似优解。不过,由于回溯法的时间复杂度为O(n²),所以城市数量非常多时仍然不太适用。代码:# -*- coding: utf-8 -*...
  • 关于旅行售货员问题,有多个版本的描述。这里小编选择了一种题目描述 在瓦罗兰大陆上,蕴含着强大能量的符文散落在各地。作为召唤师的你需要收集n个铭文来强化自身。现在给出你n个符文的坐标,假设起始点在(0,0),请...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,465
精华内容 586
关键字:

旅行售货员