旅行售货员问题(C++)

2023-11-11 22:40
文章标签 c++ 问题 旅行 售货员

本文主要是介绍旅行售货员问题(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

编译环境:Dev-C++

分支界限法解旅行售货员问题的具体算法实现


旅行售货员问题描述:

        某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。

算法描述:

        路线是一个带权图。图中各边的费用(权)为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。 旅行售货员问题的解空间可以组织成一棵排列树,从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。 

        解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表。活结点m在优先队列中的优先级定义为:  活结点m对应的子树费用下界lcost,lcost=cc+rcost,其中,cc为当前结点费用,rcost为当前顶点最小出边费用加上剩余所有顶点的最小出边费用和。

      创建一个最小堆,用于表示活结点优先队列。堆中每个结点的优先级是子树费用的下界lcost值。计算每个顶点i的最小出边费用并用minout[i]记录。如果所给的有向图中某个顶点没有出边,则该图不可能有回路,算法结束。基于优先队列式分支限界的旅行售货员问题求解算法,采用限界函数lcost ,作为优先级,不断调整搜索方向,选择最有可能取得最优解的子树优先搜索;同时,根据限界函数lcost进行剪枝,剪掉不包含最优解的分。


算法步骤:

      ①状态A表示售货员没有经过任何路径。此时cc 和 rcost 都为0。以此为初始状态,加入优先队列(最小堆)。

      ②之后取出堆顶,此活节点成为扩展节点,扩展出多个儿子节点。检测所有儿子节点的lcost值,lcost = cc+rcost,其含义为至少需要花费lcost的费用,所以比较lcost和bestc的值。

      ③若lcost > bestc,则它所在的子树再也不会小于bestc,剪枝。

      ④若lcost < bestc,则说明它的子树有可能会得到最优解,因此此儿子节点进入优先队列。

      ⑤每次搜索到叶节点,更新bestc,bestc = cc + a[n-2][n-1]+a[n-1][1]。

所有状态都被访问或者剪枝后,返回。


调试过程及实验结果

程序执行的结果:


源代码:

#include<cstdio>
#include <cstring>
#include <queue>//队列 
#define MAX 100
#define NoEdge -1
using namespace std;int n;
int arr[MAX][MAX];
int v[MAX];
int bestc;
int num = 0;class MinHeapNode{public: char name;public: int rcost,lcost; public: int cc,s;public: int* x;MinHeapNode(){num++;}bool operator<(const MinHeapNode& MH) const{return lcost > MH.lcost;}
};int BBTSP(){MinHeapNode E;int cc, rcost, MinSum, * MinOut, b;int i, j;MinSum = 0;MinOut = new int[n + 1];for (i = 1; i <= n; i++){MinOut[i] = NoEdge;for (j = 1; j <= n; j++)if (arr[i][j] != NoEdge && (arr[i][j] < MinOut[i] || MinOut[i] == NoEdge))MinOut[i] = arr[i][j];if (MinOut[i] == NoEdge)return NoEdge;MinSum += MinOut[i];}priority_queue<MinHeapNode> prioque;E.s = 0;E.cc = 0;E.rcost = MinSum;E.x = new int[n];for (i = 0; i < n; i++)E.x[i] = i + 1;bestc = NoEdge;//搜索排列空间树while (E.s < n - 1){//非叶节点if (E.s == n - 2){// 当前扩展节点是叶节点的父节点if (arr[E.x[n - 2]][E.x[n - 1]] != NoEdge && arr[E.x[n - 1]][1] != NoEdge &&(E.cc + arr[E.x[n - 2]][E.x[n - 1]] + arr[E.x[n - 1]][1] < bestc || bestc == NoEdge)){//费用更小的回路bestc = E.cc + arr[E.x[n - 2]][E.x[n - 1]] + arr[E.x[n - 1]][1];E.cc = bestc;E.lcost = bestc;E.s++;prioque.push(E);}else{delete[] E.x;      // 舍弃扩展结点}}else {// 产生当前扩展节点儿子节点for (i = E.s + 1; i < n; i++){MinHeapNode N;if (arr[E.x[E.s]][E.x[i]] != NoEdge){// E.x[E.s] 是当前要扩展的父节点,E.x[i] 是被遍历的子节点cc = E.cc + arr[E.x[E.s]][E.x[i]];       // 可行儿子节点rcost = E.rcost - MinOut[E.x[E.s]];b = cc + rcost;                          // 下界if (b < bestc || bestc == NoEdge)        // 子树可能含最优解,节点插入最小堆{N.s = E.s + 1; // 进入下一层N.cc = cc;N.lcost = b;N.rcost = rcost;N.x = new int[n];for (j = 0; j < n; j++)N.x[j] = E.x[j];N.x[E.s + 1] = E.x[i];N.x[i] = E.x[E.s + 1];prioque.push(N); // 加入优先队列}}}delete[] E.x;}if (prioque.empty())break;E = prioque.top();prioque.pop();}if (bestc == NoEdge)return NoEdge;for (i = 0; i < n; i++)v[i + 1] = E.x[i];while (prioque.size()){E = prioque.top();prioque.pop();delete[] E.x;}return bestc;
}int main(){printf("请输入城市数量及路径数量:");scanf("%d",&n);int k;memset(arr, NoEdge, sizeof(arr));scanf("%d",&k);printf("请输入各路径及其长度:");int p, q, len;for (int i = 1; i <= k; ++i){scanf("%d %d %d",&p,&q,&len);arr[p][q] = len;arr[q][p] = len;}int res = BBTSP();if (res == NoEdge){puts("无法形成回路");}else {printf("最短路径为:%d\n",res);for (int i = 1; i <= n; i++)printf("%d ",v[i]);printf("%d",v[1]);}
}

这篇关于旅行售货员问题(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL主从同步延迟问题的全面解决方案

《MySQL主从同步延迟问题的全面解决方案》MySQL主从同步延迟是分布式数据库系统中的常见问题,会导致从库读取到过期数据,影响业务一致性,下面我将深入分析延迟原因并提供多层次的解决方案,需要的朋友可... 目录一、同步延迟原因深度分析1.1 主从复制原理回顾1.2 延迟产生的关键环节二、实时监控与诊断方案

SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法

《SQLyog中DELIMITER执行存储过程时出现前置缩进问题的解决方法》在SQLyog中执行存储过程时出现的前置缩进问题,实际上反映了SQLyog对SQL语句解析的一个特殊行为,本文给大家介绍了详... 目录问题根源正确写法示例永久解决方案为什么命令行不受影响?最佳实践建议问题根源SQLyog的语句分

解决IDEA报错:编码GBK的不可映射字符问题

《解决IDEA报错:编码GBK的不可映射字符问题》:本文主要介绍解决IDEA报错:编码GBK的不可映射字符问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录IDEA报错:编码GBK的不可映射字符终端软件问题描述原因分析解决方案方法1:将命令改为方法2:右下jav

C#如何调用C++库

《C#如何调用C++库》:本文主要介绍C#如何调用C++库方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录方法一:使用P/Invoke1. 导出C++函数2. 定义P/Invoke签名3. 调用C++函数方法二:使用C++/CLI作为桥接1. 创建C++/CL

MyBatis模糊查询报错:ParserException: not supported.pos 问题解决

《MyBatis模糊查询报错:ParserException:notsupported.pos问题解决》本文主要介绍了MyBatis模糊查询报错:ParserException:notsuppo... 目录问题描述问题根源错误SQL解析逻辑深层原因分析三种解决方案方案一:使用CONCAT函数(推荐)方案二:

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》:本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key?热 key(Hot Key)定义: 热 key 常见表现:热 key 的风险:二、

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图