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

    /***************************************************************

    *                  5.9 旅行售货员问题

    *  旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成 1, 2, 3, .., n

    *  的所有排列的递归算法 perm 类似。开始时 x = [1, 2, .., n], 相应的排列

    *  树由 x[1 .. n] 的所有排列构成。

    */

    public class TravelSeller {

    static int n; // 图G的顶点数

    static int[] x; // 当前解

    static int[] bestx; // 当前最优解

    static int bestc; // 当前最优值

    static int cc; // 当前费用

    static int[][] a; // 图G的邻接矩阵

    public static int travelSeller(int[][] matrix, int[] v) {

    n = matrix.length;

    a = matrix;

    //置 x 为单位排列

    x = new int[n];

    bestx = v;

    bestc = Integer.MAX_VALUE;

    cc = 0;

    trackback(1);   //由于起点固定

    return 0;

    }

    private static void swap(int[] array, int i, int j) {

    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;

    }

    private static void trackback(int i) {

    if (i == n - 1) {

    if (a[x[i - 1]][i] < Integer.MAX_VALUE

    && a[x[i]][0] < Integer.MAX_VALUE

    && (bestc == Integer.MAX_VALUE || cc + a[x[i - 1]][x[i]]

    + a[x[i]][0] < bestc)) {

    for (int j = 0; j < n; j++) {

    bestx[j] = x[j];

    }

    bestc = cc + a[x[i - 1]][x[i]] + a[x[i]][0];

    }

    } else {

    for (int j = i; j < n; j++) {

    //是否可以进入 x[j] 子树

    if (a[x[i - 1]][x[j]] < Integer.MAX_VALUE && (bestc == Integer.MAX_VALUE || cc + a[x[i - 1]][x[j]] < bestc)) {

    //搜索子树

    swap(x, i, j);

    cc += a[x[i - 1]][x[i]];

    trackback(i + 1);

    cc -= a[x[i - 1]][x[i]];

    swap(x, i, j);

    }

    }

    }

    }

    }

    展开全文
  • 旅行售货员问题

    千次阅读 2018-10-03 22:54:49
     某售货员要到4个城市去推销商品,已知各城市之间的路程,如右图所示。 请问他应该如何选定一条从城市1出发,经过每个城市一遍,最后回到城市1的路线,使得总的周游路程最小?并分析所设计算法的计算时间复杂度...
  • 回溯法之旅行售货问题 回溯法 旅行售货员 回溯法之旅行售货员
  • 摘 要旅行售货员问题是一个古老而典型的组合优化问题。对该问题合理而有效的解法不但有重要的理论和学术意义,同时对众多工程实际中的应用提供了重要的指导意义。这篇论文首先对问题进行了大体的陈述,对其进行了...
  • 这是一个用C语言实现的旅行售货员问题,用的是分支限界法,是在Dev-C++下编写的。
  • 旅行售货员问题-回溯法

    千次阅读 多人点赞 2020-06-22 16:05:12
     某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。       结果为: 1 3 2 4 1 算法描述: 回溯法,序列树, 假设...
  • 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树,裁剪那些不能得到最优解的子树以提高搜索效率。 分支界限法解题的一般思路: (1)分支限界法的求解目标则是找出满足约束条件的一个...
  • 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个城镇,已知每两个城镇之间的距离,一个售货员从某一城镇出发巡回...
  • #includeusingnamespacestd;constintINF=10000000;intn,cc=0,bestc=INF;//n表示几个点,cc表示当前的距离bestc表示最优的距离,bests//开始时赋值最大值int**g;//二维数组g中存储各点间距离int*x,*bestx;...
  • java编写的旅行售货员问题算法,实现不同地点之间的最短路径的选择!
  • 旅行售货员问题 算法分析与设计 解决实际问题
  • 用枚举法实现的旅行售货员问题 NP问题 可以处理有向图的矩阵
  • 回溯法求解旅行问题回溯法和最近邻法的区别是,回溯法可以求得全局最优解,而最近邻法求得的是近似优解。不过,由于回溯法的时间复杂度为O(n²),所以城市数量非常多时仍然不太适用。代码:# -*- coding: utf-8 -*...
  • 1.利用回溯法求解01背包问题。 对于N个物品,在背包的总体积的限制下,有些物品肯定是该舍弃的。 对于每件物品都有取和不取俩种情况。 我们把所有的情况遍历一次,最后取最优的结果。 总体上来就是暴力枚举求最优解...

空空如也

空空如也

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

旅行售货员问题