本文分别以最近邻点法和最近插入法求解TSP问题中的Hamilton回路问题。用以下例题作为求解案例
V1 | V2 | V3 | V4 | V5 | V6 | |
---|---|---|---|---|---|---|
V1 | 0 | 10 | 6 | 8 | 7 | 15 |
V2 | 10 | 0 | 5 | 20 | 15 | 16 |
V3 | 6 | 5 | 0 | 14 | 7 | 8 |
V4 | 8 | 20 | 14 | 0 | 4 | 12 |
V5 | 7 | 15 | 7 | 4 | 0 | 6 |
V6 | 15 | 16 | 8 | 12 | 6 | 0 |
最近邻点法的主要逻辑是通过寻找离当前顶点最近的顶点来寻找回来,这样的计算方式比较简便,但是很多情况下只能找到近似解,找不到最优解。
step1.从网络中找一个点作为起点
step2.从剩下的点中找一个离上一个点最近的点加入
step3.重复step2
step4.将最后加入的点与起点连接。这样就构成了一个回路。
Matlab代码如下:
%% 最近邻点法求解Hamilton回路
clc;clear all;close all;
%% 参数初始化
Start=1; %默认取第一个点作为起点
%初始化邻接矩阵
E=[inf 10 6 8 7 15
10 inf 5 20 15 16
6 5 inf 14 7 8
8 20 14 inf 4 12
7 15 7 4 inf 6
15 16 8 12 6 inf];
%顶点集长度
PointNum=size(E,1);
% 顶点集
V=linspace(1,PointNum,PointNum);
%Hamilton回路解集
HamSolve=[];
%Hamilton回路长度
HamLength=0;
%% 最近邻点法迭代过程
%将起点加入回路解集
HamSolve=[HamSolve,Start];
%将起点从顶点集中去掉
V=setdiff(V,HamSolve);
%当前点
BetweenPoint=Start;
while ~isempty(V)
%找到离起点最近的点
VWeight=min(E(BetweenPoint,V));
Next=find(E(BetweenPoint,:)==VWeight);
%将离起点最近的点加入解集
HamSolve=[HamSolve,Next];
%将找到的点从顶点集中去掉
V=setdiff(V,Next);
%计算Hamilton回路长度
HamLength=HamLength+VWeight;
%将当前点修改为下一个点
BetweenPoint=Next;
end
%将起点加入
HamSolve=[HamSolve,Start]
%计算最后的回路长度
HamLength=HamLength+E(Next,Start)
求解结果:
最近插入法(Nearest Insertion)是Rosenkrantz和Stearns等人在1977年提出的另一种解决TSP问题的算法,它比最近邻点法复杂,但可得到相对满意的解。
%% 最近插入法求解Hamilton回路
clc;clear all;close all;
%% 初始化参数
Start=1; %默认取第一个点作为起点
%初始化邻接矩阵
E=[inf 10 6 8 7 15
10 inf 5 20 15 16
6 5 inf 14 7 8
8 20 14 inf 4 12
7 15 7 4 inf 6
15 16 8 12 6 inf];
%顶点集长度
PointNum=size(E,1);
% 顶点集
V=linspace(1,PointNum,PointNum);
%Hamilton回路
HamSolve=[];
%Hamilton回路长度
HamLength=0;
%% 最近插入法迭代过程
%将起点和终点加入回路解集
HamSolve=[HamSolve,Start,Start];
%将起点从顶点集中去掉
V=setdiff(V,HamSolve);
%当前点
BetweenPoint=Start;
%找到离起点最近的点
VWeight=min(E(BetweenPoint,V));
Next=find(E(BetweenPoint,:)==VWeight);
%Hamilton回路
HamSolve=[HamSolve(1),Next,HamSolve(end)];
%将找到的点从顶点集中去掉
V=setdiff(V,Next);
%计算Hamilton回路长度
HamLength=HamLength+VWeight+E(Next,Start);
%将当前点修改为下一个点
BetweenPoint=Next;
while ~isempty(V)
%Hamilton回路解集
HamPoint=unique(HamSolve);
%找到里当前子回路中顶点最近的顶点
NearestPoint=0;
NearWeight=zeros(1,length(HamPoint));
NearPoint=zeros(1,length(HamPoint));
for Point=1:length(HamPoint)
NearWeight(Point)=min(E(HamPoint(Point),V));
NearPoint(Point)=find(E(HamPoint(Point),:)==NearWeight(Point),1);
end
NearestPoint=NearPoint(find(NearWeight==min(NearWeight)));
%计算回路增量
HamIncrement=zeros(1,length(HamSolve)-1);
for PoinInc=1:(length(HamSolve)-1)
HamIncrement(PoinInc)=E(HamSolve(PoinInc),NearestPoint(1))+E(NearestPoint(1),HamSolve(PoinInc+1))-E(HamSolve(PoinInc),HamSolve(PoinInc+1));
end
[MinHamIncrement,InsertPoint]=min(HamIncrement);
%将点插入Hamilton回路
HamSolve=[HamSolve(1:InsertPoint),NearestPoint(1),HamSolve(InsertPoint+1:end)];
%计算Hamilton回路长度
HamLength=HamLength+MinHamIncrement;
%将已插入的点去除
V=setdiff(V,NearestPoint(1));
end
HamSolve
HamLength
求解结果:
文章浏览阅读1.2k次,点赞35次,收藏18次。AutowiredPostConstruct 注释用于在依赖关系注入完成之后需要执行的方法上,以执行任何初始化。此方法必须在将类放入服务之前调用。支持依赖关系注入的所有类都必须支持此注释。即使类没有请求注入任何资源,用 PostConstruct 注释的方法也必须被调用。只有一个方法可以用此注释进行注释。_springboot2.7获取bean
文章浏览阅读2.1k次。理论介绍 节点定义package logistic;public class Instance { public int label; public double[] x; public Instance(){} public Instance(int label,double[] x){ this.label = label; th_logisticregression java
文章浏览阅读981次,点赞21次,收藏18次。本书是获得了很多读者好评的Linux经典畅销书**《Linux从入门到精通》的第2版**。下面我们来进行文件的恢复,执行下文中的lsof命令,在其返回结果中我们可以看到test-recovery.txt (deleted)被删除了,但是其存在一个进程tail使用它,tail进程的进程编号是1535。我们看到文件名为3的文件,就是我们刚刚“误删除”的文件,所以我们使用下面的cp命令把它恢复回去。命令进入该进程的文件目录下,1535是tail进程的进程id,这个文件目录里包含了若干该进程正在打开使用的文件。
文章浏览阅读10w+次,点赞12次,收藏72次。RTMP(Real Time Messaging Protocol)实时消息传输协议是Adobe公司提出得一种媒体流传输协议,其提供了一个双向得通道消息服务,意图在通信端之间传递带有时间信息得视频、音频和数据消息流,其通过对不同类型得消息分配不同得优先级,进而在网传能力限制下确定各种消息得传输次序。_rtmp
文章浏览阅读64次。2017年12月的计算机等级考试将要来临!出国留学网为考生们整理了2017年12月计算机一级MSOffice考试习题,希望能帮到大家,想了解更多计算机等级考试消息,请关注我们,我们会第一时间更新。2017年12月计算机一级MSOffice考试习题(二)一、单选题1). 计算机最主要的工作特点是( )。A.存储程序与自动控制B.高速度与高精度C.可靠性与可用性D.有记忆能力正确答案:A答案解析:计算...
文章浏览阅读356次。在学MYSQL的时候刚刚好看到了这个提权,很久之前用过别人现成的,但是一直时间没去细想, 这次就自己复现学习下。 0x00 UDF 什么是UDF? UDF (user defined function),即用户自定义函数。是通过添加新函数,对MySQL的功能进行扩充,就像使..._the provided input file '/usr/share/metasploit-framework/data/exploits/mysql
文章浏览阅读3.1w次,点赞71次,收藏485次。webService一 WebService概述1.1 WebService是什么WebService是一种跨编程语言和跨操作系统平台的远程调用技术。Web service是一个平台独立的,低耦合的,自包含的、基于可编程的web的应用程序,可使用开放的XML(标准通用标记语言下的一个子集)标准...
文章浏览阅读1w次。前言照例给出官网:Retrofit官网其实大家学习的时候,完全可以按照官网Introduction,自己写一个例子来运行。但是百密一疏,官网可能忘记添加了一句非常重要的话,导致你可能出现如下错误:Could not locate ResponseBody converter错误信息:Caused by: java.lang.IllegalArgumentException: Could not l_已添加addconverterfactory 但是 could not locate responsebody converter
文章浏览阅读1k次。一套键鼠控制Windows+Linux——Synergy在Windows10和Ubuntu18.04共控的实践Synergy简介准备工作(重要)Windows服务端配置Ubuntu客户端配置配置开机启动Synergy简介Synergy能够通过IP地址实现一套键鼠对多系统、多终端进行控制,免去了对不同终端操作时频繁切换键鼠的麻烦,可跨平台使用,拥有Linux、MacOS、Windows多个版本。Synergy应用分服务端和客户端,服务端即主控端,Synergy会共享连接服务端的键鼠给客户端终端使用。本文_linux 18.04 synergy
文章浏览阅读374次。写demo的时候遇到了很多问题,记录一下。安装nacos1.4.0配置mysql数据库,新建nacos_config数据库,并根据初始化脚本新建表,使配置从数据库读取,可单机模式启动也可以集群模式启动,启动时 ./start.sh -m standaloneapplication.properties 主要是db部分配置## Copyright 1999-2018 Alibaba Group Holding Ltd.## Licensed under the Apache License,_seata1.4.0 +nacos 集成
文章浏览阅读833次。iperf使用方法详解 iperf3是一款带宽测试工具,它支持调节各种参数,比如通信协议,数据包个数,发送持续时间,测试完会报告网络带宽,丢包率和其他参数。 安装 sudo apt-get install iperf3 iPerf3常用的参数: -c :指定客户端模式。例如:iperf3 -c 192.168.1.100。这将使用客户端模式连接到IP地址为192.16..._iperf客户端指定ip地址
文章浏览阅读7.4k次。 写这个函数目的不是为了和C/C++库中的函数在性能和安全性上一比高低,只是为了给那些喜欢探讨函数内部实现的网友,提供一种从浮点性到字符串转换的一种途径。 浮点数是有精度限制的,所以即使我们在使用C/C++中的sprintf或者cout 限制,当然这个精度限制是可以修改的。比方在C++中,我们可以cout.precision(10),不过这样设置的整个输出字符长度为10,而不是特定的小数点后1_c++浮点数 转 字符串 精度损失最小