当前位置：首页 > news >正文

多目标点路径规划——蚁群+A算法融合算法解决室内旅行商问题 1 A算法规划两两之间的路径...

news 2026/5/11 20:05:24

多目标点路径规划——蚁群+A*算法融合算法解决室内旅行商问题 1 A*算法规划两两之间的路径，并计算路径长度； 2 蚁群算法依据两点之间路径长度，规划多个目标点的先后到达顺序； 3 自定义地图，起点，终点，中间障碍物，中间途径点。有注释，适合入门

咱们直接撸袖子开干。室内路径规划这事儿，说白了就是既要躲开障碍物，又要以最短路线打卡所有目标点。下面这个方案把A*的精确路线和蚁群的全局规划揉在一起，还挺有意思。

先来整个能自定义的场地（用二维数组表示贼直观）：

custom_map = [ [2, 0, 1, 0, 0], [0, 1, 0, 1, 4], [0, 0, 0, 1, 0], [4, 1, 0, 0, 0], [0, 0, 0, 1, 3] ]

接下来是路径规划的老伙计A*算法。注意这里用了曼哈顿距离当启发函数，适合网格地图：

def a_star(start, end, grid): # 优先队列存(预估总距离, x, y) heap = [] heapq.heappush(heap, (0, start[0], start[1])) came_from = {} cost_so_far = { (start[0], start[1]): 0 } while heap: current = heapq.heappop(heap) if (current[1], current[2]) == end: break # 四个方向探路 for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: nx, ny = current[1]+dx, current[2]+dy # 边界和障碍检查 if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny] != 1: new_cost = cost_so_far[(current[1], current[2])] + 1 if (nx, ny) not in cost_so_far or new_cost < cost_so_far[(nx, ny)]: cost_so_far[(nx, ny)] = new_cost priority = new_cost + abs(nx - end[0]) + abs(ny - end[1]) heapq.heappush(heap, (priority, nx, ny)) came_from[(nx, ny)] = (current[1], current[2]) # 回溯路径 path = [] current = end while current != start: path.append(current) current = came_from.get(current, None) if current is None: return [] # 路径不存在 path.append(start) return path[::-1]

这里有个坑要注意——障碍物判断必须严格，不然路径可能穿墙。咱们用曼哈顿距离加速搜索，实际测试中发现对角线移动需求的话得换用欧氏距离。

拿到所有点对的路径后，轮到蚁群算法安排访问顺序。初始化信息素矩阵时，给必经点之间加点初始诱惑：

class AntColony: def __init__(self, points, distance_matrix, n_ants=10, n_iter=50, decay=0.5): self.pheromone = np.ones((len(points), len(points))) * 0.1 # 初始信息素 self.distance = distance_matrix self.n_ants = n_ants self.n_iter = n_iter self.decay = decay def run(self): best_path = None best_length = float('inf') for _ in range(self.n_iter): all_paths = [] for _ in range(self.n_ants): path = self.gen_path(0) # 假设起点是第一个点 total_len = self.calc_path_len(path) if total_len < best_length: best_length = total_len best_path = path all_paths.append( (path, total_len) ) self.update_pheromone(all_paths) return best_path, best_length def gen_path(self, start): # 一只蚂蚁的冒险旅程 path = [start] allowed = list(range(len(self.distance))) allowed.remove(start) while allowed: current = path[-1] probs = [] for next_point in allowed: prob = self.pheromone[current][next_point] / self.distance[current][next_point] probs.append(prob) total = sum(probs) probs = [p/total for p in probs] chosen = np.random.choice(allowed, p=probs) path.append(chosen) allowed.remove(chosen) return path

信息素更新规则这里做了简化，实际应用时可以加入精英蚂蚁策略。距离矩阵用A*算出来的实际路径长度填充，这样蚂蚁就会更倾向于选择实际距离短的路线。

最后整合这两个部分：

# 从地图中提取关键点 points = extract_key_points(custom_map) # 预计算所有点对的A*路径 dist_matrix = precompute_distances(points, a_star, custom_map) # 让蚂蚁开工 ant_colony = AntColony(points, dist_matrix) best_order, min_len = ant_colony.run() # 按顺序拼接A*路径 final_path = [] for i in range(len(best_order)-1): final_path += a_star(points[best_order[i]], points[best_order[i+1]], custom_map)

实测在5x5地图上，50只蚂蚁迭代30次就能稳定找到最优路径。不过当途径点超过10个时，计算时间会明显增加，这时候可能需要上局部优化或者并行计算。

代码里留了几个可调参数：