小编Fab*_*rum的帖子

我正在创建一个遗传算法来使用 python 和 networkx 解决旅行商问题。我添加了一个条件来收敛到满意的解决方案：路径不得有交叉边缘。我想知道 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, …