从全0 one-hot向量出发遍历所有向量的最优最短路径求解方法

你这个问题本质是固定起点的最短哈密顿路径问题，属于轻量化的旅行商（TSP）子类，核心是先把每个one-hot向量对应为图的节点，节点间边权等于两个向量的汉明距离（也就是你说的移动步数，即向量不同维度的数量），再求解遍历所有节点的最小权路径即可，现成可用的实现方法分场景选就行：

• 向量总数量<20（需要精确最优解）
  直接用动态规划法求解，推荐用python-tsp库的精确解接口，配合numpy预计算距离矩阵效率很高，代码示例：

  import numpy as np
  from python_tsp.exact import solve_tsp_dynamic_programming
  
  # 假设你的one-hot数组存储在变量one_hot_arr中，形状为(样本数, 维度数)
  sample_count = one_hot_arr.shape[0]
  # 预计算所有节点对的汉明距离矩阵
  dist_mat = np.zeros((sample_count, sample_count), dtype=np.int32)
  for idx in range(sample_count):
      dist_mat[idx] = np.sum(one_hot_arr != one_hot_arr[idx], axis=1)
  # 固定起点为0号节点（第一个全0向量），返回最优路径顺序和总步数
  path, total_step = solve_tsp_dynamic_programming(dist_mat)
  

• 向量总数量在20~200区间（接受近似最优解）
  动态规划的时间复杂度是O(n²2ⁿ)，数量大了跑不动，换启发式算法就行，还是用同一个库的模拟退火/遗传算法接口，速度快很多，绝大多数场景得到的结果和最优解差距很小：

  from python_tsp.heuristics import solve_tsp_simulated_annealing
  path, total_step = solve_tsp_simulated_annealing(dist_mat)
  

• 特殊场景优化：所有非全0向量都是单1的情况
  这种场景不用跑TSP，直接按1所在的维度给向量分组即可：同组的向量相邻走步数为0，不同组之间跳转步数为2，加上起点到第一个组的1步，总步数刚好等于不同维度的数量，也就是你说的非零向量去重后的总数，实现复杂度只有O(n)，性能远高于通用解法。

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