TSP最近邻算法遇IndexError：布尔索引维度不匹配求助

问题概述 #

使用最近邻算法解决TSP时，基于.tsp文件转换得到的38×38距离矩阵运行代码，触发IndexError：

boolean index did not match indexed array along dimension 0; dimension is 1 but corresponding boolean dimension is 38

错误原因 #

networkx.to_numpy_matrix()返回的是numpy.matrix类型（二维矩阵对象），而非常规的numpy.ndarray。当执行A[last]时，得到的是一个1×38的二维矩阵（维度0长度为1），但用于过滤的mask是长度为38的一维布尔数组，两者维度不匹配，导致索引失败。

修复方案 #

将距离矩阵转换为numpy.ndarray类型，有两种可行方式：

1. 显式转换矩阵为数组：

   distance_matrix = np.array(networkx.to_numpy_matrix(graph))
   

2. 使用networkx直接生成数组的API（更简洁）：

   distance_matrix = networkx.to_numpy_array(graph)
   

修改后的完整代码 #

import numpy as np
import tsplib95
import networkx

# 加载TSP问题
problem = tsplib95.load('dj38.tsp')

# 转换为NetworkX图
graph = problem.get_graph()

# 转换为numpy数组类型的距离矩阵（修复核心点）
distance_matrix = networkx.to_numpy_array(graph)


def NN(A, start):
    """最近邻算法实现
    参数:
        A: N×N的距离数组
        start: 起始节点索引
    返回:
        路径列表与总路径成本
    """
    path = [start]
    cost = 0
    n = A.shape[0]
    mask = np.ones(n, dtype=bool)  # 标记未访问节点
    mask[start] = False

    for i in range(n-1):
        last = path[-1]
        # 过滤未访问节点的距离，找到最小值索引
        next_ind = np.argmin(A[last][mask])
        # 转换为原节点索引
        next_loc = np.arange(n)[mask][next_ind]
        path.append(next_loc)
        mask[next_loc] = False
        cost += A[last, next_loc]

    return path, cost

# 执行并打印结果
print(NN(distance_matrix, 1))

补充说明 #

• numpy.matrix是旧的矩阵类型，官方更推荐使用numpy.ndarray处理多维数组，避免维度匹配问题。
• 若起始节点索引从1开始，需确认TSP问题的节点编号是否与数组索引一致（dj38.tsp的节点通常从1开始，但转换为数组后索引会自动转为0-based，若需对应原节点编号，可后续调整路径输出）。

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