如何使用A*算法求解从起点出发途经所有给定点的最短路径

你当前实现的核心错误是状态定义不完整：单起点单终点的A*搜索只需要用「当前所在点」作为唯一状态标识，但你要解决的是「途经所有指定点的最短路径」问题（本质是带重复访问许可的欧几里得旅行商问题），仅记录当前所在点无法区分「已访问过不同子集的V中点」的情况，两种状态只要所在点不同、或者已访问的V中点集合不同，就是完全独立的状态，不能共用g值。
举个例子：你当前在v₁、已经访问过{v₂,v₃}，和你当前在v₁、只访问过{v₂}，是两个完全不同的状态，后者剩余待访问点更多，对应的g、h计算逻辑完全不同，你之前把所有落在v₁的状态都当成同一个节点更新，自然会得到错误结果。

1. 重新定义状态结构 #

每个搜索节点需要包含两个核心字段：

• 当前所在的空间点 cur_pos
• 已访问V中点集合的标识 visited_mask：如果V的大小n≤32可以用32位整数作为位掩码，n≤64用64位整数，n更大可以用布尔数组或哈希结构表示
  对应三个值的定义调整为：
• u.g：从起点S到当前状态（cur_pos，visited_mask）的实际最短路径长度
• u.h：从cur_pos出发，访问完所有剩余未访问V中点的最小距离下界
• u.f = u.g + u.h：作为优先级队列的排序依据

2. 调整节点更新判定逻辑 #

你需要额外维护一个距离表 dist[visited_mask][cur_pos]，记录每个状态的已知最小g值，更新逻辑改为：

// 当前处理状态为(cur_pos, cur_mask)，移动到下一个点next_pos，next_mask为cur_mask加上next_pos的访问标记
new_g = cur_g + euclidean_distance(cur_pos, next_pos)
if (new_g < dist[next_mask][next_pos]) {
    dist[next_mask][next_pos] = new_g
    new_h = 计算(next_pos, next_mask)对应的启发式值
    new_f = new_g + new_h
    将(new_f, new_g, next_pos, next_mask)加入优先级队列
}

3. 启发式函数优化建议 #

你当前用的曼哈顿距离如果是在欧几里得平面场景下，会不符合启发式可采纳性要求（即估计值大于实际剩余路径长度），会导致A*无法保证找到最优解，欧几里得平面下建议使用以下任意一种可采纳的h：

• 剩余未访问点到当前点的欧几里得距离的最大值：计算成本最低，适合小规模问题
• 剩余未访问点的最小生成树总权重 + 当前点到最小生成树的最短距离：下界更紧，能大幅减少搜索次数，适合中等规模问题

4. 终止条件 #

当你从优先级队列取出的状态满足 visited_mask 覆盖V中所有点时，该状态对应的g值就是你要求的最短路径长度。

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