回溯算法(2)--图着色问题和旅行商问题

目录

一、图着色问题

1、算法设计

2、代码

二、旅行商问题 

1、概述问题

2、穷举法

3、回溯法 


 

一、图着色问题

1、算法设计

        图着色问题,给定图中各个区域的相邻关系,抽象成一个无向图G=(V,E),给定m种颜色,可以选择一个颜色可以对每一个区域(无向图的顶点)进行着色,但需要保证相邻区域之间不能颜色相同,如下图的无向图表示。

cdb34385fd6f416f8368c10663baa05f.png

        无向图采用建立邻接矩阵a[ ][ ]来表示。注意:i和j都是从1开始的,而不是0开始的,所以邻接矩阵的0行0列,设定为-1,表示不存在。

                eq?a%5Bi%5D%5Bj%5D%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%201%20%5Cqquad%20%28i%2Cj%29%5Cin%20E%5C%5C%200%20%5Cqquad%20%5Cquad%20others%20%5Cend%7Bmatrix%7D%5Cright. 

         算法:回溯法,子集树方法。

        backtrack回溯过程:

(1)首先判断是否叶子结点已经搜索,即t>n,若满足条件,则输出当前着色方法,sum++。

(2)若不满足条件,则在当前层遍历m种颜色,若该颜色满足扩展条件,则扩展该叶子结点搜索下一层,否则选择下一个颜色,直到所有颜色都不满足条件则回溯上一层。

(3)扩展条件:遍历n个结点,若结点与叶子结点有相邻关系a[t][i]==1且叶子结点和该遍历的结点颜色相同x[t]==x[i],则返回false,否则存在一个结点有相邻关系且颜色不同,返回true用来做新的扩展结点。

(4)另外,判断(t<=n)&&x[t]==m,如果当前层数不在叶子结点层(第n层),且该层修改的颜色值为最后一个颜色(由于颜色按顺序遍历),则颜色置0,退出当前迭代层,返回上一层。也就是说当前叶子结点的所有子树都搜索过了,该结点变为死结点,要么返回到该叶子结点的邻树,要么返回叶结点上一层。

e6f2b61d62424bfdbaba3121a68fb94a.png

2、代码

//图着色问题
public class graphcoloration {static int n=5;          //顶点数static int m=3;          //颜色数static int a[][]={         //邻接矩阵{-1,-1,-1,-1,-1,-1},{-1,0,1,1,1,0},{-1,1,0,1,0,1},{-1,1,1,0,1,1},{-1,1,0,1,0,1},{-1,0,1,1,1,0}};   //-1是不存在0点,0是不可达static int sum=0;                   //可行解public static void main(String[] args){int x[]=new int[n+1];           //x存储可达的路线backtrack(1, x);                //初始节点在第一层System.out.println(sum);        //输出有多少种可行解}public static void backtrack(int t,int x[]){if(t>n){    sum++;for(int i=1;i<=n;i++){System.out.print(x[i]+" ");}System.out.println();}else{for(int i=1;i<=m;i++){x[t]=i;if(OK(t,x))                       //如果满足扩展条件则扩展backtrack(t+1, x);if((t<=n)&&x[t]==m)               //如果当前层数不在叶子结点,且该层修改的数为最后一个颜色,则颜色置0,退出当前迭代层                              {   x[t]=0;break;}}}}public static boolean OK(int t,int x[]){for(int i=1;i<=n;i++){if((a[t][i]==1)&&x[t]==x[i])        //判断所有相邻关系中颜色相同的返回falsereturn false;}return true;                            //留下的都是存在相邻关系且颜色不同的返回true}
} 

二、旅行商问题 

1、概述问题

        一个旅行商希望从一个城市出发访问n个城市,每个城市只能访问一次,且开始和结束在同一城市,给出一个不同城市之间距离的加权完全图,请设计一个算法,找到旅行商的最短路径。也就是图论中的求出最小的哈密顿回路。

        下面的算法依照下图为例,出发为a点。

