旅行商问题(枚举,回溯,动态规划,贪心,分支界限)

这篇具有很好参考价值的文章主要介绍了旅行商问题(枚举,回溯,动态规划,贪心,分支界限)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

假设有一个货郎担要拜访n个城市,他必须选择所要走的路程,路程的限制时每个城市只能拜访一次,而且最后要走到原来出发的城市,要求路径长度。

旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法

旅行商问题将要走过的城市建立成一个完全图。稠密图,所以用临接矩阵来存。
由于路径的特殊性,可以正走也可以反着走,所以一般存在两条最优路径同时也可以用这条性质检验算法的正确性。

暴力枚举

使用dfs枚举每一个点, 不适用剪枝的话就是暴力枚举方法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int g[N][N], n, m;
int cv = 0, bv = 0x3f3f3f3f;
bool st[N];

vector<int> ans, x;

void dfs(int k)
{
    
    if (k == n)
    {
        // printf("before cv : %d\n", cv);
        // printf("last : {%d, %d} = %d\n", 1, x[k - 1], g[1][x[k - 1]]);
        cv += g[1][x[k - 1]];
        x.push_back(x[0]);
        
        for (auto i : x)
            printf("%d ", i);
        puts("");
        printf("{cv : %d}\n", cv);
        
        if(cv < bv)
        {
            
            bv = cv;
            ans = x;
        }
        cv -= g[1][x[k - 1]];//注意最后一个加的cv要减掉
        x.pop_back();//同样也要删掉
        return;
    }
    
    for (int i = 1; i <= n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            x.push_back(i);//注意x的添加要在前面不然后面下标会出错
            cv += g[x[k - 1]][i];
            // printf("{%d, %d} : %d\n", x[k - 1], i,  g[x[k - 1]][i]);
            dfs(k + 1);
            cv -= g[x[k - 1]][i];
            x.pop_back();
            st[i] = false;
        }
    }
}

void out()
{
    puts("路径为:");
    for (int i = 0; i <= n; i ++){
        printf("%d", ans[i]);
        printf(i == n ? "\n" : "->");
    }
}

int main()
{
    memset(g, 0x3f, sizeof g);
    
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    for (int i = 0; i <= n; i ++) g[i][i] = 0; 
    
    st[1] = true; 
    x.push_back(1);
    dfs (1);
    puts("最短路径为:");
    printf("%d\n", bv);
    out();

    reverse(ans.begin(), ans.end());
    out();
    puts("");
    
    return 0;
}

旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法

回溯法

回溯法就是在暴力枚举的是后加上剪枝函数减少枚举的结点数目
剪枝函数为
左剪枝:
当 c v > b v 时减去 当cv > bv时减去 cv>bv时减去
旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法
在暴力枚举的基础上加上这个剪枝函数就行

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int g[N][N], n, m;
int cv = 0, bv = 0x3f3f3f3f;
bool st[N];

vector<int> ans, x;

void dfs(int k)
{
    
    if (k == n)
    {
        // printf("before cv : %d\n", cv);
        // printf("last : {%d, %d} = %d\n", 1, x[k - 1], g[1][x[k - 1]]);
        cv += g[1][x[k - 1]];
        x.push_back(x[0]);
        
        for (auto i : x)
            printf("%d ", i);
        puts("");
        printf("{cv : %d}\n", cv);
        
        if(cv < bv)
        {
            
            bv = cv;
            ans = x;
        }
        cv -= g[1][x[k - 1]];//注意最后一个加的cv要减掉
        x.pop_back();//同样也要删掉
        return;
    }
    
    for (int i = 1; i <= n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            x.push_back(i);
            cv += g[x[k - 1]][i];
            // printf("{%d, %d} : %d\n", x[k - 1], i,  g[x[k - 1]][i]);
            if (cv <= bv)
                dfs(k + 1);
            cv -= g[x[k - 1]][i];
            x.pop_back();
            st[i] = false;
        }
    }
}

void out()
{
    puts("路径为:");
    for (int i = 0; i <= n; i ++){
        printf("%d", ans[i]);
        printf(i == n ? "\n" : "->");
    }
}

int main()
{
    memset(g, 0x3f, sizeof g);
    
    scanf("%d%d", &n, &m);
    
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    for (int i = 0; i <= n; i ++) g[i][i] = 0; 
    
    st[1] = true; 
    x.push_back(1);
    dfs (1);
    puts("最短路径为:");
    printf("%d\n", bv);
    out();

    reverse(ans.begin(), ans.end());
    out();
    puts("");
    
    return 0;
}

搜索的结点数变成了
旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法
相比穷举减少了搜索的结点数

动态规划法

状态压缩dp
利用一个int位中的32位0/1bit码来表示图走了哪些点,如果此位为1表示经过,0表示还未经过

