【算法设计与分析】实验8:分支限界—TSP问题

目录

一、实验目的

二、实验环境

三、实验内容

四、核心代码

五、记录与处理

六、思考与总结

七、完整报告和成果文件提取链接

一、实验目的

        掌握分支界限求解问题的思想;针对不同的问题,能够利用分支界限法进行问题拆分和求解以及时间复杂度分析,并利用JAVA/C/C++等编程语言将算法转换为对应的程序上机运行(语言不限)。

二、实验环境

        1、机房电脑  Window11

        2、Eclipse/devc++

三、实验内容

实验要求:

①分支限界求解问题的策略及思路;(BFS广度优先搜索)

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

【求解过程】

在分支限界法中,每一个活结点只有一次机会成为扩展结点。

1.活结点一旦成为扩展结点,就一次性产生其所有儿子结点。当前点从活动节点队列中删去;

2.儿子结点中,不可行解或非最优解结点删去,其余儿子结点被加入活结点列表中;

3.从活结点表中取下一结点成为当前扩展结点;

4.重复上述结点扩展过程。直至活动结点列表为空;

活结点扩展顺序:先进入活结点列表,优先变为扩展节点

   活结点存储结构是队列Queue

②分析与回溯法求解问题的异同;

分支限界法与回溯法的不同之处:

(1)求解目标:

 回溯法:一般是找出解空间树中满足约束条件的所有解,也可找最优解的树;

分支限界法:找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。

(2)搜索方式的不同:

回溯法:以深度优先的方式搜索解空间树;

分支限界法:以广度优先或以最小耗费优先的方式搜索解空间树。

③掌握基于分支限界的TSP旅行商问题的设计求解;

针对如下问题,给出基于优先队列分支限界的算法设计策略。

如下4个城市,城市间的耗费如图。从城市1出发进行遍历。寻找最短遍历路径。

首先分析该问题的解空间树,它是一棵排列树:

它的特点如下:

(1)指定一个城市作为出发城市

(2)把第n-1层结点看做叶子结点

1.算法开始时创建一个最小堆,用于表示活结点优先队列

2.堆中每个结点的优先级为:cc+lcostcc为出发城市到当前城市的路程,lcost是当前顶点最小出边+剩余顶点最小出边和

3.每次从优先队列中取出一个活结点成为扩展结点

4. s=n-2,扩展出的结点是排列树中某个叶子结点的父结点。如该叶结点相应一条可行回路且费用小于当前最优解bestc,则将该结点插入到优先队列中,否则舍去该结点

5. s<n-2,产生当前扩展结点的所有儿子结点。计算可行儿子。结点的优先级cc+lcost及相关信息。当cc+lcost<bestc时,将这个可行儿子结点插入到活结点优先队列中。

④对上述算法进行时间复杂性分析,分析时间复杂度对比。

        回溯法是一种通过探索所有可能的候选解来找出所有解的算法。在解决TSP问题时,回溯法会生成一棵解空间树,其中每个节点代表一个可能的城市访问顺序,叶子节点代表一个完整的访问序列。

      对于n个城市,解空间树是一个n-1层的完全二叉树,这棵树的节点总数是(n-1)!

      在最坏情况下,回溯法需要遍历解空间树的所有节点来找到最短路径。因此,时间复杂度是O((n-1)!),但由于(n-1)!与n!相差不大,通常可以简化为O(n!)。

      分支限界法解决TSP问题的时间复杂度在最坏情况下也是O(n!),然而,在实际应用中,通过剪枝操作,分支限界法大大减少了实际搜索空间,因此平均运行时间优于蛮力算法。

四、核心代码

//用这种简单粗暴的方法获取必定小于结果的一个值
void get_low()
{//取每行最小值之和作为下界low = 0;for (int i = 1; i <= n; i++){//创建一个等同于map的临时数组,可用memcpyint 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;
}

五、记录与处理

此处定义INF无穷大为100000,即对角线为INF

六、思考与总结

通过分析回溯法和分支限界法的时间复杂度以及实际运行效率,我深刻认识到了算法优化的重要性。我学会了如何使用限界函数和剪枝策略来减少搜索空间,从而提高算法的运行效率。

七、完整报告和成果文件提取链接