7dc5b3cfb00e4d578b08e02cac2d75ba.png

2、穷举法

        穷举法就是求所有a为出发点,a为终点的全排列。

        全排列算法:

(1)全排列算法使用递归算法,如果迭代到最后一层,则计算当前路线的加权和(注意第一个值不用进行全排列,因为初始点不动),minl存放加权和最小的值。

(2)若没有迭代到最后一层,则遍历k<=i<=n,k为当前全排列迭代的层数,交换op[i]和op[k],继续排列k+1层,再交换op[i]和op[k],保证对后续没有影响。

fbeb6d7d23444ed58d878cb68cba198a.png

代码如下:

//旅行商问题
public class tsp {public static final int MAX=9999;public static int[][] a={{MAX,MAX,MAX,MAX,MAX},{MAX,MAX,2,5,8},{MAX,2,MAX,7,3},{MAX,5,7,MAX,1},{MAX,8,3,1,MAX},};public static int n=4;public static int minl=999;public static void main(String []args){int op[]=new int[n+1];for(int i=1;i<=n;i++)op[i]=i;perm(2,op);System.out.println(minl);} //全排列算法public static void perm(int k,int op[]){if(k==n){  int tmp=calulate(op);minl=tmp<minl?tmp:minl;}for(int i=k;i<=n;i++){swap(i,k,op);perm(k+1,op);swap(i,k,op);}}//交换数组中元素public static void swap(int i,int k,int []op){int tmp=op[i];op[i]=op[k];op[k]=tmp;}//计算全排列后当前排列的加权和public static int calulate(int []op){int tot=0;for(int i=1;i<n;i++){tot+=a[op[i]][op[i+1]];}tot+=a[op[n]][1];return tot;}
}

3、回溯法 

        时间复杂度分析:对于回溯法(本质上也是穷举法)和穷举法的时间复杂度都是O(n!),所以随着城市的数量增加,计算时间指数级增长,所以对于大规模的TSP问题可以采用动态规划、启发式算法等方法,来在短时间接近最优解,但这一定不是完备的。

        算法流程:

(1)首先判断是否叶子结点已经搜索,即满足k>n,则计算当前加权和,minl保存最小的加权和。

(2)若不满足,则遍历所有叶子结点,是否存在可以扩展的结点,进行扩展迭代到下一层,若没有则返回上一层。

(3)扩展条件:判断所有结点中满足a[k][i]!=MAX即待扩展节点与判断结点不可达,且x[k]==x[i]待扩展节点与判断结点相同,则不可扩展。也就是存在某一节点可以到达,且与上一个结点不同,则扩展。

//旅行商问题
public class tsp {public static final int MAX=9999;public static int[][] a={{MAX,MAX,MAX,MAX,MAX},{MAX,MAX,2,5,8},{MAX,2,MAX,7,3},{MAX,5,7,MAX,1},{MAX,8,3,1,MAX},};public static int n=4;public static int minl=999;public static void main(String []args){int op[]=new int[n+1];int x[]=new int[n+1];for(int i=1;i<=n;i++)op[i]=i;backtrack(1,x);System.out.println(minl);} //回溯法public static void backtrack(int k,int x[]){//注意这里一定要大于号,也就是已经判断好当前路径的叶子结点,再进行输出,或者替换最小值。if(k>n){int tot=0;for(int i=1;i<n;i++)tot+=a[x[i]][x[i+1]]; tot+=a[x[n]][x[1]];minl=minl<tot?minl:tot;}else{for(int i=1;i<=n;i++){x[k]=i;if(Ok(k, x))backtrack(k+1,x);}}}//判断是否能继续扩展public static boolean Ok(int k,int x[]){for(int i=1;i<=n;i++){if(a[k][i]!=MAX&&x[k]==x[i])return false;}return true;}
}

 

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

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

