优化网格路径规划邻接矩阵构建效率的技术咨询

我正在开展一个项目，需可视化给定预算在不同价格区地图上的可达范围。例如包含水域、乡村、城市3种价格区的场景，每个区域每米通行成本不同。

核心问题 #

当前方案时间复杂度极差，提升网格分辨率（减小单元格米级尺寸）时耗时增长极快，问题大概率出在迭代创建scipy.sparse.lil_array构建邻接图的步骤上。

现有流程与耗时瓶颈 #

当前实现分为6个核心步骤，各步骤耗时如下：

• 创建shapely.geometry.Point类型的Python列表（代表2D网格采样点），转成DataFrame后与GeoPandas区域做交集匹配：13.6s
• 将DataFrame转为GeoDataFrame，用gpd.sjoin匹配不同价格区，得到对应3个区域的GeoDataFrame：0.7s
• 将点的价格映射回2D数组，通过坐标转索引填充Python二维列表：14.9s
• 将成本数组转为邻接矩阵：迭代向scipy.sparse.lil_array插入边，再转为scipy.sparse.csr_array：136.7s——核心瓶颈，节点采用5×5邻域偏移规则构建边
• 调用scipy.sparse.csgraph.dijkstra计算路径：0.4s
• 迭代遍历数组添加节点固定成本：0.2s

疑问 #

当前方案（因节点边数有限导致边缘块状误差，该误差可忽略）是否合理？若合理，如何高效构建邻接图以降低步骤4耗时？

已尝试方案 #

• 从原点绘制射线计算预算可达长度：无法通过低价区寻优路径，运行效率差
• 使用列表式邻接图：构建时间降低，但自实现Dijkstra导致总耗时翻倍
• 使用DOK格式构建邻接矩阵：耗时增至674s，效果更差

解决方案 #

方案合理性判断 #

你的方案完全合理。基于网格节点的图模型计算预算可达范围，在边缘块状误差可忽略的前提下，完全能满足可视化需求——毕竟可视化只需要直观体现价格区对可达范围的影响，无需绝对精度。

邻接图构建优化方案 #

针对步骤4的瓶颈，放弃迭代插入边的低效方式，改用批量生成+向量化操作替代循环，可大幅压缩耗时：

1. 批量生成邻接边的索引与权重
   先明确5×5邻域的偏移规则（比如排除自身，仅保留网格范围内的有效相邻节点），再用NumPy批量处理：

   • 假设网格为M×N，先建立每个节点的线性索引（对应邻接矩阵的行/列）与二维坐标(i,j)的映射关系
   • 生成5×5邻域的偏移量数组：offsets = np.array([[di,dj] for di in range(-2,3) for dj in range(-2,3) if (di,dj)!=(0,0)])
   • 对所有节点的二维坐标加上偏移量，筛选出落在网格范围内的坐标，再转换为线性索引，得到所有合法的(src, dst)边对
   • 根据src和dst所在网格的成本，批量计算每条边的通行成本（比如两点间距离×区域平均成本，具体规则可根据需求调整）

2. 直接构建CSR矩阵
   拿到批量的src、dst、weights数组后，直接调用scipy.sparse.csr_matrix((weights, (src, dst)), shape=(total_nodes, total_nodes))构建邻接矩阵，完全跳过LIL/DOK的迭代插入流程。这种方式利用CSR矩阵的批量构建特性，效率比循环插入高数个数量级。

3. 额外优化策略

   • 若存在完全不可通行的区域（如水域成本极高），可提前过滤这些节点，减少邻接图的总节点数
   • 5×5邻域中，若相邻节点属于同一价格区，可批量计算成本，避免逐个处理的冗余操作

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