首页 > 其他分享 >图与网络——TSP问题精解

图与网络——TSP问题精解

时间:2024-09-12 22:46:15浏览次数:7  
标签:distance point 路径 网络 start path 精解 TSP

旅行商问题(Travelling Salesman Problem, TSP)是组合优化领域中的经典问题之一。TSP的概念最早可以追溯到18世纪,瑞士数学家欧拉在解决柯尼斯堡七桥问题时首次提出了关于图中遍历的问题。不过,作为一个优化问题,TSP在19世纪才开始形成系统的研究。1920年代,TSP被德国数学家卡尔·孟格尔首次形式化提出,他称之为"最短汉密尔顿路径问题"。1954年,数学家D.R. Fulkerson、S. Dantzig和S.M. Johnson通过线性规划的方法为TSP问题提供了新的求解思路,他们在美国兰德公司首次使用计算机对TSP问题进行求解,为TSP的现代研究奠定了基础。TSP是NP-hard问题,这意味着随着城市数量的增加,求解问题的难度呈指数级增长。

34城市TSP 漫画TSP

一、TSP问题描述

旅行推销员问题(Travelling salesman problem, 简记为TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。
1978年,波恩大学的一位数学家面临一个经典的旅行商问题(TSP),该问题的背景是在当时的西德,旅行商需要访问120个有铁路连接的城市,并找到一条最短的回路,使得旅行商经过每个城市一次并返回起点。这一问题不仅在当时具有理论研究价值,也对实际应用产生了深远影响,尤其是在交通运输、物流规划和网络设计等领域。该问题的复杂性来源于城市之间的距离以及路径选择的数量。西德的120个城市之间的距离可以通过铁路局提供的精确数据获得。在这种情况下,问题变得更加具体:在这些城市之间,如何找到一条最短的路径,使得每个城市都被访问一次,并最终回到起点?从数学角度来看,这就是一个典型的TSP问题,涉及到如何优化路径长度。由于有120个城市,这意味着每个城市之间有120x119/2=7,140条可能的连接路径(变量)。在这种规模下,TSP问题的复杂性呈现指数增长,因此不能通过简单的蛮力方法去解答。每新增一个城市,可能的路径数量都会急剧增加,这使得该问题成为了当时计算能力的重大挑战。

1.1 TSP问题的数学模型

对于有向图 \(G=(V, A)\) ,其中\(V=U \cup\{0\},|A|=|V| \times(|V|-1), c_{i j},(i, j) \in A\) 为弧泊的成本,TSP可以被分解为以下四个约束和其目标函数。首先最后一个约束指变量 \(x_{ij}\) 为二进制变量, 其等于 1 当仅当弧\(ij\)属于解回路。约束(1)和(2)用于定义闭合回路,即任意须点 \(/ \mathrm{i}\) ,解回路中必有且仅有一条弧以其作为起点的同时有且仅有一条弧以其作为终点。但是仅仅有约束 (1) 和 (2) 是不足以定义TSP,因为虽然保证了解为闭合回路却没有保证解仅含一条闭合回路、因此我们需要约束(3)以防止小圈的出现。约束 (3) 可以理解为对于任意点集合S(非\(V\)且含2个顶点及以上),必定存在至少有一个S中的顶点与S外的顶点相连接。综上, 我们可以得到以下数学模型:

\[\begin{aligned} & \operatorname{Min} \sum_{(i, j) \in A} c_{i j} x_{i j} \\ & \text { subject to } \\ & \qquad \sum_{i \in V \backslash(j\}} x_{i j}=1, j \in V \\ & \sum_{j \in V \backslash\{i\}} x_{i j}=1, i \in V \\ & \sum_{i \in S} \sum_{j \in S} x_{i j} \geq 1, S \subsetneq V,|S| \geq 2 \\ & x_{i j} \in\{0,1\},(i, j) \in A \end{aligned} \]

其中约束(3)尽管可被简化但仍使得该问题成为了NP问题。

1.2 应用场景

尽管TSP问题看似抽象,但其应用非常广泛,几乎涵盖了众多实际生活和工业领域。以下是一些典型的应用场景:

物流与运输:TSP的最直接应用是在货物配送和路径规划中。企业需要在最短的时间内将货物从仓库运送到不同的地点,规划最优的运输路线可以极大地节省成本。著名的"快递员路径问题"就是TSP的一个变种。
芯片设计与制造:在电子电路设计中,电路板上的布线问题可被看作是TSP的一种形式。芯片制造商希望找到最短的布线路径,以减少信号传输时间,提高芯片效率。
数据分析与机器学习:在聚类分析中,TSP可以用于解决数据分类和特征选择的问题。它可以帮助研究人员寻找最优的聚类中心点排列,降低数据处理中的误差。
DNA测序:TSP也应用于生物信息学领域。在DNA测序过程中,通过TSP模型可以优化基因片段的排列顺序,以减少实验步骤。
机器人路径规划:TSP在自动化领域,尤其是机器人路径规划中,也有重要应用。机器人在执行任务时需要依次访问多个工作点,而TSP可以用于设计最优访问路径,从而提升工作效率。

二、TSP问题的Python求解

2.1 示例1

给出下面6个顶点的TSP环游路径。

\(c_{ij}\) 0 1 2 3 4 5
0 0 11 8.4 5.2 4.8 2.6
1 11 0 7.4 4.2 10.2 12
2 8.4 7.4 0 3.2 6.4 11
3 5.2 4.2 3.2 0 6 7.8
4 4.8 10.2 6.4 6 0 10.2
5 2.6 12 11 7.8 10.2 0
import numpy as np
import matplotlib.pyplot as plt

# Greedy TSP算法
def greedy_tsp(distance_matrix, start_point):
    n = len(distance_matrix)
    visit_mask = [False] * n
    path = [start_point]
    visit_mask[start_point] = True
    current_point = start_point
    total_distance = 0  # 初始化总路径长度
    
    while len(path) < n:
        next_point = None
        min_dist = float('inf')
        for i in range(n):
            if not visit_mask[i] and distance_matrix[current_point][i] < min_dist:
                min_dist = distance_matrix[current_point][i]
                next_point = i
        path.append(next_point)
        visit_mask[next_point] = True
        total_distance += min_dist  # 累加路径长度
        current_point = next_point
    
    # 返回起点,并累加最后一段的距离
    total_distance += distance_matrix[current_point][start_point]
    path.append(start_point)  
    
    return path, total_distance

# 距离矩阵
distance_matrix = [
    [0, 11, 8.4, 5.2, 4.8, 2.6],
    [11, 0, 7.4, 4.2, 10.2, 12],
    [8.4, 7.4, 0, 3.2, 6.4, 11],
    [5.2, 4.2, 3.2, 0, 6, 7.8],
    [4.8, 10.2, 6.4, 6, 0, 10.2],
    [2.6, 12, 11, 7.8, 10.2, 0]
]

# 开始点为0
start_point = 0
tour_path, tour_length = greedy_tsp(distance_matrix, start_point)

print("访问路径:", tour_path)
print("路径总长度:", tour_length)

# 绘制路径
def draw_tsp_path_with_distances(path, distance_matrix):
    # 生成节点的坐标,均匀分布在圆上
    n = len(distance_matrix)
    theta = np.linspace(0, 2 * np.pi, n, endpoint=False)
    radius = 10
    x = radius * np.cos(theta)
    y = radius * np.sin(theta)

    plt.figure(figsize=(12, 12))  # 图像放大至12x12
    
    # 绘制节点,扩大节点大小
    plt.scatter(x, y, c='lightblue', s=3000, edgecolors='black', zorder=2)  # 节点扩大3倍
    
    # 标注节点编号,扩大字号
    for i in range(n):
        plt.text(x[i], y[i], str(i), fontsize=36, ha='center', va='center', color='black')  # 字号扩大3倍
    
    # 绘制路径并标注距离
    for i in range(len(path) - 1):
        start, end = path[i], path[i+1]
        plt.plot([x[start], x[end]], [y[start], y[end]], 'r-', lw=6, zorder=1)  # 线宽扩大3倍
        
        # 计算线的中点,标注距离
        mid_x = (x[start] + x[end]) / 2
        mid_y = (y[start] + y[end]) / 2
        dist = distance_matrix[start][end]
        plt.text(mid_x, mid_y, f'{dist}', fontsize=30, color='blue', ha='center', va='center')  # 距离标注字号扩大3倍
    
    # 标注起点,扩大节点大小
    plt.scatter(x[start_point], y[start_point], c='red', s=3000, edgecolors='black', zorder=3)  # 起点扩大3倍
    
    plt.title("TSP Path with Distances (Scaled)", fontsize=24)  # 标题字号扩大
    plt.gca().set_aspect('equal', adjustable='box')
    plt.axis('off')  # 关闭坐标轴
    plt.show()

# 绘制TSP路径
draw_tsp_path_with_distances(tour_path, distance_matrix)  # 包括最后一个回到起点的0
TSP顶点布局 路径和长度
访问路径: [0, 5, 3, 2, 4, 1, 0] ;路径总长度: 41.2

2.2 示例2

距离(公里) C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 门店
C1 - 2.6 3.7 4.1 3.1 3.5 1.7 4.2 1.7 3.5 2.7
C2 2.6 - 1.6 2.7 3.2 1.1 2.6 2.2 1.2 2.4 1.5
C3 3.7 1.6 - 1.3 2.8 0.7 3.0 0.6 2.4 1.4 1.3
C4 4.1 2.7 1.3 - 2.1 2.1 2.9 0.9 3.1 0.7 1.5
C5 3.1 3.2 2.8 2.1 - 3.2 1.4 2.8 2.7 1.5 1.8
C6 3.5 1.1 0.7 2.1 3.2 - 3.1 1.3 2.1 2.0 1.5
C7 1.7 2.6 3.0 2.9 1.4 3.1 - 3.3 1.4 2.2 1.7
C8 4.2 2.2 0.6 0.9 2.8 1.3 3.3 - 2.9 1.3 1.6
C9 1.7 1.2 2.4 3.1 2.7 2.1 1.4 2.9 - 2.5 0.9
C10 3.5 2.4 1.4 0.7 1.5 2.0 2.2 1.3 2.5 - 9.0
门店 2.7 1.5 1.3 1.5 1.8 1.5 1.7 1.6 0.9 9.0 -

基于上表提供的距离矩阵来求解TSP,并绘制相应的网络图,我们可以使用以下步骤:

TSP问题建模:根据给出的距离矩阵,构建一个完整图,其中节点表示各个城市(C1, C2, ..., C10,门店),边的权重表示城市之间的距离。
求解TSP问题:使用网络X库或其他优化算法来解决TSP问题,寻找从门店出发,经过所有城市后返回门店的最短路径。
绘制网络图:绘制图形,将门店置于中心,其他节点围绕门店排列,并标注城市之间的距离。

import numpy as np
import matplotlib.pyplot as plt

# Greedy TSP算法
def greedy_tsp(distance_matrix, start_point):
    n = len(distance_matrix)
    visit_mask = [False] * n
    path = [start_point]
    visit_mask[start_point] = True
    current_point = start_point
    total_distance = 0  # 初始化总路径长度
    
    while len(path) < n:
        next_point = None
        min_dist = float('inf')
        for i in range(n):
            if not visit_mask[i] and distance_matrix[current_point][i] < min_dist:
                min_dist = distance_matrix[current_point][i]
                next_point = i
        path.append(next_point)
        visit_mask[next_point] = True
        total_distance += min_dist  # 累加路径长度
        current_point = next_point
    
    # 返回起点,并累加最后一段的距离
    total_distance += distance_matrix[current_point][start_point]
    path.append(start_point)  
    
    return path, total_distance

# 距离矩阵
distance_matrix = [
    [0, 2.6, 3.7, 4.1, 3.1, 3.5, 1.7, 4.2, 1.7, 3.5, 2.7],
    [2.6, 0, 1.6, 2.7, 3.2, 1.1, 2.6, 2.2, 1.2, 2.4, 1.5],
    [3.7, 1.6, 0, 1.3, 2.8, 0.7, 3.0, 0.6, 2.4, 1.4, 1.3],
    [4.1, 2.7, 1.3, 0, 2.1, 2.1, 2.9, 0.9, 3.1, 0.7, 1.5],
    [3.1, 3.2, 2.8, 2.1, 0, 3.2, 1.4, 2.8, 2.7, 1.5, 1.8],
    [3.5, 1.1, 0.7, 2.1, 3.2, 0, 3.1, 1.3, 2.1, 2.0, 1.5],
    [1.7, 2.6, 3.0, 2.9, 1.4, 3.1, 0, 3.3, 1.4, 2.2, 1.7],
    [4.2, 2.2, 0.6, 0.9, 2.8, 1.3, 3.3, 0, 2.9, 1.3, 1.6],
    [1.7, 1.2, 2.4, 3.1, 2.7, 2.1, 1.4, 2.9, 0, 2.5, 0.9],
    [3.5, 2.4, 1.4, 0.7, 1.5, 2.0, 2.2, 1.3, 2.5, 0, 9.0],
    [2.7, 1.5, 1.3, 1.5, 1.8, 1.5, 1.7, 1.6, 0.9, 9.0, 0]
]

# 开始点为“门店”(即索引10)
start_point = 10
tour_path, tour_length = greedy_tsp(distance_matrix, start_point)

print("访问路径:", tour_path)
print("路径总长度:", tour_length)

# 绘制路径
def draw_tsp_path_with_distances(path, distance_matrix):
    # 生成节点的坐标,均匀分布在圆上
    n = len(distance_matrix)
    theta = np.linspace(0, 2 * np.pi, n, endpoint=False)
    radius = 10
    x = radius * np.cos(theta)
    y = radius * np.sin(theta)

    plt.figure(figsize=(12, 12))  # 图像放大至12x12
    
    # 绘制节点,扩大节点大小
    plt.scatter(x, y, c='lightblue', s=3000, edgecolors='black', zorder=2)  # 节点扩大3倍
    
    # 标注节点编号,扩大字号
    labels = ["C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9", "C10", "门店"]
    for i in range(n):
        plt.text(x[i], y[i], labels[i], fontsize=16, ha='center', va='center', color='black')
    
    # 绘制路径并标注距离
    for i in range(len(path) - 1):
        start, end = path[i], path[i+1]
        plt.plot([x[start], x[end]], [y[start], y[end]], 'r-', lw=2, zorder=1)
        
        # 计算线的中点,标注距离
        mid_x = (x[start] + x[end]) / 2
        mid_y = (y[start] + y[end]) / 2
        dist = distance_matrix[start][end]
        plt.text(mid_x, mid_y, f'{dist}', fontsize=12, color='blue', ha='center', va='center')
    
    # 标注起点,扩大节点大小
    plt.scatter(x[start_point], y[start_point], c='red', s=3000, edgecolors='black', zorder=3)
    
    plt.title("TSP Path with Distances", fontsize=24)
    plt.gca().set_aspect('equal', adjustable='box')
    plt.axis('off')
    plt.show()

# 绘制TSP路径
draw_tsp_path_with_distances(tour_path, distance_matrix)
访问路径: [10, 8, 1, 5, 2, 7, 3, 9, 4, 6, 0, 10]
路径总长度: 13.40

总结

随着计算能力的提升和优化算法的发展,TSP问题的求解已经取得了显著进展。在小规模问题(几十到几百个城市)的情况下,现代计算机和算法已经能够在合理时间内找到精确解。而对于中等规模问题(上千个城市),元启发式算法如模拟退火、遗传算法、蚁群算法等,可以在较短时间内得到接近最优解的结果。此外,研究人员也提出了一些基于特定领域的近似算法,这些算法在特定应用场景下表现出色。例如,在物流配送中,结合实际地理因素和交通情况的TSP模型可以生成更接地气的近似解,而不是仅依赖理论上的最短路径。在大规模问题(几千到上万城市)的场景下,虽然精确求解仍然极具挑战,但通过并行计算、分布式系统以及云计算的手段,可以极大地提升求解效率。近年来,随着量子计算的兴起,研究人员也开始探索如何利用量子计算加速TSP的求解。虽然量子计算的实用性还有待验证,但这一方向为未来的TSP研究带来了新的希望。TSP问题作为NP完全问题,虽然无法通过经典计算方法在多项式时间内获得全局最优解,TSP不仅是一个理论上的挑战,也是推动算法研究和实际应用发展的重要问题之一。

参考资料

  1. 算法设计分析(Kruskal构造最小生成树)
  2. 最小生成树(最小支撑树)算法

标签:distance,point,路径,网络,start,path,精解,TSP
From: https://www.cnblogs.com/haohai9309/p/18410905

相关文章

  • day09(网络编程基础)服务器模型
    目录服务器模型循环服务器并发服务器多进程多线程​​​​​​​IO多路复用​​​​​​​并发服务器总结服务器模型在网络通信中,通常一个服务器要连接多个客户端为了处理多个客户端的请求,通常有多种表现形式循环服务器一个服务器在同一时间只能处理一个客户......
  • 《深度学习》—— 神经网络基本结构
    前言深度学习是一种基于神经网络的机器学习算法,其核心在于构建由多层神经元组成的人工神经网络,这些层次能够捕捉数据中的复杂结构和抽象特征。神经网络通过调整连接各层的权重,从大量数据中自动学习并提取特征,进而实现预测或分类等任务。一、神经网络结构神经网络的基本组......
  • 最新24年计算机三级网络技术速过指南之校园网部署的解题方法与思路,包拿分教程
            多了不说少了不唠,直接进入主题。校园网分析这种体型,共15分,五个空,涉及到的考点有十余个,还有两道天选题。目录一、常规题型做题方法:    1.看题干提取要点    2.看图提取要点    3.看空的上下左右提取要点           ......
  • 网络流24题(8/24 待更新 码风良好可做代码参考)
    P2764最小路径覆盖问题建模方式拆所有点为入点和出点两部分,创建超级源点和超级汇点。连边:源点到所有入点边权值为1表示,每个点只进入一个流量,出点到汇点边权值也为1,表示出度也为1。然后对图求最大流。最小路径覆盖=总点数-最大流代码实现lln,m;structedge{  l......
  • 数帝网络:架桥修路, 携手用友为企业数智化“换挡提速” | 商业创新同行者
    “能用众力,则无敌于天下矣;能用众智,则无畏于圣人矣。”《三国志·吴志·孙权传》里有这样一句发人深省的名言。在当代的名人名言中,异曲同工的格言不胜枚举,甚至成为指导产业发展的路径。当前,“生态”、“体系”、“伙伴”等词汇,以及“软件定义一切”的理念,已经成为企业数智化转型的重......
  • 网络协议头分析
    目录数据的传输与封装过程以太网完整帧以太网头部IP头TCP头数据的传输与封装过程以太网完整帧●对于网络层最大数据帧长度是1500字节●对于链路层最大数据长度是1518字节(1500+14+CRC)●发送时候,IP层协议栈程序检测到发送数据和包头总长度超过1500字节时候,会......
  • GNN图神经网络简单理解
    GNN简单理解文章目录一、GNN图神经网络综述1什么是图1.1图基础1.2图的分类1.3数据成图1.3.1图像转图1.3.2文本转图1.3.3其他转图1.4图结构化数据的问题类型1.4.1图层面任务graph-leveltask1.4.2节点层面任务node-leveltask1.4.3边层面任务edge-leve......
  • 初学者如何学习网络安全,零基础入门到精通,收藏这一篇就够了
    学习任何技术或知识前,需要培养好的学习习惯,投入时间和精力去进行钻研,培养兴趣和学习能力,并能通过搜索引擎解决问题。对于网络安全学习来说,要掌握学习方法,因为它的知识面广且复杂。之前看到一张"高效工作三部曲"的图,通过这种图是否可以延伸出“高效学习三部曲”呢?同样可以用......
  • 残差神经网络(李沐老师课程)
    resnet实现的细节:各种残差块各模型对比图代码:importtorchfromtorchimportnnfromtorch.nnimportfunctionalasFfromd2limporttorchasd2l​"""ResNet沿用了VGG完整的3*3卷积层设计。残差块里首先有2个有相同输出通道数的3*3卷积层。每个卷积......
  • 2024年最强网络安全学习路线,详细到直接上清华的教材!
     关键词:网络安全入门、渗透测试学习、零基础学安全、网络安全学习路线首先咱们聊聊,学习网络安全方向通常会有哪些问题前排提示:文末有CSDN官方认证Python入门资料包!1、打基础时间太长学基础花费很长时间,光语言都有几门,有些人会倒在学习linux系统及命令的路上,更多的人会倒......