Christofides 1.0.1

用法

使用compute（）函数，该函数将距离矩阵作为输入，并返回christofides解，如下所示：

from Christofides import christofides
TSP = christofides.compute(distance_matrix)

或：

import Christofides
TSP = Christofides.christofides.compute(distance_matrix)

距离矩阵是一个上三角矩阵，从节点到自身的距离为0，因为christofides算法 只能应用于无向图。同时，节点到自身的距离实际上是0。 距离矩阵的示例如下： 距离矩阵=

[[0,45,65,15],
 [0,0,56,12],
 [0,0,0,89],
 [0,0,0,0]]

当我们要计算 距离=

[[0,45,65,15],
[45,0,56,12],
[65,56,0,89],
[15,12,89,0]]

christofides.compute（距离矩阵）返回带以下键的字典：

christofides_解决方案， 旅行费用， MST公司， 奇数顶点 索引， 多重图， 欧拉之旅

• dt> ChistoFieSex解：一个由TSP近似旅行组成的列表。< /dt >

  使用：tsp['chistofides_solution']

• 差旅成本：生成的TSP差旅成本。

  使用：tsp[“差旅费用”]

• mst：在christofides算法中生成的最小生成树。

  使用：tsp['mst']

• 奇数顶点：最小生成树的奇数顶点列表。

  使用：tsp[“奇数顶点”]

• 索引：奇数顶点的最小代价完美匹配的边列表。

  使用：tsp[“索引”]

• dt>多重图：索引后形成的多图边. < /dt>

  使用：tsp['multigraph']

• 欧拉旅行：多重图的欧拉旅行。

  使用：tsp['euler_tour']

christofides中的支持函数

• CSR生成三倍（CSR矩阵）
• mst的奇数顶点（距离矩阵，节点数）
• 最小munkres（距离矩阵，二部图）
• munkres_cost（索引，二部图）
• 二部图（距离矩阵、二部集、奇数顶点）
• 创建多图（距离矩阵、mst、索引、奇数顶点）
• Euler_Tour（多重图）
• 快捷方式游览（游览）
• 费用（Christofides_Tour，Distance_Matrix）

安装

python setup.py安装

附加套餐

神经病，神经病，神经病，口吃