如何为并行A*算法均匀分区网格图？解决子图节点孤立问题

我目前正尝试并行化A*算法，需根据进程数量拆分类网格结构的图，以下是我的实现代码：

if __name__ == "__main__":
comm = MPI.COMM_WORLD
rank = comm.Get_rank()
size = comm.Get_size()
file_path = "grid_graph.txt"
graph = None
assigned_nodes = []

if rank == 0:
    graph = load_graph(file_path)


graph = comm.bcast(graph, root=0)
total_nodes = len(graph)
num_processes = comm.Get_size()


base_num_nodes = total_nodes // num_processes
remaining_nodes = total_nodes % num_processes


start_index = rank * base_num_nodes
end_index = (rank + 1) * base_num_nodes

if rank < remaining_nodes:
    start_index += rank
    end_index += rank + 1
else:
    start_index += remaining_nodes
    end_index += remaining_nodes

assigned_nodes = list(graph.keys())[start_index:end_index]

all_assigned_nodes = comm.gather(assigned_nodes, root=0)

if rank == 0:
    for process_rank, nodes in enumerate(all_assigned_nodes):
        print("Process", process_rank, "assigned nodes:", nodes)
print("Process", rank, "assigned nodes:", assigned_nodes)
start = Node((0, 0))
goal = Node((2, 2))

try:
    start_time = time.time()
    path = astar(start, goal, graph)
    print("Process", rank, "Path found:", path)
    print("Process", rank, "Total cost:", total_cost(path, graph))
    print("Process", rank, "Execution time:", time.time() - start_time, "seconds")
except ValueError:
    print("Process", rank, "No path found")

当前问题是子图中的部分节点没有邻居，请问如何进行图分区才能保证所有子图连通或至少存在可搜索路径？

当前按节点索引均分的分区方式完全忽略了网格图的拓扑结构，导致子图被拆得支离破碎，出现孤立节点。针对网格图的并行A*，需要基于拓扑结构做分区，以下是几种可行方案：

1. 基于网格空间的块划分（最适合网格图） #

直接按网格的二维空间切分，而非节点列表索引：

• 假设网格为M行×N列，按进程数将网格划分为P个矩形块（比如2进程可横向/纵向对半切割）
• 每个进程负责一个连续矩形区域，区域内节点天然连通，邻居节点要么在本区域，要么在相邻进程的区域
• 实现时，通过节点的坐标(x,y)判断所属矩形块，再分配给对应进程

示例逻辑：

# 假设graph的key是Node对象，包含x、y属性
rows = max(node.x for node in graph.keys()) + 1
cols = max(node.y for node in graph.keys()) + 1

# 按纵向切分（按列分配）
cols_per_process = cols // num_processes
remaining_cols = cols % num_processes

start_col = rank * cols_per_process
end_col = (rank + 1) * cols_per_process
if rank < remaining_cols:
    start_col += rank
    end_col += rank + 1
else:
    start_col += remaining_cols
    end_col += remaining_cols

# 筛选当前进程负责的节点
assigned_nodes = [node for node in graph.keys() if start_col <= node.y < end_col]

2. 保留边界节点的重叠分区 #

为避免跨进程邻居查询问题，让相邻进程的分区保留重叠边界节点：

• 每个进程在自身负责的块基础上，额外包含周围一圈的边界节点
• 确保每个节点的邻居要么在本进程分区内，要么在重叠区域，不会出现孤立无邻居的情况
• 注意处理重复节点的计算冲突，可通过锁或主进程协调解决

3. 基于图连通性的分区算法（通用图场景） #

若网格存在障碍物导致非规则连通区域，可使用专门的图分区算法：

• 比如METIS，它能在保证分区大小均衡的同时，最小化跨分区的边数，确保每个子图连通
• 实现时，先将网格图转换为METIS支持的格式，调用工具得到分区结果后分配给各进程

额外优化：并行A*的协作逻辑 #

分区后需调整A*执行逻辑：

• 每个进程仅处理自身分区内节点的扩展操作
• 当扩展到边界节点时，将节点信息发送给对应邻居进程
• 主进程负责汇总各进程的开放列表，或采用分布式开放列表协调搜索

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