如何在蚁群算法求解TSP时避免蚂蚁访问已遍历顶点？

你的代码存在几处逻辑错误，导致无法有效防止蚂蚁重复访问节点，以下是具体修正方案：

核心问题分析 #

1. 循环条件错误：while(k != 3)仅循环2次，完全无法覆盖所有节点，应根据顶点数量设置循环次数，确保遍历全部节点。
2. 已访问节点判断逻辑错误：你用j != ant_path[k0][i]就累加概率，这会导致只要有一个位置不等于j就重复累加，正确逻辑是j不在已访问列表中才累加。
3. 节点遍历范围错误：选择下一个节点时for j in range(vertice-1)会漏掉最后一个顶点，应遍历所有顶点并跳过已访问的。
4. 变量命名冲突：sum是Python内置函数，用作变量名可能引发意外问题，建议替换为total_prob。

修正后的代码片段 #

current_position = draw_first_position
k = 1
k0 = 0
# 初始化路径，起点放入第0位
ant_path[k0][0] = current_position
# 用列表专门记录当前蚂蚁已访问的节点
visited = [current_position]

# 循环vertice-1次，覆盖所有剩余节点
while k < vertice:
    # 计算未访问节点的概率总和
    total_prob = 0
    for j in range(vertice):
        if j not in visited:
            total_prob += probability[current_position][j]
    
    # 生成随机概率值
    draw = random.uniform(0, total_prob)
    accumulated = 0
    next_position = -1
    
    # 遍历所有节点，跳过已访问的，选择下一个节点
    for j in range(vertice):
        if j in visited:
            continue
        prob = probability[current_position][j] / total_prob
        accumulated += prob
        if draw <= accumulated:
            next_position = j
            break
    
    # 更新路径、当前位置和已访问列表
    ant_path[k0][k] = next_position
    current_position = next_position
    visited.append(next_position)
    k += 1

# 最后回到起点，完成TSP回路
ant_path[k0][vertice] = draw_first_position
print(ant_path)

关键修正点说明 #

• 已访问节点管理：用visited列表单独记录当前蚂蚁走过的节点，判断逻辑更清晰，避免遍历整个路径数组的错误。
• 循环逻辑：while k < vertice确保走够vertice步（起点+vertice-1个节点），最后添加起点形成完整回路。
• 概率计算：仅累加未访问节点的概率，保证选择范围仅限可用节点，从根源避免重复访问。
• 节点选择：遍历所有节点并跳过已访问项，不会漏掉任何可用顶点。

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