完整可运行代码以及相关实验报告以下链接可获取:
链接: https://pan.baidu.com/s/1iss6-C2nxZQGkEpo-WDn0A?pwd=g5cg 提取码: g5cg 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2025年大年初一篇,C#调用GPU并行计算推荐

C#调用GPU库的主要目的是利用GPU的并行计算能力&#xff0c;加速计算密集型任务&#xff0c;提高程序性能&#xff0c;支持大规模数据处理&#xff0c;优化资源利用&#xff0c;满足特定应用场景的需求&#xff0c;并提升用户体验。在需要处理大量并行数据或进行复杂计算的场景…

2025:影刀RPA使用新实践--CSDN博客下载

文章目录 一键CSDN博客下载器程序说明指导说明使用步骤 获取方法 一键CSDN博客下载器 程序说明 配置信息&#xff1a;CSDN账号&#xff08;手机号/邮箱/用户名&#xff09;、密码、博客文件类型支持markdown格式、html格式&#xff08;默认值markdown格式&#xff09;、博客保…

游戏引擎 Unity - Unity 启动(下载 Unity Editor、生成 Unity Personal Edition 许可证)

Unity Unity 首次发布于 2005 年&#xff0c;属于 Unity Technologies Unity 使用的开发技术有&#xff1a;C# Unity 的适用平台&#xff1a;PC、主机、移动设备、VR / AR、Web 等 Unity 的适用领域&#xff1a;开发中等画质中小型项目 Unity 适合初学者或需要快速上手的开…

【Postman接口测试】Postman的安装和使用

在软件测试领域&#xff0c;接口测试是保障软件质量的关键环节之一&#xff0c;而Postman作为一款功能强大且广受欢迎的接口测试工具&#xff0c;能够帮助测试人员高效地进行接口测试工作。本文将详细介绍Postman的安装和使用方法&#xff0c;让你快速上手这款工具。 一、Pos…

边缘检测算法(candy)

人工智能例子汇总&#xff1a;AI常见的算法和例子-CSDN博客 Canny 边缘检测的步骤 1. 灰度转换 如果输入的是彩色图像&#xff0c;则需要先转换为 灰度图像&#xff0c;因为边缘检测通常在单通道图像上进行。 2. 高斯滤波&#xff08;Gaussian Blur&#xff09; 由于边缘…

WinDBG查找C++句柄泄露

C代码&#xff08;频繁点击About按钮导致Mutex句柄泄露&#xff09; HANDLE _mutexHandle;LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam) {switch (message){case WM_COMMAND:{int wmId LOWORD(wParam);// 分析菜单选择:switch (wmId){c…

基于微信小程序的酒店管理系统设计与实现(源码+数据库+文档)

酒店管理小程序目录 目录 基于微信小程序的酒店管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 (1) 用户信息管理 (2) 酒店管理员管理 (3) 房间信息管理 2、小程序序会员模块的实现 &#xff08;1&#xff09;系统首页 &#xff…

大白话讲清楚embedding原理

Embedding&#xff08;嵌入&#xff09;是一种将高维数据&#xff08;如单词、句子、图像等&#xff09;映射到低维连续向量的技术&#xff0c;其核心目的是通过向量表示捕捉数据之间的语义或特征关系。以下从原理、方法和应用三个方面详细解释Embedding的工作原理。 一、Embe…

mysql中in和exists的区别?

大家好&#xff0c;我是锋哥。今天分享关于【mysql中in和exists的区别&#xff1f;】面试题。希望对大家有帮助&#xff1b; mysql中in和exists的区别&#xff1f; 在 MySQL 中&#xff0c;IN 和 EXISTS 都是用于子查询的操作符&#xff0c;但它们在执行原理和适用场景上有所不…

MySQL高可用

一、mysql路由 1.利用路由器的连接路由特性&#xff0c;用户可以编写应用程序来连接到路由器&#xff0c;并令路由器使用响应的路由策略来处理连接来使其连接到正确的mysql数据库服务器 2.mysql route的部署方式 需要在所有数据库主机之外再打开一台主机mysql-router 配置mysql…

DDD - 微服务架构模型_领域驱动设计(DDD)分层架构 vs 整洁架构(洋葱架构) vs 六边形架构(端口-适配器架构)

