Hamilton问题求解-最近邻点法和最近插入法(Python实现)

简介: Hamilton问题求解-最近邻点法和最近插入法(Python实现)

Hamilton问题求解-最近邻点法和最近插入法

一、定义

1. 哈密顿通路

设G = < V , E >为一个图(有向图或者无向图)。G中经过的每个顶点一次且仅一次的通路称为哈密顿通路。(通路不一定回到起点,但一定穿过每个顶点一次且仅一次)

2. 哈密顿回路

设G = < V , E >为一个图(有向图或者无向图)。G中经过的每个顶点一次且仅一次的回路称为哈密顿回路。(回路要求穿过每个顶点一次后回到起点)

3. 性质

存在哈密顿通路(回路)的图一定是连通图

哈密顿通路是初级通路,哈密顿回路是初级回路

初级是通路(回路)指除了起点和终点之外,所有的顶点和边都互不相同的通路(回路)

若图G GG中存在哈密顿回路,则它一定存在哈密顿通路

只有哈密顿通路,无哈密顿回路的图不叫哈密顿图

二、判定定理

目前没有判定哈密顿图的简单充要条件

image.png

image.png

三、求解算法

1. 最近邻点法

算法思想:每次将离当前顶点最近的顶点加入,一般只能找到近似解,不能找到最优解

算法步骤

  • 从网络中找一个点做为起点
  • 从剩下的点中找一个离上一个点最近的点加入
  • 重复步骤2
  • 将最后加入的点与起点连接构成回路

2.最近插入法

最近插入法(Nearest Insertion)于1977年提出,用于解决TSP问题,可以得到相对最近邻点法更优的解。

算法步骤

image.png

四、Python源码实现

Hamilton.py

import numpy as np
class HamiltonUtil:
    def __init__(self, input_matrix):
        self.graph = input_matrix
        self.point_num = np.shape(self.graph)[0]
        self.HamSolve = []
        self.HamLength = 0
    def search_min(self, index, matrix):
        min_val = np.float('inf')
        for i in matrix:
            if self.graph[index][i - 1] < min_val:
                min_val = self.graph[index][i - 1]
        return min_val
    def find_match_vex(self, index, match_val):
        ret_index = 0
        for i in self.graph[index]:
            if i != match_val:
                ret_index += 1
            else:
                break
        return ret_index
    def find_index(self, vec, value):
        index = 0
        for i in vec:
            if i != value:
                index += 1
            else:
                break
        return index
    def clear_stack(self):
        self.HamSolve = []
        self.HamLength = 0
    def neibor_point(self):
        self.clear_stack()
        start = 1
        V = np.arange(1, self.point_num + 1, 1)
        self.HamSolve.append(start)
        V = np.delete(V, start - 1)
        BetweenPoint = start
        while np.shape(V)[0] != 0:
            VWeight = self.search_min(BetweenPoint - 1, V)
            Next = self.find_match_vex(BetweenPoint - 1, VWeight) + 1
            self.HamSolve.append(Next)
            V = np.setdiff1d(V, Next)
            self.HamLength = self.HamLength + VWeight
            BetweenPoint = Next
        self.HamSolve.append(start)
        self.HamLength = self.HamLength + self.graph[Next - 1][start - 1]
    def nearest_insertion(self):
        self.clear_stack()
        start = 1
        V = np.arange(1, self.point_num + 1, 1)
        self.HamSolve.append(start)
        V = np.setdiff1d(V, self.HamSolve)
        BetweenPoint = start
        VWeight = self.search_min(BetweenPoint - 1, V)
        Next = self.find_match_vex(BetweenPoint - 1, VWeight) + 1
        self.HamSolve.append(Next)
        self.HamSolve.append(start)
        V = np.setdiff1d(V, Next)
        self.HamLength = self.HamLength + VWeight + self.graph[Next - 1][start - 1]
        BetweenPoint = Next
        while np.shape(V)[0] != 0:
            HamPoint = list(set(self.HamSolve))
            NearestPoint = 0
            NearWeight = np.zeros((len(HamPoint),), dtype=float)
            NearPoint = np.zeros((len(HamPoint),), dtype=int)
            for i in range(len(HamPoint)):
                NearWeight[i] = self.search_min(HamPoint[i] - 1, V)
                NearPoint[i] = self.find_match_vex(HamPoint[i] - 1, NearWeight[i]) + 1
            NearestPoint = NearPoint[self.find_index(NearWeight, np.min(NearWeight))]
            HamIncrement = np.zeros((len(self.HamSolve) - 1,), dtype=float)
            for i in range(len(self.HamSolve) - 1):
                HamIncrement[i] = self.graph[self.HamSolve[i] - 1][NearestPoint - 1] + \
                                  self.graph[NearestPoint - 1][self.HamSolve[i + 1] - 1] - \
                                  self.graph[self.HamSolve[i] - 1][self.HamSolve[i + 1] - 1]
            MinHamIncrement = np.min(HamIncrement)
            InsertPoint = self.find_index(HamIncrement, MinHamIncrement) + 1
            self.HamSolve.insert(InsertPoint, NearestPoint)
            self.HamLength += MinHamIncrement
            V = np.setdiff1d(V, NearestPoint)