相关文章

Hadoop PseudoDistributed Mode 伪分布式

Hadoop PseudoDistributed Mode 伪分布式加粗样式 hadoop101hadoop102hadoop103192.168.171.101192.168.171.102192.168.171.103namenodesecondary namenoderecource managerdatanodedatanodedatanodenodemanagernodemanagernodemanagerjob historyjob logjob logjob log 1. …

基于人工势场法的航线规划

GitHub - zzuwz/Artificial-Potential-Field: 2D平面下的人工势场法 GitHub - mellody11/Artificial-Potential-Field: 机器人导航--人工势场法及其改进 matlab2020a可以运行

Selenium元素定位之页面检测技巧

在进行web自动化测试的时候进行XPath或者CSS定位&#xff0c;需要检测页面元素定位是否正确&#xff0c;如果用脚本去检测&#xff0c;那么效率是极低的。 一般网上推选装额外的插件来实现页面元素定位检测 如&#xff1a;firebug。 其实F12开发者工具就能直接在页面上检测元…

linux上重启mysql

1、先关闭 [rootHIS bin]# ./mysqladmin -h 127.0.0.1 -u root -p shutdown 2、 再重启 [rootHIS support-files]# ./mysql.server start

Android开发知识学习——Kotlin基础

函数声明 声明函数要用用 fun 关键字&#xff0c;就像声明类要用 class 关键字一样 「函数参数」的「参数类型」是在「参数名」的右边 函数的「返回值」在「函数参数」右边使用 : 分隔&#xff0c;没有返回值时可以省略 声明没有返回值的函数&#xff1a; fun main(){println…

微信小程序上传图片和上传视频的组件失效

微信小程序上传图片和上传视频的组件失效 今天公司的小程序展示图片和视频文字的页面上传图片组件突然失效&#xff0c;之前用的好好的&#xff0c;突然所有使用都都发现用不了&#xff0c;以为是代码出现问题&#xff0c;反复查了很久。换了一个openid居然就可以了&#xff0…

jeecg-uniapp 转成小程序的过程 以及报错 uniapp点击事件

uniapp 点击事件 tap: 单击事件 confirm: 回车事件 blur:失去焦点事件 touchstart: 触摸开始事件 touchmove: 触摸移动事件。 touchend: 触摸结束事件。 longpress: 长按事件。 input: 输入框内容变化事件。 change: 表单元素值变化事件。 submit: 表单提交事件。 scroll: 滚动…

Seata入门系列【19】分布式事务之CAP、BASE理论

1 CAP理论 CAP是以下三个词语的缩写&#xff1a; Consistency&#xff1a;一致性Availability&#xff1a;可用性Partition tolerance&#xff1a;分区容忍性 CAP理论的基础概念就是在分布式系统中&#xff0c;无法同时满足以上三点。 下面我们以一个简单的分布式系统&…

如何提高Python图像表格数据提取的准确率?

Python图像表格数据提取 1、数据来源2、目标图像3、图像文本提取4、图像灰度化与二值化可以提高识别准确率吗1、数据来源 国家统计局:http://www.stats.gov.cn/sj/ 数据来源:国家统计局中国统计年鉴2022年人口数及构成 2、目标图像 数据(部分)如下: 数据形式:http://www…

docker打包container成image,然后将image上传到docker hub

第一步&#xff1a;停止正在运行的容器 docker stop <container_name> eg: docker stop xuanjie_mlir 第二步&#xff1a;将对应的container打包成image docker commit <container_id> <镜像名&#xff1a;版本> eg&#xff1a;docker commit 005672e6d97a…

MPLAB X IDE 仿真打断点提示已中断的断点?

这种中间带裂缝的是无效断点。 原因可能与XC编译器的优化有关&#xff0c;最后生成的汇编与C语言并不是一一对应的(官方给的解释是效率高)。所以这一行C语言转换的汇编代码可能并不在这个位置&#xff0c;也可能与其它汇编合并后根本就没有 我的解决方法是把优化等级调到最低&a…