文章目录 引言1. 概述2. 领域驱动设计&#xff08;DDD&#xff09;分层架构模型2.1 DDD的核心概念2.2 DDD架构分层解析 3. 整洁架构&#xff1a;洋葱架构与依赖倒置3.1 整洁架构的核心思想3.2 整洁架构的层次结构 4. 六边形架构&#xff1a;解耦核心业务与外部系统4.1 六边形架…

LS和MMSE信道估计

1️⃣ LS&#xff08;最小二乘&#xff09;信道估计 OFDM系统的信道估计常在频域进行&#xff0c;因为OFDM本身就是基于频域的。频域模型可以表示为&#xff1a; Y ( f ) X ( f ) H ( f ) Z ( f ) Y(f)X(f) H(f)Z(f) Y(f)X(f)H(f)Z(f) 其中&#xff0c; Y ( f ) Y(f) Y(f)表…

C++ strcpy和strcat讲解

目录 一. strcpy 代码演示&#xff1a; 二.strcat 代码演示&#xff1a; 一. strcpy 使⽤字符数组可以存放字符串&#xff0c;但是字符数组能否直接赋值呢&#xff1f; ⽐如&#xff1a; char arr1[] "abcdef"; char arr2[20] {0}; arr2 arr1;//这样这节赋值可…

力扣257. 二叉树的所有路径(遍历思想解决)

Problem: 257. 二叉树的所有路径 文章目录 题目描述思路复杂度Code 题目描述 思路 遍历思想(利用二叉树的先序遍历) 利用先序遍历的思想&#xff0c;我门用一个List变量path记录当前先序遍历的节点&#xff0c;当遍历到根节点时&#xff0c;将其添加到另一个List变量res中&…

JVM运行时数据区域-附面试题

Java虚拟机在执行Java程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域 有各自的用途&#xff0c;以及创建和销毁的时间&#xff0c;有的区域随着虚拟机进程的启动而一直存在&#xff0c;有些区域则是 依赖用户线程的启动和结束而建立和销毁。 1. 程序计…

向上调整算法(详解)c++

算法流程&#xff1a; 与⽗结点的权值作⽐较&#xff0c;如果⽐它⼤&#xff0c;就与⽗亲交换&#xff1b; 交换完之后&#xff0c;重复 1 操作&#xff0c;直到⽐⽗亲⼩&#xff0c;或者换到根节点的位置 这里为什么插入85完后合法&#xff1f; 我们插入一个85&#xff0c;…

数据库备份、主从、集群等配置

数据库备份、主从、集群等配置 1 MySQL1.1 docker安装MySQL1.2 主从复制1.2.1 主节点配置1.2.2 从节点配置1.2.3 创建用于主从同步的用户1.2.4 开启主从同步1.2.4 主从同步验证 1.3 主从切换1.3.1 主节点设置只读&#xff08;在192.168.1.151上操作&#xff09;1.3.2 检查主从数…

【题解】AtCoder Beginner Contest ABC391 D Gravity

题目大意 原题面链接 在一个 1 0 9 W 10^9\times W 109W 的平面里有 N N N 个方块。我们用 ( x , y ) (x,y) (x,y) 表示第 x x x 列从下往上数的 y y y 个位置。第 i i i 个方块的位置是 ( x i , y i ) (x_i,y_i) (xi​,yi​)。现在执行无数次操作&#xff0c;每一次…

FFmpeg工具使用基础

一、FFmpeg工具介绍 FFmpeg命令行工具主要包括以下几个部分: ‌ffmpeg‌:编解码工具‌ffprobe‌:多媒体分析器‌ffplay‌:简单的音视频播放器这些工具共同构成了FFmpeg的核心功能,支持各种音视频格式的处理和转换‌ 二、在Ubuntu18.04上安装FFmpeg工具 1、sudo apt-upda…

自制虚拟机(C/C++)(二、分析引导扇区,虚拟机读二进制文件img软盘)

先修复上一次的bug&#xff0c;添加新指令&#xff0c;并增加图形界面 #include <graphics.h> #include <conio.h> #include <windows.h> #include <commdlg.h> #include <iostream> #include <fstream> #include <sstream> #inclu…