寻径算法:如何有效处理权值变化

所以,我有一个简单的寻路算法,它预先计算到几个目标端点的最短路径,每个端点都有不同的权重。这在某种程度上相当于在一个端点和每个端点之间都有一个节点,尽管其中的边具有不同的权重。它使用的算法是一个简单的扩展算法,在1d中,它看起来是这样的(表示墙,-表示空间):

• 5 - - - 3 | - - - 2 - - - - 2
• 5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes
• 5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes
• 5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes
• 5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes
• Done. Any remaining rooms are unreachable.

所以,假设我有一个预先计算好的寻路解决方案,像这样,其中只有5个是目标:

- - - - | 5 4 3 2 1 -

如果我把墙改成房间。重新计算很简单。只需重新处理所有距离节点(但忽略已经存在的节点)。然而,我无法找到一种有效的方法来处理如果4变成一堵墙该怎么办。很明显,结果是:

- - - - | 5 | - - - -

但是,在二维解决方案中,我不知道如何有效地处理4。很容易就可以存储4依赖于5,因此需要重新定义,但是如何安全地确定其新的依赖性和值?我宁愿避免重新计算整个数组。

一个比什么都没有要好的解决方案是(大致)只重新计算距5曼哈顿距离的数组元素,并维护源信息。 这基本上意味着将算法重新应用到选定区域,但我能做得更好吗?