类似题目AcWing 91. 最短Hamilton路径

旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法

/*
    由于要遍历每一个点所以不能用最短路径算法
    从一个已知点到另一个点只需要关注两个状态:1、终点是什么, 2、经过了哪些点
    而dp[i][j] 表示从0到终点j,经过了二进制状态(每个点有走过和没走两个状态)的点的路径
    状态计算:dp[i][j] <- dp[i - j][k](在已经经过的点中,去掉点j的方案取最小)
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 21, M = 1 << N;
int dp[M][N];
int w[N][N];
int n;

int main()
{
    scanf("%d", &n);
    
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            scanf("%d", &w[i][j]);
            
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    
    for (int i = 0; i < 1 << n; i ++)
        for (int j = 0; j < n; j ++)
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1)
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[j][k]);// 转移到达第i个点时将第i个点的状态要去掉就
                        // 例如要将100101的第2个点去掉就需要 - 000100 = 100001
                        
    printf("%d\n", dp[(1 << n) - 1][n - 1]);// 100000 - 000001 = 0111111 要将n - 1位全置位为1只需要用n为1后面为0减个位1即可
    return 0;
}

贪心法

贪心就是从起点开始每次走从这个点出发权重最小的边
但是这个寻找局部最优解的过程找到的并不是全局最优解
思路和生成最小生成树的思路一样,由于是完全图稠密图,所以使用prim算法更好

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dist[N];
bool st[N];
int n, m;
vector<int> ans;

int prime()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;// 最小生成树中的权重之和

    for (int i = 0; i < n; i ++)
    {
        int t = -1;// t表示集合外与集合相连的边最小的结点
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[j] < dist[t]))// 集合外的,第一次直接赋值,值更小的
                t = j;

        st[t] = true;// 加入集合
        ans.push_back(t);
        
        if (i && dist[t] == INF) return INF;// 不是第一个节点且到集合的距离无穷,说明各个结点都不连通
        if (i) res += dist[t];

        for (int j = 1; j <= n; j ++)
            dist[j] = min (dist[j], g[t][j]);// 更新与集合相连的最小值
    }

    return res;
}

void out()
{
    puts("路径:");
    for (int i = 0; i <= n; i ++)
    {
        printf("%d", ans[i]);
        printf(i == n ? "\n" : "->");
    }
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min (g[a][b], c);// 无向图要将两个方向的边都赋上权重
    }
    
    int res = prime();
    if (res == INF) puts("impossible");
    else printf("%d\n", res + g[ans[n - 1]][1]);
    
    ans.push_back(ans[0]);
    
    out();
    reverse(ans.begin(), ans.end());
    out();
    
    return 0;
}

旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法

分支界限法

使用优先队列形式
cc为当前代价,rc为剩余结点的最小出边代价和
下界函数为: cc + rc
左剪枝:
当 c c > b c 时剪枝 当cc > bc时剪枝 cc>bc时剪枝
右剪枝:
当 c c + r c > b c 是剪枝 当cc + rc > bc是剪枝 cc+rc>bc是剪枝

归结左右剪枝都可以用bound = cc + rc进行剪枝

剩余结点最小出边代价和就是枚举剩余每条结点对没给结点只算最小的出边

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 16;
const int INF = 0x3f3f3f3f;

int g[N][N], n, m, bc = INF;
vector<int> ans;

struct Node {
    int idx, cost, bound;
    vector<int> path;
    bool st[N];

    bool operator<(const Node& other) const {
        return bound + cost > other.bound + other.cost;  // 按照 bound + cost 降序排序
    }
};

int bound(const Node& x) {
    int minCost = 0;
    for (int i = 1; i <= n; ++i) {
        if (x.st[i]) {
            int m = INF;
            for (int j = 1; j <= n; ++j) {
                if (x.st[j]) {
                    m = min(m, g[i][j]);
                }
            }
            minCost += m;
        }
    }
    return minCost;
}

void bfs() {
    priority_queue<Node> heap;

    Node head = {1, 0, 0, {1}, {false}};
    head.st[1] = true;

    heap.push(head);

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        if (t.idx == n) {
            int cc = t.cost + g[t.path[t.idx - 1]][1];
            for (auto i : t.path)
                printf("%d ", i);
            printf("%d", 1);
            puts("");
            if (cc < bc)
            {
                bc = cc;
                ans = t.path;
            }
            continue;
        }

        for (int i = 1; i <= n; ++i) {
            if (!t.st[i]) {
                Node newNode = t;
                newNode.st[i] = true;
                newNode.path.push_back(i);
                newNode.cost += g[newNode.path[newNode.idx - 1]][i];
                newNode.idx++;
                newNode.bound = bound(newNode); 
                if(newNode.bound < bc)//左右剪枝通用,因为是排列树左右都要算下界函数
                    heap.push(newNode);
            }
        }
    }
}

void out()
{
    puts("路径:");
    for (int i = 0; i <= n; i ++)
    {
        printf("%d", ans[i]);
        printf(i == n ? "\n" : "->");
    }
}

int main() {
    memset(g, 0x3f, sizeof g);

    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    bfs();
    printf("%d\n", bc);
    ans.push_back(ans[0]);
    
    out();
    reverse(ans.begin(), ans.end());
    out();
    return 0;
}

旅行商问题贪心算法c语言,矿大往事,算法设计与分析,算法文章来源地址https://www.toymoban.com/news/detail-760470.html

到了这里,关于旅行商问题(枚举,回溯,动态规划,贪心,分支界限)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 五种基础算法小结与典型题目分享(动态规划、分治、贪心、回溯、分支限界)

    动态规划是用于解决多阶段决策问题的算法策略。它通过用变量集合描述当前情境来定义“状态”,进而用这些状态表达每个阶段的决策。 每个阶段的状态是基于前面的状态经过某种决策得到的。通过建立状态间的递推关系,并将其形式化为数学递推式,得到“状态转移方程

    2024年01月19日
    浏览(65)
  • 【课设】java:迷宫小游戏(递归与分治、动态规划、贪心算法、回溯法、分支限界法)

    鱼弦:CSDN内容合伙人、CSDN新星导师、全栈领域优质创作者 、51CTO(Top红人+专家博主) 、github开源爱好者(go-zero源码二次开发、游戏后端架构 https://github.com/Peakchen) 递归与分治算法 原理: 递归与分治算法将问题分解为子问题,递归地解决每个子问题,最后将结果合并得到整

    2024年02月02日
    浏览(39)
  • 湘潭大学 算法设计与分析实验 回溯 动态规划 贪心 模拟退火解决背包问题

    https://download.csdn.net/download/SQ_ZengYX/88620871 测试用例

    2024年02月02日
    浏览(62)
  • 01背包问题三种解决(贪心动态规划分支限界)

    一、实验目的 1、深入理解背包相关问题。 2、能正确设计相应的算法,解决实际问题。   3、掌握算法时间复杂度分析。 二、实验要求 用3种方法求解0-1背包问题(贪心算法、 动态规划、分支限界法 ),获得精确最优解或近似最优解均可。 通过一个规模较大的实例比较不同

    2024年02月02日
    浏览(57)
  • 回溯法,分支限界法,动态规划法求解0-1背包问题(c++)

    问题描述 给定n种物品和一背包。物品i的重量是wi0,其价值为vi0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 搜索空间: 子集树(完全二叉树) 约束函数(进包用): 如果当前背包中的物品总重量是cw,前面k-1件物品都已经决定是否进包,那

    2024年02月10日
    浏览(58)
  • 四大算法:贪心、分治、回溯、动态规划

    贪心算法(又称贪婪算法),在求解问题时,总是做出在当前看来是最好的选择。也就是说,不从整体最优解进行考虑,而是得到某种意义上的局部最优解。 贪心算法采用自顶向下,以迭代的方法做出贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的问题。

    2024年02月15日
    浏览(65)
  • LeeCode——回溯法、动态规划、贪心法、分治法(快速说明)

    算法方法 用处 优点 缺点 拓展与改良 回溯法 适用于求解组合问题、排列问题、搜索问题等。 1. 可以搜索整个解空间,找到最优解。 2. 不需要预先知道问题的解可能在哪里。 1. 时间复杂度高,因为需要遍历整个解空间。 2. 需要较大的空间存储搜索轨迹。 1. 剪枝优化。 2. 双

    2024年02月10日
    浏览(86)
  • Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

    1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解, 然后综合各个小问题,得到最终答案。 2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。 3、迭代法(Iterative Method) 无法使用公式一次求解,而需要使用重复结构

    2024年02月08日
    浏览(45)
  • 整数规划——分支界定算法(旅行商问题,规约矩阵求解)

    一、普通优化问题分枝定界求解 题目的原问题为   在计算过程中,利用MATLAB中的linprog()函数进行求解最优解,具体的计算步骤如下: A为约束系数矩阵,B为等式右边向量,C为目标函数的系数向量。   进行第一次最优求解以A=[2 9;11 -8],B=[40;82],C=[-3,-13]利用linprog函数求解。解

    2024年02月16日
    浏览(39)
  • (软考-软件设计师.下午)动态规划算法、回溯算法、贪心算法、分治算法的应用

    :【递归技术】【二分查找】 分治法的设计思路: 将一个难以直接解决的 大问题 分解成一些 规模较小 的相同问题以便于 逐个击破,分而治之 。      由代码可以看出二分查找也属于分治法的一种,关于二分查找,这位博主总结的很详细。  :【查表】   动

    2024年02月06日
    浏览(78)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包