精华内容
下载资源
问答
  • 旅行售货商问题是高校大一计算概论课程习题集中的一个属于递归学习范畴的经典c语言问题,对于旅行售货商问题用带有剪枝的递归法进行解决,普通的递归方法会导致程序运行超时。
  • 旅行售货商问题

    2020-02-22 13:52:46
    17 旅行售货商问题 描述 一个国家有 n 个城市,每两个城市之间都开设有航班,从城市 i 到城市 j 的航班价格为 cost[i, j] ,而且往、返航班的价格相同。 售货商要从一个城市出发,途径每个城市 1 次(且每个城市只能...

    17 旅行售货商问题

    描述

    一个国家有 n 个城市,每两个城市之间都开设有航班,从城市 i 到城市 j 的航班价格为 cost[i, j] ,而且往、返航班的价格相同。

    售货商要从一个城市出发,途径每个城市 1 次(且每个城市只能经过 1 次),最终返回出发地,而且他的交通工具只有航班,请求出他旅行的最小开销。

    关于输入

    输入的第 1 行是一个正整数 n (3 <= n <= 15)
    然后有 n 行,每行有 n 个正整数,构成一个 n * n 的矩阵,矩阵的第 i 行第 j 列为城市 i 到城市 j 的航班价格。

    关于输出

    输出数据为一个正整数 m,表示旅行售货商的最小开销

    例子输入
    4
    0 4 1 3
    4 0 2 1
    1 2 0 5
    3 1 5 0
    
    例子输出

    7

    分析

    本题初看是一个非常简单的递归问题,直接使用递归写出来再改成记忆化搜索即可。然而这种方法有一个致命的错误,就是剩余的城市数目代表不了当前的状况dp数组中的某一维度不能仅仅使用待访问的城市数目来体现,而是要使用剩下的城市的集合来体现

    那么我们如何表示这个集合呢?答案是使用二进制数来表示。例如我们有 { 1 , 2 , 3 } \{1,2,3\} {1,2,3}这个集合,表示我们还有1号、2号、3号城市待访问,那么我们用一个二进制数的第1、2、3位分别表示这个集合中元素的状态,集合中如果存在 i i i号城市,那么这个集合对应的二进制数的第二位(从后往前数)就是1,否则为0

    事实上,也可以用剪枝来做,但是注意由于城市之间的旅行价格一定会大于0,所以在剪枝的过程中可以加一个下界限剪枝:如果剩余n个城市,那么最小的钱+n,进行剪枝

    代码实现
    #include<iostream>
    using namespace std;
    int n;
    bool visited[16] = { false };
    int price[16][16] = { 0 };
    int dp[16][32768] = { 0 };
    
    int getNum(int c, int bina_num)// 返回bina_num集合中从后往前数的第c个非0数
    {
    	int result = 0, i = 0;
    	while (c > 0)
    	{
    		if (((bina_num >> i) & 1) == 1)c--;
    		i++;
    	}
    	return i;
    }
    
    int FlipNum(int c, int bina_num)//将bina_num从后往前数的第c个数反转
    {
    	bina_num ^= (1 << (c - 1));
    	return bina_num;
    }
    
    int f(int c, int m)//当前在c,从c开始,接着走剩下的城市用的最小的钱,m是一个二进制数,存储了剩下的没有走的城市
    {
    	if (dp[c][m] != 0)
    	{
    		return dp[c][m];
    	}
    	if (m == 1)//走完了,回到起点
    	{
    		dp[0][(0 << c)] = price[0][c];
    		return price[1][c];
    	}
    		
    	int min = 99999, cut = 99999;
    	visited[c] = true;
    	for (int i = 1; i <= n; ++i)//选中了第i个房子
    	{
    		if (visited[i])continue;
    		if (price[c][i] >= cut)continue;
    		int num = FlipNum(i, m);
    		int temp = f(i, num) + price[c][i];
    		//visited[i] = false;
    		if (min > temp)
    			min = temp;
    		cut = min < cut ? min : cut;
    	}
    	visited[c] = false;
    	dp[c][m] = min;
    	return min;
    }
    
    int main()
    {
    	cin >> n;	
    	for (int i = 1; i <= n; ++i)
    		for (int j = 1; j <= n; ++j)
    			cin >> price[i][j];
    	int num = 0;
    	for (int i = 1; i <= n; ++i)
    		num = FlipNum(i, num);
    	cout << f(1, num);
    }
    
    展开全文
  • 算法分析与设计实验报告——旅行售货商问题 目录:算法分析与设计实验报告——旅行售货商问题一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论七、实验特色与心得附件一 ...

    算法分析与设计实验报告——旅行售货商问题

    一、 实验目的

    掌握分支限界法的基本思想和解决问题的基本步骤,认识回溯法和分支限界法的联系与区别。

    二、实验要求

    用c++语言实现分支限界法解决决旅行售货商问题,分析时间复杂性,体会分支限界法、回溯法解决问题的基本思路和步骤与区别。

    三、 实验原理

    四、 实验过程(步骤)

    见附件一
    实验步骤、特点
    重要源代码(流操作的部分要醒目的提示并注释)

    五、 运行结果

    见附件二

    六、实验分析与讨论

    遇到的问题,及解决方案

    七、实验特色与心得

    附件一 实验过程(步骤)

    #include "bits/stdc++.h"
    const int INF = 100000;
    const int MAX_N = 22;
    using namespace std;
    //n*n的一个矩阵
    int n;
    int cost[MAX_N][MAX_N];//最少3个点,最多MAX_N个点
    struct Node
    {
        bool visited[MAX_N];//标记哪些点走了
        int s;//第一个点
        int s_p;//第一个点的邻接点
        int e;//最后一个点
        int e_p;//最后一个点的邻接点
        int k;//走过的点数
        int sumv;//经过路径的距离
        int lb;//目标函数的值(目标结果)
        bool operator <(const Node &p)const
        {
            return p.lb < lb;//目标函数值小的先出队列
        }
    };
    priority_queue<Node> pq;//创建一个优先队列
    int low, up;//下界和上界
    bool dfs_visited[MAX_N];//在dfs过程中搜索过
    
    //确定上界,利用dfs(属于贪心算法),贪心法的结果是一个大于实际值的估测结果
    int dfs(int u, int k, int l)//当前节点,目标节点,已经消耗的路径
    {
        if (k == n) return l + cost[u][1];//如果已经检查了n个节点,则直接返回路径消耗+第n个节点回归起点的消耗
        int minlen = INF, p;
        for (int i = 1; i <= n; i++)
        {
            if (!dfs_visited[i] && minlen > cost[u][i])//取与所有点的连边中最小的边
            {
                minlen = cost[u][i];//找出对于每一个节点,其可达节点中最近的节点
                p = i;
            }
        }
        dfs_visited[p] = true;//以p为下一个节点继续搜索
        return dfs(p, k + 1, l + minlen);
    }
    void get_up()
    {
        dfs_visited[1] = true;//以第一个点作为起点
        up = dfs(1, 1, 0);
    }
    //用这种简单粗暴的方法获取必定小于结果的一个值
    void get_low()
    {
        //取每行最小值之和作为下界
        low = 0;
        for (int i = 1; i <= n; i++)
        {
            //创建一个等同于map的临时数组,可用memcpy
            int tmpA[MAX_N];
            for (int j = 1; j <= n; j++)
            {
                tmpA[j] = cost[i][j];
            }
            sort(tmpA + 1, tmpA + 1 + n);//对临时的数组进行排序
            low += tmpA[1];
        }
    }
    int get_lb(Node p)
    {
        int ret = p.sumv * 2;//路径上的点的距离的二倍
        int min1 = INF, min2 = INF;//起点和终点连出来的边
        for (int i = 1; i <= n; i++)
        {
            if (!p.visited[i] && min1 > cost[i][p.s])
            {
                min1 = cost[i][p.s];
            }
        }
        ret += min1;
        for (int i = 1; i <= n; i++)
        {
            if (!p.visited[i] && min2 > cost[p.e][i])
            {
                min2 = cost[p.e][i];
            }
        }
        ret += min2;
        for (int i = 1; i <= n; i++)
        {
            if (!p.visited[i])
            {
                min1 = min2 = INF;
                for (int j = 1; j <= n; j++)
                {
                    if (min1 > cost[i][j])
                        min1 = cost[i][j];
                }
                for (int j = 1; j <= n; j++)
                {
                    if (min2 > cost[j][i])
                        min2 = cost[j][i];
                }
                ret += min1 + min2;
            }
        }
        return (ret + 1) / 2;
    }
    
    int solve()
    {
        //贪心法确定上界
        get_up();
        //取每行最小的边之和作为下界
        get_low();
        //设置初始点,默认从1开始
        Node star;
        star.s = 1;//起点为1
        star.e = 1;//终点为1
        star.k = 1;//走过了1个点
        for (int i = 1; i <= n; i++)
        {
            star.visited[i] = false;
        }
        star.visited[1] = true;
        star.sumv = 0;//经过的路径距离初始化
        star.lb = low;//让目标值先等于下界    
        int ret = INF;//ret为问题的解
        pq.push(star);//将起点加入队列
        while (pq.size())
        {
    
            Node tmp = pq.top();pq.pop();
            if (tmp.k == n - 1)//如果已经走过了n-1个点
            {
                //找最后一个没有走的点
                int p;
                for (int i = 1; i <= n; i++)
                {
                    if (!tmp.visited[i])
                    {
                        p = i;//让没有走的那个点为最后点能走的点
                        break;
                    }
                }
                int ans = tmp.sumv + cost[p][tmp.s] + cost[tmp.e][p];//已消耗+回到开始消耗+走到P的消耗
                //如果当前的路径和比所有的目标函数值都小则跳出
                if (ans <= tmp.lb)
                {
                    ret = min(ans, ret);
                    break;
                }
                    //否则继续求其他可能的路径和,并更新上界
                else
                {
                    up = min(up, ans);//上界更新为更接近目标的ans值
                    ret = min(ret, ans);
                    continue;
                }
            }
            //当前点可以向下扩展的点入优先级队列
            Node next;
            for (int i = 1; i <= n; i++)
            {
                if (!tmp.visited[i])
                {
                    next.s = tmp.s;//沿着tmp走到next,起点不变
                    next.sumv = tmp.sumv + cost[tmp.e][i];//更新路径和                
                    next.e = i;//更新最后一个点                
                    next.k = tmp.k + 1;//更新走过的顶点数                
                    for (int j = 1; j <= n; j++) next.visited[j] = tmp.visited[j];//tmp经过的点也是next经过的点
                    next.visited[i] = true;//自然也要更新当前点
                    next.lb = get_lb(next);//求目标函数
                    if (next.lb > up) continue;//如果大于上界就不加入队列
                    pq.push(next);//否则加入队列
                }
            }
        }
        return ret;
    }
    int main()
    {
        cout<<"请输入城市数量n:";
        cin >> n;
        cout<<"请输入距离矩阵:"<<endl;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                cin >> cost[i][j];
                if (i == j)
                {
                    cost[i][j] = INF;
                }
            }
        }
        cout<<"最小距离为:";
        cout << solve() << endl;
        return 0;
    }
    
    /*
    5
    100000 5 61 34 12
    57 100000 43 20 7
    39 42 100000 8 21
    6 50 42 100000 8
    41 26 10 35 100000
    */
    
    
    

    附件二 运行结果

    在这里插入图片描述

    展开全文
  • #include <iostream> using namespace std; const int Inf = 10000000;//定义一个比较大的值 const int number = 12;//度 int information[2][number] = {{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4}, {2, 3, 4, 1,...

    例题

    #include <iostream>
    using namespace std;
    const int Inf = 10000000;//定义一个比较大的值
    const int number = 12;//度
    int information[2][number] = {{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4}, {2, 3, 4, 1, 3, 4, 1, 2, 4, 1, 2, 3}};//边
    double Distance[number] = {30, 6, 4, 10, 5, 10, 6, 5, 20, 4, 10, 20};//距离
    class Traveling {
    private:
        int _city_number;//城市数
        double **_city_array;//距离矩阵
        int *_Best_solution;//最优解
        double _Best_length;//最短长度
        int *_solution;//解
    public:
        Traveling(int city_number = 0):_city_number(city_number), _Best_length(Inf)//初始化数据
        {
            _Best_solution = new int[_city_number];
            _solution = new int[_city_number];
            _city_array = new double*[_city_number];
            for(int i = 0; i < _city_number; i++)
            {
                _city_array[i] = new double[_city_number];
                for(int j = 0; j < _city_number; j++)
                    _city_array[i][j] = Inf;
            }
            for(int i = 0; i < number; i++)
                _city_array[information[0][i] - 1][information[1][i] - 1] = Distance[i];
            for(int i = 0; i < _city_number; i++)
                _solution[i] = i;
            Backtrack(1, 0);//调用回溯函数
            Print();//输出最优
        }
        ~Traveling()//析构函数
        {
            delete []_solution;
            delete []_Best_solution;
            for(int i = 0; i < _city_number; i++)
                delete[]_city_array[i];
            delete[](_city_array);
        }
        bool OK(int t)//约束函数(判断两顶点是否有边相连)
        {
            if(t == _city_number - 1)//最后一个顶点特殊判断为最后两个点的长度和最后一个点和第一个点
                if(_city_array[_solution[t]][_solution[t-1]] != Inf && _city_array[_solution[t]][_solution[0]] != Inf)
                    return true;
            if(t != _city_number - 1)
                if(_city_array[_solution[t]][_solution[t-1]] != Inf)
                    return true;
            return false;
        }
        double is_best(int t, double length)//限界函数(判断是否能够取得更优值)没有返回-1
        {
            if(t == _city_number - 1)//最后一个点特殊判断,为最后两个点的长度和最后一个点和第一个点
                if(_city_array[_solution[t]][_solution[t - 1]] + length + _city_array[_solution[0]][_solution[t]] < _Best_length)
                    return (_city_array[_solution[t]][_solution[t - 1]] + length + _city_array[_solution[0]][_solution[t]]);
            if(t != _city_number - 1)
                if(_city_array[_solution[t]][_solution[t - 1]] + length <  _Best_length)
                    return (_city_array[_solution[t]][_solution[t - 1]] + length);
            return -1;
        }
        void swap(int t1, int t2)//交换函数
        {
            int temp = _solution[t1];
            _solution[t1] = _solution[t2];
            _solution[t2] = temp;
        }
        void Backtrack(int t, double length)//回溯函数
        {
            if(t >= _city_number)//当获得最后点时更新解
            {
                for(int i = 0; i < _city_number; i++)
                    _Best_solution[i] = _solution[i];
                _Best_length = length;
                return;
            }
            else{
                for(int i = t; i < _city_number; i++)//遍历本层的全部结点
                {
                    swap(t, i);
                    if(OK(t))//约束
                    {
                        double L = is_best(t, length);
                        if(L != -1)//限界
                            Backtrack(t + 1, L);
                    }
                   swap(t, i);
                }
            }
        }
        void Print()//输出最优解
        {
            cout << "以 " << _solution[0] + 1 << " 为出发和结束点最长度为 : " << _Best_length << endl << "路径:" << endl;
            for(int i = 0; i < _city_number; i++)
                cout << " " << _Best_solution[i] + 1;
        }
    };
    int main()
    {
        Traveling travel(4);
    }
    
    展开全文
  • 旅行售货商问题 1

    2018-11-05 09:10:32
    #include&lt;iostream&gt; using namespace std; const int INF = 10000000; int n, cc = 0, bestc = INF; int **g; int *x, *bestx; void travel(int t) { if(t==n){ if(g[x[t-1]][x[t]]!=I...
    #include<iostream>  
    using namespace std;   
    const int INF = 10000000;  
    int n, cc = 0, bestc = INF;  
    int **g;  
    int *x, *bestx;    
    void travel(int t) {
        if(t==n){ 
    		if(g[x[t-1]][x[t]]!=INF&&g[x[t]][1]!=INF&&(cc+g[x[t-1]][x[t]]+g[x[t]][1]<bestc||bestc==INF)){
    			for(int i=0; i<n+1;i++)  
    				bestx[i]=x[i];  
    				bestc=cc+g[x[t-1]][x[t]]+g[x[t]][1];  
            }  
            return;  
        }  
        for(int i=t;i<n;i++) {  
            if (g[x[t-1]][x[i]]!=INF&&(cc+g[x[t-1]][x[i]]<bestc||bestc==INF)){ 
    			//定义宏swap(x,y)用于交换两个参数x和y的值,并编写程序测试。 
    			swap(x[i],x[t]);            
    			cc+=g[x[t-1]][x[t]];  
    			travel(t+1);  
    			cc-=g[x[t-1]][x[t]];  
    			swap(x[i],x[t]);  
            }  
        }  
    }   
    
    void output(){  
    	printf("输出最小路径:\n");
    	printf("%d\n",bestc);
    	printf("输出最优路线:\n");
    	printf("%d",bestx[1]);
        for (int i=2;i<n+1;i++)  	
    		printf(" %d",bestx[i]);
    	printf(" %d\n",bestx[1]);
    }  
      
    int main(){  
        n = 4;  
        g = new int*[n+1];  
        x = new int[n+1];  
        bestx = new int[n+1];   
        for (int i=0;i<n +1;i++) {  
            g[i] = new int[n+1];  
            x[i] = i;  
            for (int j=0; j<n+1;j++)  
                g[i][j]=INF;  
        }  
        g[1][2] = g[2][1] = 30;  
        g[1][3] = g[3][1] = 6;  
        g[1][4] = g[4][1] = 4;   
        g[2][3] = g[3][2] = 5;  
        g[2][4] = g[4][2] = 10;  
        g[3][4] = g[4][3] = 20;  
        travel(2);  
        output();  
        return 0;  
    }
    

     

    展开全文
  • 优先队列式分支限界法解决旅行售货商问题 问题描述: 某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。 他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。...
  • 旅行售货商问题 -- 回溯法

    千次阅读 2018-11-05 09:10:42
    /*旅行售货问题回溯法*/ #include&lt;stdio.h&gt; #define N 4 int cc,//当前路径费用 bestc;//当前最优解费用 int a[N+1][N+1];//邻接矩阵,存放图的信息 int bestx[N+1];//当前最优解 int x[N+1]...
  • 售货商要从一个城市出发,途径每个城市 1 次(且每个城市只能经过 1 次),最终返回出发地,而且他的交通工具只有航班,请求出他旅行的最小开销。 关于输入 输入的第 1 行是一个正整数 n (3 <= n <= ...
  • 回溯算法旅行商问题代码实现。算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次,每次更新bestx需计算时间O(n),从而整个算法的计算时间复杂性为O(n!)。
  • 主要介绍了Python基于回溯法子集树模板解决旅行商问题(TSP),简单描述了旅行商问题并结合实例形式分析了Python使用回溯法子集树模板解决旅行商问题的相关实现步骤与操作技巧,需要的朋友可以参考下
  • C# 实现旅行收货商问题
  • #include<bits/stdc++.h> #include<queue> using namespace std; const int point_number = 4;///顶点个数 double **Distance;...double Best_length = 1000000;///最优距离(开始时取较大值) ...
  • 摘 要旅行售货问题是一个古老而典型的组合优化问题。对该问题合理而有效的解法不但有重要的理论和学术意义,同时对众多工程实际中的应用提供了重要的指导意义。这篇论文首先对问题进行了大体的陈述,对其进行了...
  • 旅行商问题的贪心求解算法,吴飞跃,姚香娟,旅行商问题是组合数学中一个古老而又困难的问题, 至今尚未彻底解决。因此,人们转向寻找近似算法或启发式算法, 其中较有成效的是�
  • 旅行售货问题即给几个地点,相互之间有路径,有每个路径对应的消耗的费用。我们将起点设为1,其他地点设为2,3,4…n。我们起初将所有路径费用都设置成∞,然后再输入 相通路径的费用,再更新费用值。我们以下图为...
  • 用枚举法实现的旅行售货问题 NP问题 可以处理有向图的矩阵
  • TSP旅行售货问题-回溯法 最近比较颓废,考试实在是太多了,月考简直了。对转专业的学生太不友好了。一大堆公共课简直消磨了我对编程的热情。 今天刚好去听了节一直逃课的晚课,老师找我谈了谈,没有怪我。我也...
  • 回溯法求解旅行商问题回溯法和最近邻法的区别是,回溯法可以求得全局最优解,而最近邻法求得的是近似优解。不过,由于回溯法的时间复杂度为O(n²),所以城市数量非常多时仍然不太适用。代码:# -*- coding: utf-8 -*...
  • 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树,裁剪那些不能得到最优解的子树以提高搜索效率。 分支界限法解题的一般思路: (1)分支限界法的求解目标则是找出满足约束条件的一个...
  • 旅行售货问题-回溯法

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

    万次阅读 2018-05-06 16:33:40
    问题描述:某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。算法描述:回溯法,序列树, 假设起点为 1。算法开始时 x = [1...
  • 07回溯法-旅行售货问题 **问题描述:**已知有m个城市,城市之间由n条不同长度的道路相连。一个售货员从一座城市出发,途径所有城市,并最终回到原点,设计算法计算售货员所走的最短路径结点。 **问题分析:**从...
  • 关于旅行商问题 旅行售货员问题 货郎担问题的一些文章,均是pdf格式的,基本都是中国期刊网上下载的,是付费下载的哦!!一般地方是找不到的!
  • 回溯法即是在按条件搜索走不通的情况下退回再选择其他路线的方法,这里我们来看C语言使用回溯法解旅行售货问题与图的m着色问题的方法示例:
  • TSP问题旅行售货问题

    千次阅读 2018-06-08 22:19:39
    问题:TSP问题(旅行售货员问题)旅行商问题,即TSP问题(Traveling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,...
  • 分支与限界-旅行售货问题

    千次阅读 多人点赞 2019-06-20 16:25:00
    类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的...

空空如也

空空如也

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

旅行售货商问题