python - "map"的算法

Question

好吧，我正在尝试解决以下问题:假设我有一张“城市 map ”。我有一个来源和一个目的地。有些街道被封锁，有些街道是免费的。想要创建一个算法来告诉我要走哪条路才能到达目的地，穿过免费的街道。

例子:

S - Source 
D - Destination 
F - Free Streets 
B - Busy Streets 

B B B B B 
S F F F B 
F B B F F 
F F B B D 
B F F F F

在这种情况下，会有两条可能的路线:

B B B B B 
S - - - B 
* B B - - 
* * B B D 
B * * * *

正在考虑执行以下操作:

创建一个函数来检查路线是否空闲。例如，如果 east 是空闲的，该函数将创建一个具有新坐标的线程，x 和 y + 1 等等，将为每个方向创建一个线程每个 “点”。我不知道这是否是最好的方法，但想知道是否有人可以提供其他方法的想法!

正在考虑用 python 做，因为我更熟悉这门语言。我只是把它当作一种爱好。

Answer 1

这些类型的问题属于 routing算法。引用Dijikstra的最短路径查找算法。

因为你的输入是一个数组( Map )，你可以做 Depth first search在其上确定构成路径的连接点。

如果您正在寻找有效的方法来实现这一点，您可能想看看 networkx图书馆。引用here用于在 networkx 中预先实现的遍历方法。