寻路（不常见） [英] Pathfinding (not the usual)

问题描述

我已经看到很多方法可以找到从A点到B点的正确路径。（Astar，dijkstra等）



现在我要解决的是其他问题，我不知道是否有人曾经做过类似的事情......



我会尝试解释。



假设我有点A，B和C. br />
在这些点之间有一个给定的速度限制，让我们说AB 20km / h，AC，10km / h，BC 20km / h，距离是：AB 5km，AC 10km，不列颠哥伦比亚省5公里。



现在我必须找到从A到C的最快路径。现在看起来直接从A到C更容易，但它是绝对不是最快的。



我可以创建一个递归调用来检查每个可能的路径，但是当我有数千个点时它会变得有点慢。

解决方案

这称为加权图（每个边都有成本）。您的情况下的成本是从一个节点到下一个节点的总时间（可以使用您指定的输入，速度和距离计算）。



您已经提到了一种可能的解决方案： Dijkstra'算法，适用于加权图。


现在，如果AB与BA不同，那就更有趣了（但是，你所描述的道路似乎是两个方向上相同的速度）。

Hi,

I have already seen a lot of methods to find the right path from point A to B. (Astar, dijkstra, etc.)

Now what I am trying to solve is something else, and i don''t know if anyone have ever done something like this before...

I''ll try to explain.

Let''s say I have point A, B, and C.
Between these points there''s a given speed limit, let''s say A-B 20km/h, A-C, 10km/h, B-C 20km/h, and the distances are: A-B 5km, A-C 10km, B-C 5km.

Now I have to find the "fastest" path from A to C. Now it would seem easier to go form A to C directly, but it is definitely not the fastest.

I could create a recursive call to check every possible path, but when I have thousands of points it would become kinda slow.

解决方案

That is called a weighted graph (where each edge has a "cost"). The "cost" in your case would be the total time to travel from one node to the next (which can be calculated with the inputs you specified, speed and distance).

You mentioned one possible solution already: Dijkstra''s algorithm, which works for weighted graphs.

Now, if A-B is different than B-A, that''d be more interesting (it appears, however, that the "roads" you are describing are the same speed in both directions).

这篇关于寻路（不常见）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！