五、运行测试实例

main.py

from Hamilton import HamiltonUtil
import numpy as np
if __name__ == '__main__':
    E = np.array([[np.float('inf'), 10, 6, 8, 7, 15],
                  [10, np.float('inf'), 5, 20, 15, 16],
                  [6, 5, np.float('inf'), 14, 7, 8],
                  [8, 20, 14, np.float('inf'), 4, 12],
                  [7, 15, 7, 4, np.float('inf'), 6],
                  [15, 16, 8, 12, 6, np.float('inf')]], dtype=float)
    neibor_point = HamiltonUtil(E)
    # 最邻近点法
    neibor_point.neibor_point()
    print(neibor_point.HamSolve)
    print(neibor_point.HamLength)
    E = np.array([[np.float('inf'), 10, 6, 8, 7, 15],
                  [10, np.float('inf'), 5, 20, 15, 16],
                  [6, 5, np.float('inf'), 14, 7, 8],
                  [8, 20, 14, np.float('inf'), 4, 12],
                  [7, 15, 7, 4, np.float('inf'), 6],
                  [15, 16, 8, 12, 6, np.float('inf')]], dtype=float)
    nearest_insertion = HamiltonUtil(E)
    # 最近插值法
    nearest_insertion.nearest_insertion()
    print(nearest_insertion.HamSolve)
    print(nearest_insertion.HamLength)
相关文章
vuecli3 启动服务的时候报错:TypeError: Cannot read property ‘upgrade‘ of undefined
vuecli3 启动服务的时候报错:TypeError: Cannot read property ‘upgrade‘ of undefined
407 0
vuecli3 启动服务的时候报错:TypeError: Cannot read property ‘upgrade‘ of undefined
|
12月前
|
监控 安全 物联网
13位物联网卡与11位物联网卡有什么不同
物联网卡(IoT卡)的13位号码和11位号码之间存在一些关键差异。以下是针对这两者区别的详细操作步骤和解释:
|
8月前
|
数据可视化 算法 数据挖掘
用傅里叶变换解码时间序列:从频域视角解析季节性模式
本文介绍了如何使用傅里叶变换和周期图分析来识别时间序列中的季节性模式,特别是在能源消耗数据中。通过Python实现傅里叶变换和周期图,可以有效提取并量化时间序列中的主要和次要频率成分,克服传统可视化分析的局限性。这对于准确捕捉时间序列中的季节性变化具有重要意义。文章以AEP能源消耗数据为例,展示了如何应用这些方法识别日、周、半年等周期模式。
348 3
用傅里叶变换解码时间序列:从频域视角解析季节性模式
|
算法 定位技术
路径规划算法 - 求解最短路径 - A*(A-Star)算法
路径规划算法 - 求解最短路径 - A*(A-Star)算法
1631 1
|
运维 监控 安全
物联网卡:物联网卡为什么不能使用在手机上
物联网卡(IoT SIM卡)通常是为物联网设备设计的,这些设备包括但不限于智能家居设备、可穿戴设备、工业监控设备等。它们与用于智能手机的SIM卡有所不同,主要是因为设计目标、功能限制、资费结构以及网络接入策略上的差异。以下是物联网卡不能直接在手机上使用的主要原因:
|
JavaScript 前端开发
JavaScript如何设置定时器,怎么清除定时器
JavaScript如何设置定时器,怎么清除定时器
392 3
|
Python
Python实现因子分析(附案例实战)
Python实现因子分析(附案例实战)
2490 0
Python实现因子分析(附案例实战)
|
传感器 人工智能 IDE
探索电子技术的魅力:使用Arduino实现LED闪
探索电子技术的魅力:使用Arduino实现LED闪