精华内容
下载资源
问答
  • 旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线...
  • 回溯算法旅行问题代码实现。算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次,每次更新bestx需计算时间O(n),从而整个算法的计算时间复杂性为O(n!)。
  • 旅行售货员问题-回溯法

    千次阅读 多人点赞 2020-06-22 16:05:12
     某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。       结果为: 1 3 2 4 1 算法描述: 回溯法,序列树, 假设...

    问题描述

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

      结果为: 1 3 2 4 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] 的耗费小于当前最优解的耗费,则算法进入排列树下一层,否则剪掉相应的子树。


    递归回溯

    • 回溯法对解空间作深度优先搜索
    • 通常用递归方法实现回溯法

    在这里插入图片描述

    void backtrack (int t)
    {
           if (t>n) output(x);// t>n时已搜索到一个叶结点, output(x)对得到的可行解x进行记录或输出处理.
           else{                                     
             for (int i=f(n,t);i<=g(n,t);i++) { // 函数f和g分别表示在当前扩展结点处未搜索子树的起止编号.                            
               x[t]=h(i); //h(i)表示在当前扩展结点处x[t]的第i个可选值
               if (constraint(t)&&bound(t)) backtrack(t+1);
             } //for循环结束后, 已搜索遍当前扩展结点的所有未搜索子树.
           }
    } //Backtrack(t)执行完毕, 返回t-1层继续执行, 对未测试过的x[t-1]的值继续搜索.
    
    • if (Constraint(t)&&Bound(t) ) Backtrack(t + 1);if语句含义:Constraint(t)和Bound(t)表示当前扩展节点处的约束函数和限界函数。
    • Constraint(t): 返回值为true时,在当前扩展节点处x[1:t]的取值问题的约束条件,否则不满足问题的约束条件,可剪去相应的子树
    • Bound(t): 返回的值为true时,在当前扩展节点处x[1:t]的取值为时目标函数越界,还需由Backtrack(t+1)对其相应的子树做进一步搜索。否则,当前扩展节点处x[1:t]的取值是目标函数越界,可剪去相应的子树
    • for循环作用:搜索遍当前扩展的所有未搜索过的子树。
    • 递归出口:Backtrack(t)执行完毕,返回t-1层继续执行,对还没有测试过的x[t-1]的值继续搜索。当t=1时,若以测试完x[1]的所有可选值,外层调用就全部结束。

    迭代回溯

      采用树的非递归深度优先遍历算法,可将回溯法表示为一个非递归迭代过程。

    void iterativeBacktrack ( )
    {
      int t=1;
      while (t>0) {
        if (f(n,t)<=g(n,t)) 
          for (int i=f(n,t);i<=g(n,t);i++) {// 函数f和g分别表示在当前扩展结点处未搜索子树的起止编号.
            x[t]=h(i);
            if (constraint(t)&&bound(t)) {
              if (solution(t)) output(x); //solution(t)判断当前扩展结点处是否已得到问题的一个可行解                                       
              else t++;} //solution(t)为假,则仅得到一个部分解,需继续纵深搜索
            }
        else t--;
      } //while循环结束后,完成整个回溯搜索过程
    }
    

    子集树与排列树

    • 子集树: 所给的问题是从n个元素的集合中找出满足某种性质的子集时, 相应的解空间称为子集树.

      子集树通常有2n个叶结点, 遍历子集树的任何算法均需Ω(2n)的计算时间.

      例如: 0-1背包问题的解空间为一棵子集树.

    • 排列树: 当所给的问题是确定n个元素满足某种性质的排列时, 相应的解空间称为排列树.

      排列树通常有(n-1)!个叶结点, 遍历排列树需要Ω(n!)的计算时间.

      例如: 旅行售货员问题的解空间为一棵排列树.

    在这里插入图片描述


    代码实现

    #include <bits/stdc++.h>
    using namespace std;
    const int max_ = 0x3f3f3f;   //定义一个最大值
    const int NoEdge = -1;      //两个点之间没有边
    int citynum;                //城市数
    int edgenum;                //边数
    int currentcost;            //记录当前的路程
    int bestcost;               //记录最小的路程(最优)
    int Graph[100][100];        //图的边距记录
    int x[100];                 //记录行走顺序
    int bestx[100];             //记录最优行走顺序
    
    void InPut()
    {
        int pos1, pos2, len;     //点1 点2 距离
    
        cout<<"请输入城市数和边数(c e):";
        cin>>citynum>>edgenum;
    
        memset(Graph, NoEdge, sizeof(Graph));
    
        cout<<"请输入两座城市之间的距离(p1 p2 l):"<<endl;
        for(int i = 1; i <= edgenum; ++i)
        {
            cin>>pos1>>pos2>>len;
            Graph[pos1][pos2] = Graph[pos2][pos1] = len;
        }
    }
    
    //初始化
    void Initilize()
    {
        currentcost = 0;
        bestcost = max_;
        for(int i = 1; i <= citynum; ++i)
        {
            x[i] = i;
        }
    }
    
    
    void Swap(int &a, int &b)
    {
        int temp;
        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]);
                }
            }
        }
    }
    
    void OutPut()
    {
        cout<<"最短路程为:"<<bestcost<<endl;
        cout << "路线为:" << endl;
        for(int i = 1; i <= citynum; ++i)
            cout << bestx[i] << " ";
        cout << "1" << endl;
    }
    
    
    int main()
    {
        InPut();
        Initilize();
        BackTrack(2);
        OutPut();
    }
    
    



    样例测试

    以前面的样例示范

    输入

    请输入城市数和边数(c e):4 6
    请输入两座城市之间的距离(p1 p2 l):
    1 2 30
    1 3 6
    1 4 4
    2 4 10
    2 3 5
    3 4 20


    输出
    最短路程为:25
    路线为:
    1 3 2 4 1
    在这里插入图片描述

    展开全文
  • 旅行售货员问题即给几个地点,相互之间有路径,有每个路径对应的消耗的费用。我们将起点设为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;
    }
    
    

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

    展开全文
  • 回溯法之旅行售货问题 回溯法 旅行售货员 回溯法旅行售货员
  • TSP旅行售货员问题-回溯法 最近比较颓废,考试实在是太多了,月考简直了。对转专业的学生太不友好了。一大堆公共课简直消磨了我对编程的热情。 今天刚好去听了节一直逃课的晚课,老师找我谈了谈,没有怪我。我也...

    TSP旅行售货员问题-回溯法

    最近比较颓废,考试实在是太多了,月考简直了。对转专业的学生太不友好了。一大堆公共课简直消磨了我对编程的热情。
    今天刚好去听了节一直逃课的晚课,老师找我谈了谈,没有怪我。我也开始思考我目标是什么,我好像很忙,但是没有目标。很盲目
    仔细思考了一下,我就是喜欢比较简单的生活。有时间做自己的事情,发展一下兴趣爱好。但现在学业都快压得我喘不过气,而且我深知学校教的很多课根本就没有用。但是我还是得去,浪费时间。我还是觉得应该追寻自己的本心。人生是短暂的。连喜欢的事情都做不了就太可悲了。转换一下思想以后,感觉其实我还是迷茫。希望开心每一天吧。

    讲了这么多废话接下来看一看题目吧
    在这里插入图片描述

    旅行商问题

    旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。从图论的角度来看,该问题实质是在一个带权完全无向图中,找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等

    • 我这题是用的回溯算法

    算法的思想很简单就是深搜
    先来看一下解集树
    在这里插入图片描述
    在这里插入图片描述
    简单来说就是新加入路径以后看是否符合条件,也就是让length符合最小同时要存在可行路径,符合就swap,为什么要swap。swap可以把加入的点换到加入位置,也就是变相描绘出了路径。
    也不细说了,用的代码也比较简单易懂。
    主要是太累了,懒得写(狗头)

    #include <iostream> 
    using namespace std; 
    #define N 100
    int n;//城市个数 
    int d[N+1][N+1]; //邻接矩阵 
    int x[N];//存放顶点号 
    int best[N]; //最优路径 
    int len_now; //当前路径长度 
    int length=0;//最优距离 
    
    void TSP(int t) 
    { 
    	 if(t>n) //到叶子节点 
    	 { 
    	    //如果最后一个城市与出发的城市之间有路径,且当前总距离比最优值小,则更新最优值 
    		 if(d[x[n]][x[1]] > 0 && len_now+d[x[n]][x[1]] < length || length==0)
    		 { 
    			 length=len_now+d[x[n]][x[1]]; 
    			 for(int j=1; j<=n; j++) 
    				 best[j]=x[j];  
    		 } 
    	 } 
         //没有搜索到叶子结点
    	 else 
    	 { 
    		 for(int i=t;i<=n;i++) 
    		 {
    		 	//如果第t-1个城市与第i个城市之间有路径,且当前总距离比最优值小,则更新最优值 
    			 if(d[x[t-1]][x[i]] > 0 && len_now + d[x[t-1]][x[i]] < length || length==0)
    			 { 
    				swap(x[t],x[i]); 
    				len_now+=d[x[t-1]][x[t]];  
    				TSP(t+1); //递归判断其余节点 
    				len_now-=d[x[t-1]][x[t]]; //回溯 
    				swap(x[t],x[i]); 
    			} 
    		} 
    	} 
    } 
    
    int main()
    { 
    	int i,j; 
    	while(cin>>n)
        {
            //输入图,构造邻接矩阵
    		for(i=1;i<=n;i++) 
    			for(j=1;j<=n;j++) 
    				cin>>d[i][j]; 
    		
    		for(i=1;i<=n;i++) 
    			x[i]=i; 
    		TSP(2);		
    		//cout<<"\n最终最优解为:"<<endl;
            cout<<length<<endl;
    		for(int k=1;k<=n;k++) 
    			cout<<best[k]<<" "; 
    
    	} 
    	return 0; 
    } 
    
    
    展开全文
  • 主要介绍了Python基于回溯法子集树模板解决旅行问题(TSP),简单描述了旅行问题并结合实例形式分析了Python使用回溯法子集树模板解决旅行问题的相关实现步骤与操作技巧,需要的朋友可以参考下
  • #include <stdio.h> #include <bits/stdc++.h> using namespace std; #define maxn 1000 #define NoEdge 0x3f3f3f int m;//路径数 int n;//顶点数 int road[maxn][maxn]= {NoEdge};...int bestl=NoEdg
    #include <stdio.h>
    #include <bits/stdc++.h>
    using namespace std;
    #define maxn 1000
    #define NoEdge 0x3f3f3f
    
    int m;//路径数
    int n;//顶点数
    int road[maxn][maxn]= {NoEdge}; //路径的邻接矩阵
    int x[maxn];//当前解
    int bestx[maxn];//最优解
    int l;//当前路径长度
    int bestl=NoEdge;//最优路径长度
    
    
    void BackTrack(int i)
    {
        if(i==n)//到达叶子节点
        {
            if(road[x[i-1]][x[i]]!=NoEdge&&road[x[1]][x[i]]!=NoEdge&&l+road[x[i-1]][x[i]]+road[1][x[i]]<bestl)
            {//n-1到n之间1到n之间存在路径并且改回路长度比最优解短,则记录当前解为最优解
                for(int j=1; j<=n; j++)
                {
                    bestx[j]=x[j];
                }
                bestl=l+road[x[n-1]][x[n]]+road[1][x[n]];
            }
    
        }
        else//未到达叶子节点
        {
            for(int j=i; j<=n; j++)//没走过的路径遍历一遍
            {
                //i-1到j之间有路径并且当前路径长度加上i-1到j的距离比当前最短路径短
                if(road[x[i-1]][x[j]]!=NoEdge&&l+road[x[i-1]][x[j]]<bestl)
                {
                    swap(x[i],x[j]);//将j交换到i的位置
                    l+=road[x[i-1]][x[i]];//记录当前路径长度
                    BackTrack(i+1);//继续下一层
                    l-=road[x[i-1]][x[i]];//返回上一层
                    swap(x[i],x[j]);//将路径位置调回原位置,保证搜索顺序与解空间树一致(可省略)
                }
    
            }
        }
    }
    /*测试用例
    4 6
    1 2 30
    1 3 6
    1 4 4
    2 3 5
    2 4 10
    3 4 20
    */
    int main()
    {
        cout<<"输入城市个数及路径条数:"<<endl;
        cin>>n>>m;
        for(int i=1; i<=n; i++)
        {
            x[i]=i;
        }
        int a,b,c;
        printf("输入存在路径的两点及路径长度:\n");
        for(int i=0; i<m; i++)
        {
            cin>>a>>b>>c;
            road[a][b]=c;
            road[b][a]=c;
        }
        BackTrack(2);
        cout<<endl<<"最优路径为:"<<endl;
        for(int i=1; i<=n; i++)
            cout<<bestx[i]<<" -> ";
        cout<<"1"<<endl;
        cout<<endl<<"最优路径长度为:";
        cout<<endl<<bestl<<endl;
    
    
    }
    
    
    展开全文
  • java版经典算法 旅行售货员 这个只有代码,没有可视化界面的~因为界面不是在所有的环境下都可以通过运行,所以只上传了代码!注意啊
  • 旅行售货员问题-回溯法-深度搜索

    万次阅读 2018-05-06 16:33:40
    问题描述:某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。算法描述:回溯法,序列树, 假设起点为 1。算法开始时 x = [1...
  • 思路是回溯法,具体如下: 假设城市=4,出发地=1城市,那么所有可能如下: 1->2->3->4->1 1->2->4->3->1 1->3->2->4->1 1->3->4->2->1 1->4->3->2->1 ...
  • 回溯法解决旅行售货员问题 java语言实现
  • #include #include using namespace std; const int noEdge=65535; class Traveling { public: void BackTrack(int i); int n;... cout旅行售货员问题的最优值为:"(vector,v,n); }
  • 该题利用回溯法求解,此时需要确定解空间的类型:我们可以知道该解空间为一棵排列树。我们假设初始的一条路线为x,x中的值为 1,2,3,……,n,表示该路线为由城市1依次经过城市2、3……到n后再回到城市1(当然是...
  • 旅行售货员问题回溯法求解

    万次阅读 2016-05-04 21:22:37
    旅行售货员问题的解空间是一颗排序树,对于排序树的回溯法搜索与生成1,2,3,4,...,n的所有排列的递归算法Perm类似,开始时,x = [1,2,...,n],则相应的排序树由x[1:n]的所有排序构成。以下解释排序算法Perm: (1...
  • #includeusingnamespacestd;constintINF=10000000;intn,cc=0,bestc=INF;//n表示几个点,cc表示当前的距离bestc表示最优的距离,bests//开始时赋值最大值int**g;//二维数组g中存储各点间距离int*x,*bestx;...
  • 回溯法_旅行售货员问题

    千次阅读 2016-12-20 17:01:55
    回溯法_旅行售货员问题 * * @author Matt */ public class Bttsp { static int n = 4; // 城市数量 static int[] x; // 当前路径 static int[] bestx; // 最优路径 static float bestc; // 最少花费 static...
  • 旅行售货员问题回溯法笔记

    千次阅读 2019-10-20 09:52:21
    旅行员售货问题 ...旅行售货员问题的解空间是一棵排列树。对于排列树的回溯法与生成1,2,……n的所有排列的递归算法Perm类似。开始时x=[1,2,……n],则相应的排列树有x[1:n]的所有排列构成。 在递归算法Backtrac...
  • 旅行售货员问题回溯法实现)

    千次阅读 2017-03-18 21:29:24
    本人第一次写博客,为了把自己的... * 回溯算法  *   * @author Ming  *   */ public class BackTrackTest { private static int n; // 图的顶点 private static int[] x; // 当前解 public stat
  • 07回溯法-旅行售货员问题 **问题描述:**已知有m个城市,城市之间由n条不同长度的道路相连。一个售货员从一座城市出发,途径所有城市,并最终回到原点,设计算法计算售货员所走的最短路径结点。 **问题分析:**从...
  • 回溯法----旅行售货员问题java算法

    千次阅读 2018-04-21 15:22:37
    原文:...分支限界----旅行售货员问题&gt; 二、代码实现 程序实现了 递归回溯 解决该问题 迭代回溯算法仍在考虑中...[cpp] view plain copy/******************************...
  • 由于只有4个城市,如果规定售货员总是从城市1出发,那么依据排列组合可以得到6种不同的旅行方案,比如12341、13241等等。在这些排列组合基础上可以很容易绘制出一棵排列树,也是该问题的解空间树,排列树如下: ...
  • 回溯法思想和案例(旅行售货员问题,装载问题, 0-1背包问题,图的m着色问题)。 算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
  • 全排列回溯 #include <iostream> using namespace std; const int max_ = 0x3f3f3f; //定义一个最大值 const int NoEdge = -1; //两个点之间没有边 int citynum; //城市数 int edgenum; //边数 int ...
  • 问题描述:某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。 算法描述:回溯法,序列树, 假设起点为 1,算法开始时 x =...
  • 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 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 574
精华内容 229
关键字:

旅行售货员问题回溯法