用动态规划算法解Travelling Salesman Problem(TSP)问题

2023-11-05 23:20

本文主要是介绍用动态规划算法解Travelling Salesman Problem(TSP)问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

用动态规划算法解Travelling Salesman Problem(TSP)问题

  • 基础知识
  • 动态规划的求解过程
    • 动态规划方程的推导
    • 状态压缩
  • 源码:
  • 输入数据:

基础知识

  Travelling Salesman Problem (TSP) 是最基本的路线问题。它寻求的是旅行者由起点出发,通过所有给定的需求点后,再次返回起点所花费的最小路径成本,也叫旅行商问题、旅行推销员问题、担货郎问题等。
  动态规划算法(Dynamic Programming,简称DP)通常用于求解具有某种最优性质的问题,其基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后由这些子问题的解再得到原问题的解。

动态规划的求解过程

  下面来验证一下此方法求解的可行性。
  设 s,s1,s2…s为满足题意的最短回路。假设从s到s1的路径已经确定,则问题转化为从s1到s的最短路径问题。而很显然,s1,s2…s一定可以构成一条最短路径,所以构成最优子结构性质,可以用动态规划求解。

动态规划方程的推导

  用 V’ 表示一个点的集合,假设从顶点 s 出发, d ( i , V’ ) 表示当前到达顶点 i,经过 V’ 集合中所有顶点一次的最小花费。

  1. .当 V’ 为仅包含起点的集合,也就是
    d ( s , { s } ) = 0 d(s,\{ s\} ) = 0 d(s,{s})=0
  2. 其他情况,则对子问题求最优解。需在 V’ 这个城市集合中,尝试每一个城市结点,并求出最优解。
    在这里插入图片描述
  3. 最后的求解方式为:
    在这里插入图片描述

其中 S 为包含所有点的集合。把公式一套,题就解了。

状态压缩

  推到动态规划方程时,我们注意到 V’ 是一个数的集合,而且解决的问题规模比较小,于是可以用一个二进制数来存储这个集合。简单来说就是——如果城市 k 在集合 V’ 中,那么存储集合的变量 i 的第 k 位就为 1,否则为 0。由于有 n 个城市,所有的状态总数我们用 M 来表示,那么很明显:M = 2^n,而 0 到 2^n -1 的所有整数则构成了 V’ 的所有状态。这样,结合位运算,动归方程的状态表示就很容易了。

源码:

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
// 定义常量
const int INF = 0x3f3f3f3f;
#define sqr(x) ((x)*(x))
// 定义变量
string file_name;
int type; // type == 1 满秩矩阵格式, type == 2 二维坐标式
int s;
int N;// 城市结点数量
int init_point;
double **dp; // 动态规划状态数组dp[i][j],i表示集合V’,j表示当前到达的城市结点
double **dis; // 两个城市结点之间的距离
double ans;
// 定义结构体
struct vertex {double x, y; // 城市结点的坐标int id; // 城市结点的idint input(FILE *fp) {return fscanf(fp, "%d %lf %lf", &id, &x, &y);}
}*node;double EUC_2D(const vertex &a, const vertex &b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}void io() { // 数据读入printf("input file_name and data type\n");cin >> file_name >> type;FILE *fp = fopen(file_name.c_str(), "r");fscanf(fp, "%d", &N);node = new vertex[N + 5];dis = new double*[N + 5];if (type == 1) {for (int i = 0; i < N; i++) {dis[i] = new double[N];for (int j = 0; j < N; j++)fscanf(fp, "%lf", &dis[i][j]);}}else {for (int i = 0; i < N; i++)node[i].input(fp);for (int i = 0; i < N; i++) {dis[i] = new double[N];for (int j = 0; j < N; j++)dis[i][j] = EUC_2D(node[i], node[j]);// 计算城市之间的距离}}fclose(fp);return;
}void init() { // 数据初始化dp = new double*[(1 << N) + 5];for (int i = 0; i < (1 << N); i++) {dp[i] = new double[N + 5];for (int j = 0; j < N; j++)dp[i][j] = INF;} // 初始化,除了dp[1][0],其余值都为INFans = INF;return;
}double slove() {int M = (1 << N);// M就是第四部分所说的V’状态总数,1<<N表示2^N,总共有2^N种状态dp[1][0] = 0;// 假设固定出发点为0,从0出发回到0的花费为0。TSP只要求是一个环路,所以出发点可以任选for (int i = 1; i < M; i++) {// 枚举V’的所有状态for (int j = 1; j < N; j++) {// 选择下一个加入集合的城市if (i & (1 << j)) continue;// 城市已经存在于V’之中if (!(i & 1)) continue;// 出发城市固定为0号城市for (int k = 0; k < N; k++) {// 在V’这个城市集合中尝试每一个结点,并求出最优解if (i & (1 << k)) {// 确保k已经在集合之中并且是上一步转移过来的结点dp[(1 << j) | i][j] = min(dp[(1 << j) | i][j], dp[i][k] + dis[k][j]); // 转移方程} // 将j点加入到i集合中}}}for (int i = 0; i < N; i++)ans = min(dp[M - 1][i] + dis[i][0], ans);// 因为固定了出发点,所以要加上到城市0的距离。另外要从所有的完成整个环路的集合V’中选择,完成最后的转移return ans;
}int main() {io();init();string tmp = file_name + ".sol";FILE *fp = fopen(tmp.c_str(), "w");fprintf(fp, "%.2lf\n", slove());delete[] dp;delete[] node;delete[] dis;fclose(fp);return 0;
}

输入数据:

若城市数据文件如下所示:

     161   38.24   20.422   39.57   26.153   40.56   25.324   36.26   23.125   33.48   10.546   37.56   12.197   38.42   13.118   37.52   20.449   41.23   9.1010   41.17   13.0511   36.08   -5.2112   38.47   15.1313   38.15   15.3514   37.51   15.1715   35.49   14.3216   39.36   19.56

这篇关于用动态规划算法解Travelling Salesman Problem(TSP)问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/353106

相关文章

解决pandas无法读取csv文件数据的问题

《解决pandas无法读取csv文件数据的问题》本文讲述作者用Pandas读取CSV文件时因参数设置不当导致数据错位,通过调整delimiter和on_bad_lines参数最终解决问题,并强调正确参... 目录一、前言二、问题复现1. 问题2. 通过 on_bad_lines=‘warn’ 跳过异常数据3

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499

kkFileView启动报错:报错2003端口占用的问题及解决

《kkFileView启动报错:报错2003端口占用的问题及解决》kkFileView启动报错因office组件2003端口未关闭,解决:查杀占用端口的进程,终止Java进程,使用shutdown.s... 目录原因解决总结kkFileViewjavascript启动报错启动office组件失败,请检查of

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束

Python错误AttributeError: 'NoneType' object has no attribute问题的彻底解决方法

《Python错误AttributeError:NoneTypeobjecthasnoattribute问题的彻底解决方法》在Python项目开发和调试过程中,经常会碰到这样一个异常信息... 目录问题背景与概述错误解读:AttributeError: 'NoneType' object has no at

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx