如何用NetworkX验证TSP路径是否存在交叉边？

问题背景 #

我用Python和NetworkX实现遗传算法解决旅行商问题(TSP)，为了让算法收敛到满意解，添加了一个收敛条件：路径不能存在交叉边。想知道NetworkX中有没有快速验证图中是否存在交叉边的函数，或者如何自行实现该功能。

我的图基于点列表path创建，每个点包含x、y坐标，点的序列即为旅行路径的索引。创建nx.Graph()对象的代码如下：

G = nx.Graph()
for i in range(len(path)):
    G.add_node(i, pos=(path[i].x, path[i].y))
    
for i in range(len(path)-1):
    G.add_edge(i, i+1)
G.add_edge(len(path)-1, 0)

未收敛至最优解的示例路径：

通过nx.get_node_attributes(G,'pos')获取的节点坐标如下：

{0: (494, 680), 1: (431, 679), 2: (217, 565), 3: (197, 581), 4: (162, 586), 5: (90, 522), 6:(138, 508), 7: (217, 454), 8: (256, 275), 9: (118, 57), 10: (362, 139), 11: (673, 89), 12: (738, 153), 13: (884, 119), 14: (687, 542), 15: (720, 618), 16: (745, 737), 17: (895, 887), 18: (902, 574), 19: (910, 337), 20: (823, 371), 21: (601, 345), 22: (608, 302), 23: (436, 294), 24: (515, 384), 25: (646, 495)}

这个收敛条件的依据是一篇TSP科普文章，核心结论为：平面点集的最优TSP路径不存在交叉边。

解答 #

一、NetworkX是否有内置函数？ #

NetworkX没有直接提供检测TSP路径交叉边的内置函数，它的定位是通用图算法库，不聚焦于这类几何路径的特定验证逻辑，因此需要自行实现交叉检测。

二、自行实现交叉边检测的方案 #

核心逻辑

平面中两条线段（边）交叉的判定需满足：

• 两条线段的四个端点互相跨立对方线段（即每条线段的两个端点分别在另一条线段的两侧）；
• 排除端点重合或共线不重叠的情况（TSP路径是简单环，相邻边才会共享端点，可提前过滤此类边对）。

代码实现

def ccw(A, B, C):
    """判断三点A、B、C的逆时针方向
    返回值：>0 逆时针；=0 共线；<0 顺时针
    """
    return (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])

def segments_intersect(a1, a2, b1, b2):
    """判断线段a1a2与b1b2是否交叉（不包含端点接触的情况）"""
    # 计算四个跨立判定值
    ccw1 = ccw(a1, a2, b1)
    ccw2 = ccw(a1, a2, b2)
    ccw3 = ccw(b1, b2, a1)
    ccw4 = ccw(b1, b2, a2)
    
    # 两条线段互相跨立则交叉
    if (ccw1 * ccw2 < 0) and (ccw3 * ccw4 < 0):
        return True
    
    # 排除共线或端点接触的情况（TSP场景下可忽略）
    return False

def has_crossing_edges(G):
    """判断TSP路径图G中是否存在交叉边"""
    pos = nx.get_node_attributes(G, 'pos')
    node_count = len(pos)
    # 提取路径的所有边（包括环的闭合边）
    edges = []
    for i in range(node_count - 1):
        edges.append((pos[i], pos[i+1]))
    edges.append((pos[node_count - 1], pos[0]))
    
    # 遍历所有非相邻边对
    for i in range(len(edges)):
        for j in range(i + 2, len(edges)):
            # 处理环形路径的首尾相邻情况
            if i == len(edges)-1 and j == 0:
                continue
            seg1_start, seg1_end = edges[i]
            seg2_start, seg2_end = edges[j]
            if segments_intersect(seg1_start, seg1_end, seg2_start, seg2_end):
                return True
    return False

使用示例

# 检测你的TSP路径图是否存在交叉边
if has_crossing_edges(G):
    print("路径存在交叉边，未满足收敛条件")
else:
    print("路径无交叉边，满足收敛条件")

三、优化建议 #

• 若处理的TSP点数量较大（>100），双重循环的O(n²)时间复杂度可能成为瓶颈，可考虑扫描线算法等更高效的几何检测方法；但对于遗传算法中常见的小规模种群，O(n²)的性能完全足够。
• 可将交叉检测逻辑集成到遗传算法的适应度函数中，直接对带有交叉边的路径施加惩罚，加速算法收敛到无交叉的最优路径。

内容的提问来源于stack exchange，提问作者Fabricio Brum