旅行商问题（枚举，回溯，动态规划，贪心，分支界限）

文章目录

  • 问题描述
  • 暴力枚举
  • 回溯法
  • 动态规划法
  • 贪心法
  • 分支界限法

问题描述

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

在这里插入图片描述

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

暴力枚举

使用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 v > b v 时减去 当cv > bv时减去 当cv>bv时减去
在这里插入图片描述
在暴力枚举的基础上加上这个剪枝函数就行

#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;
}

搜索的结点数变成了
在这里插入图片描述
相比穷举减少了搜索的结点数

动态规划法

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

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

在这里插入图片描述

/*
    由于要遍历每一个点所以不能用最短路径算法
    从一个已知点到另一个点只需要关注两个状态：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;
}

在这里插入图片描述

分支界限法

使用优先队列形式
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;
}

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/182461.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

爬虫逆向你应该懂得Javascript知识

爬虫逆向你应该懂得Javascript知识

背景 大家在学习爬虫逆向的时候&#xff0c;一般都会涉及到对js源文件进行代码扣去&#xff0c;但是有的时候&#xff0c;你最好有js基础&#xff0c;能发现加密或者解密在那个位置&#xff0c;或者是能用python改写js代码&#xff0c;这就对个人的Javascript的能力有一定要求…
阅读更多...
python如何快速查找到想要的文档

python如何快速查找到想要的文档

字多不看版&#xff0c;直接体验 待补充 演示代码 # -*- coding:UTF-8 -*-# region 导入必要的依赖包 import os import subprocess from enum import Enum模块名 pyperclip try:import pyperclip # 需要安装 pyperclip 模块&#xff0c;以支持粘贴板操作 except ImportEr…
阅读更多...
激光雷达与惯导标定 | Lidar_IMU_Init ： 编译

激光雷达与惯导标定 | Lidar_IMU_Init ： 编译

激光雷达与惯导标定&#xff1a;Lidar_IMU_Init 编译 功能包安装安装ceres-solver-2.0.0 &#xff08;注意安装2.2.0不行&#xff0c;必须要安装2.0.0&#xff09; LI-Init是一种鲁棒、实时的激光雷达惯性系统初始化方法。该方法可校准激光雷达与IMU之间的时间偏移量和外部参数…
阅读更多...
【Spring】 IoCDI

【Spring】 IoCDI

回顾 企业命名规范 大驼峰:BookDao(首字母都大写) 类名 小驼峰:bookDao(第一个字母小写) 方法名 蛇形:book_dao(小写下划线_) 数据库 串形:book-dao(小写连字符-) 项目文件夹 各种注解 学习Spring MVC, 其实就是学习各种Web开发需要⽤的到注解 a. RequestMapping: 路由…
阅读更多...
（一）C语言之入门：使用Visual Studio Community 2022运行hello world

（一）C语言之入门：使用Visual Studio Community 2022运行hello world

使用Visual Studio Community 2022运行c语言的hello world 一、下载安装Visual Studio Community 2022 与 新建项目二、编写c helloworld三、编译、链接、运行 c helloworld1. 问题记录&#xff1a;无法打开源文件"stdio.h"2. 问题记录&#xff1a;调试和执行按钮是灰…
阅读更多...
Leetcode算法系列| 1. 两数之和(四种解法)

Leetcode算法系列| 1. 两数之和(四种解法)

目录 1.题目2.题解解法一&#xff1a;暴力枚举解法二&#xff1a;哈希表解法解法三&#xff1a;双指针(有序状态)解法四&#xff1a;二分查找(有序状态) 1.题目 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数…
阅读更多...
前端 vue 面试题(二)

前端 vue 面试题(二)

文章目录 如何让vue页面重新渲染组件间通信vue为什么要mutation、 action操作插槽、具名插槽、作用域插槽vue编译使用的是什么库&#xff1f;vue怎么实现treeshakingwebpack实现treeshaking为什么只有es module 能支持 tree shaking mixin 的作用mixin的底层原理nexTick原理vue…
阅读更多...
小辰的智慧树（差分+前缀和）

小辰的智慧树（差分+前缀和）

登录—专业IT笔试面试备考平台_牛客网 1.考虑总长度之和不能超过m&#xff0c;2考虑限制每棵树高度不能低于ci&#xff0c;如果用二分最短输能截到的高度&#xff0c;还要另外去判断&#xff0c;是否每棵树mid都能严格大于ci &#xff0c;这样容易超时&#xff0c;换个角度&…
阅读更多...
14 redis全量复制与部分复制

14 redis全量复制与部分复制

1、设置主服务器的地址和端口 首先是在从服务器设置需要同步的主服务器信息&#xff0c;包括机器IP, 端口。 主从复制的开启&#xff0c;完全是在从节点发起的。不需要我们在主节点做任何事情。 从节点开启主从复制&#xff0c;有3种方式 配置文件&#xff1a;在从服务器的配…
阅读更多...
使用【画图】软件修改图片像素、比例和大小

使用【画图】软件修改图片像素、比例和大小

打开电脑画图软件&#xff0c;点击开始 windows附件 画图 在画图软件里选择需要调整的照片&#xff0c;点击文件 打开 在弹出窗口中选择照片后点击打开 照片在画图软件中打开后&#xff0c;对照片进行调整。按图中顺序进行 确定后照片会根据设定的值自动调整 保存…
阅读更多...
P6 C++控制流语句(continue, break, return)

P6 C++控制流语句(continue, break, return)

前言 今天我们讲的是控制流语句&#xff0c;本期内容是上期课程的延续。 控制流语句一般与循环语句一起工作&#xff0c;它们让我们可以更好的控制这些循环的实际运行。 我们有三个主要的控制流语句可以使用&#xff0c;continue 、break 和 return&#xff0c;它们有不同的…
阅读更多...
CCFCSP试题编号：201803-2试题名称：碰撞的小球

CCFCSP试题编号：201803-2试题名称：碰撞的小球

一、题目描述 二、思路 1.首先妾身分析这个题目&#xff0c;想要解题&#xff0c;得得解决2个问题。 1&#xff09;判断小球到达端点或碰撞然后改变方向&#xff1b; 2&#xff09;每时刻都要改变位置 两个问题都比较好解决&#xff0c;1&#xff09;只要简单判断坐标&…
阅读更多...
【Vue】核心特性（响应式）

【Vue】核心特性（响应式）

响应式&#xff1a; 数据变化&#xff0c;视图自动更新 接下来使用一个例子来体现一下什么是响应式 案例一&#xff1a; 访问数据&#xff0c;视图自动更新 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><…
阅读更多...
12个最佳WordPress投票插件

12个最佳WordPress投票插件

您是否正在为您的网站寻找WordPress投票插件&#xff1f; WordPress投票插件可让您轻松地在您的网站上进行民意调查&#xff0c;用户可以投票。这是在收集见解的同时建立用户参与度的有效策略。 在本文中&#xff0c;我们精心挑选了最好的WordPress投票插件&#xff0c;可帮助…
阅读更多...
【C/PTA】函数专项练习（四）

【C/PTA】函数专项练习（四）

本文结合PTA专项练习带领读者掌握函数&#xff0c;刷题为主注释为辅&#xff0c;在代码中理解思路&#xff0c;其它不做过多叙述。 目录 6-1 计算A[n]1/(1 A[n-1])6-2 递归实现顺序输出整数6-3 自然数的位数(递归版)6-4 分治法求解金块问题6-5 汉诺塔6-6 重复显示字符(递归版)…
阅读更多...
代码随想录算法训练营第五十二天|300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组

代码随想录算法训练营第五十二天|300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组

文档讲解&#xff1a;代码随想录 视频讲解&#xff1a;代码随想录B站账号 状态&#xff1a;看了视频题解和文章解析后做出来了 300.最长递增子序列 class Solution: # 2516 ms, faster than 64.96%def lengthOfLIS(self, nums: List[int]) -> int:n len(nums)dp [1] * n…
阅读更多...
黑马点评-10实现用户点赞和点赞排行榜功能

黑马点评-10实现用户点赞和点赞排行榜功能

用户点赞功能 如果用户只要点赞一次就对数据库中blog表中的liked字段的值加1就会导致一个用户无限点赞 PutMapping("/like/{id}") public Result likeBlog(PathVariable("id") Long id) {// 修改点赞数量,update tb_blog set liked liked 1 where id …
阅读更多...
JavaScript编程基础 – 布尔值(Booleans)

JavaScript编程基础 – 布尔值(Booleans)

JavaScript编程基础 – 布尔值(Booleans) Javascript Programming Essentials – Booleans 一个JavaScript布尔值包含两个值中的一个&#xff0c;即 true 或者 false。 本文简要介绍JavaScript布尔值的具体应用&#xff0c;以及可能作为对象的布尔值等。 1. 布尔值(Booleans)…
阅读更多...
Py之PyPDF2：PyPDF2的简介、安装、使用方法之详细攻略

Py之PyPDF2：PyPDF2的简介、安装、使用方法之详细攻略

Py之PyPDF2&#xff1a;PyPDF2的简介、安装、使用方法之详细攻略 目录 PyPDF2的简介 PyPDF2的安装 PyPDF2的使用方法 1、基础用法 PyPDF2的简介 PyPDF2是一个免费的、开源的纯python PDF库&#xff0c;能够拆分、合并、裁剪和转换PDF文件的页面。它还可以为PDF文件添加自定…
阅读更多...
springcloud超市管理系统源码

springcloud超市管理系统源码

技术说明&#xff1a; jdk1.8&#xff0c;mysql5.7&#xff0c;idea&#xff0c;vscode springcloud springboot mybatis vue elementui mysql 功能介绍&#xff1a; 后台管理&#xff1a; 统计分析&#xff1a;查看用户&#xff0c;商品&#xff0c;销售数量&#xff1b;…
阅读更多...
最新文章

Copyright @ 2022~2023