导轨电表适不适合家用?

导轨电表&#xff0c;作为一种新型的电能计量设备&#xff0c;近年来在我国得到了广泛的应用。然而&#xff0c;对于家用市场来说&#xff0c;导轨电表是否适用仍然存在争议。那么&#xff0c;导轨电表适不适合家用呢&#xff1f;接下来&#xff0c;小编来为大家讲解下&#xf…

计算机网络第4章-网络层(1)

引子 网络层能够被分解为两个相互作用的部分&#xff1a; 数据平面和控制平面。 网络层概述 路由器具有截断的协议栈&#xff0c;即没有网络层以上的部分。 如下图所示&#xff0c;是一个简单网络&#xff1a; 转发和路由选择&#xff1a;数据平面和控制平面 网络层的作用…

精选8款UML图工具,闭眼入!

在现代软件开发领域&#xff0c;UML&#xff08;统一建模语言&#xff09;图是不可或缺的工具之一&#xff0c;用于可视化和通信复杂系统的结构和设计。然而&#xff0c;在选择合适的UML图工具时&#xff0c;你需要考虑多个因素&#xff0c;如项目规模、团队协作需求、功能复杂…

Docker dnmp 多版本php安装 php8.2

Laravel9 开发需要用到php8.1以上的版本&#xff0c;而dnmp只支持到php8.0。安装php8.2的步骤如下&#xff1a; 1. 从/services/php80目录复制一份出来&#xff0c;重命名为php82&#xff0c;extensions目录只保留 install.sh 和 install-php-extensions 这两个文件 2. 修改.en…

苹果IOS系统webglcontextlost问题-解决方案

问题描述 在IOS手机 解码视频流的时候&#xff0c;第一次可以正常播放&#xff0c;但只要IOS手机熄屏&#xff0c;再重新唤醒&#xff0c;就会一直播放失败&#xff0c;无论换哪个浏览器都不行。安卓手机则一切正常。 经过排查&#xff0c;发现 IOS手机 的浏览器会无故 webGL…

突破性技术!开源多模态模型—MiniGPT-5

多模态生成一直是OpenAI、微软、百度等科技巨头的重要研究领域&#xff0c;但如何实现连贯的文本和相关图像是一个棘手的难题。 为了突破技术瓶颈&#xff0c;加州大学圣克鲁斯分校研发了MiniGPT-5模型&#xff0c;并提出了全新技术概念“Generative Vokens "&#xff0c…

新工业革命?基于机器视觉技术分拣机器人的未来与发展

原创 | 文 BFT机器人 01 分拣机器人的应用 基于机器视觉技术的分拣机器人可以将工人从繁重的劳动中解放出来&#xff0c;大大提高了分拣的效率&#xff0c;因此被广泛地应用于食品、物流以及煤矿等多个行业。 1.1 分拣机器人在水果分拣中的应用 随着农业科技的发展和人民生活…

SOLIDWORKS参数化设计之部分打包 慧德敏学

参数化设计就是通过主参数来驱动整个模型的变化&#xff0c;类似于SOLIDWORKS的方程式中&#xff0c;使用全局变量来控制模型其它参数的变化&#xff0c;因此要做参数化就必须要确定好主参数以及变化逻辑。 我们之前介绍过SOLIDWORKS参数化设计软件-SolidKits.AutoWorks&#…

软件设计模式原则(二)开闭原则

继续讲解第二个重要的设计模式原则——开闭原则~ 一.定义 开闭原则(Open Closed Principle&#xff09;是编程中最基础、最重要的设计原则。一个软件实体如类&#xff0c;模块和函数应该对扩展开放(对提供方)&#xff0c;对修改关闭(对使用方)。用抽象构建框架&#xff0c;用实…