在 X 步内找到从 A 点到 B 点的路径。 （A* 左右）
我目前正在寻找一种可视化数据的方法，算法的一部分需要与 A* 路径查找 99% 相同的东西，但我无法完全理解它。我知道这将是一个相当简单的修改。 （特定成本而不是最低成本）
基本上我需要以 X 步绘制一条从 A 点到 B 点的路径（2D 网格，无对角线）。
例如，如果起点和终点彼此相邻，并且我需要路径为 3 步，那么它将有一个小循环。 （移动：上、右、下）。
该算法是否有一个已知的名称，或者该算法的使用是否非常罕见？
我目前正在研究这个 AS3 Librbay 进行修改，因为它显然非常快，而且对我来说看起来干净简单： http://www.dauntless.be/astar/
非常感谢任何建议/帮助...
约翰
I am currently looking at a way of visualising data and a part of the algorithm needs something 99% the same as A* Path Finding but I cannot wrap my head round it fully. I know it will be a fairly simple modification. (specific cost instead of least cost)
Basically I need to plot a path (2D Grid, no Diagonals) from point A to point B in X number of steps.
E.g. If the start and end points were right next to each other and I needed the path to be 3 steps it would have a tiny loop. (moves: up, right, down).
Is there a known name for this algorithm or is the use of this so rare it's uncommon?
I am currently looking at this AS3 Librbay for modification as it is apparently very fast and seems clean and simple to me:
http://www.dauntless.be/astar/
Any advise / assistance greatly appreciated...
John
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我喜欢这个问题——很有趣。
我不知道如何编写这个代码，但这些只是我脑海中的想法。
基本上，您在这里处理曼哈顿距离，因为您没有使用对角线。因此，您需要知道最短的可能路径并从那里导出。如果您的具体成本小于曼哈顿距离，则该路径是不可能的。如果相等，则理想路径是您可能的最短路径。
一旦超出这个范围，事情就会变得有点棘手，因为你的问题有多种解决方案。您也许可以暴力破解答案，但我不知道是否有一种非天真的方法可以做到这一点。 （但请注意，这些只是我的想法，所以......）
还要注意，对于某些情况，不会有解决方案，因为您使用的是曼哈顿距离！例如，如果您有一个 6x6 的网格，起点位于一个角，终点位于对角，则您可以 10 步到达终点，但不能是 11 步（因为您必须自己加倍）。我确信这是有一条规则的，但我必须推导出它。 （再次，超出我的想象。）（编辑：我意识到这一点 - 这本身并不是一个真正的规则，但你的具体成本不能落在最短路径距离和第二个路径距离之间最短路径距离。我认为，曼哈顿网格中的第二短路径应该是 n+2。）
所以基本上......我认为可以写这样的东西，但我不认为那样您可以轻松计算它，而无需检查很多的可能性。您可以通过规则优化特定情况，但一旦您这样做了，我认为您就会陷入困境。
不过，试一试吧。听起来很有趣！
第二次编辑：我刚刚意识到......你的路径成本总是会增加两倍（同样，由于曼哈顿距离）。这意味着只要知道最短距离，就可以进一步优化；您的具体成本必须是 2 的倍数加上您的最短距离。用算法术语来说，你的具体成本 = 2n + 最短距离。
不过，在这一点之后，你将不得不暴力破解它。
希望这会有所帮助。
第三次编辑（希望是最后一次）：我在这里可能有点迂腐（而且我可能正在弄清楚其他人在我之前已经弄清楚的事情）但事情就是这样。如果您知道具体成本，并且知道最短路径距离，则实际上可以将两者之间的差值除以二来计算出路径中需要多少个循环。循环可以“堆叠”（我的意思是，您可以启动一个循环，并继续一段距离；这是“双倍返回”），因此您可以通过仅检查路径来进一步优化具有特定数量的循环。然而，此时，您几乎已经找到了到达最终节点的可能路径（假设障碍物没有阻挡您找到的所有可能路径）。因此，只有在避免任何障碍时才需要暴力破解。我希望这是有道理的。
I like this question - it's interesting.
I'm not sure how I'd code this, but these are just the thoughts off the top of my head.
Basically, you're dealing with Manhattan distance here, since you aren't using diagonals. As such, you need to know the shortest possible path and derive from there. If your specific cost is less than your Manhattan distance, the path isn't possible. If it's equal, the ideal path is your shortest possible path.
Once you go beyond that, things get a bit tricky, because you have multiple solutions to your problem. You might be able to brute-force an answer, but I don't know if there's a non-naive way to do it. (Note, though, that these are just the thoughts from the top of my head, so...)
Also note that for some situations, there won't be a solution, because you're using Manhattan distance! For instance, if you have a 6x6 grid with a start point in one corner and the end point in the opposite corner, you can end on the end point in 10 steps, but not 11 (because you have to double back on yourself). There's a rule to this, I'm sure, but I'd have to derive it. (Again, off the top of my head.) (EDIT: I realized this - it's not really a rule per se, but your specific cost cannot fall between the shortest path distance and the second shortest path distance. The second shortest path, in a Manhattan grid, should be n+2, I believe.)
So basically...I think it's possible to write something like this, but I don't think that you can easily calculate it without checking a lot of possibilities. You can optimize out specific cases via rules, but once you've done that, I think you're stuck.
Give it a shot, though. It sounds pretty interesting!
SECOND EDIT: I just realized....your path costs will always increase by two (again, due to Manhattan distance). This means that you can optimize a little more as long as you know your shortest distance; your specific cost must be a multiple of 2, plus your shortest distance. In algorithmic terms, you'd have specific cost = 2n + shortest distance.
After this point, though, you're gonna have to brute force it.
Hope this helps.
THIRD EDIT (and hopefully the final one): I'm probably being a bit pedantic here (and I'm probably figuring out what others have figured out wayyy before me) but here's the deal. If you know your specific cost, and you know your shortest path distance, you can actually take the difference between both and divide by two to figure out how many loops you need in your path. Loops can "stack" (and by this I mean, you can start a loop, and continue it for a distance; this is "doubling back") and so you can optimize even further by only checking paths that have a specific number of loops. However, by this time, you've pretty much found a possible path to your end node (assuming that obstacles don't block all of the possible paths you've found). As such, brute forcing would only be necessary to avoid any obstacles. I hope that made sense.
A* 在设计上无法做到这一点。我会使用 Dijkstra 算法并通过所有可能的路径（从最短的路径开始）进行暴力破解，直到找到符合您标准的路径。我真的想不出更简单的方法，因为可以有任意数量的路径满足该条件（包括 0）。
A* is by design not able to do this. I would use Dijkstra's algorithm and brute force through all possible paths (starting at the shortest) until you find one that fits your criteria. I can't really think of an easier way, since there can be any number of paths that fill that criteria (including 0).
首先，您需要明白这不是一个微不足道的问题，因此您不会在这里找到完美的答案，但您会发现一些好主意。
该问题固有的第一件事是，由于您无法穿过对角线，因此某些成本值将无法实现。我假设网格有无法穿越的障碍物，如果不是这种情况，A* 不是一个好的起点。
您的问题需要更多澄清，但我将提供我发现的两种可能性的答案：
没有重复出现点的路径：
修改 A* 算法以继续运行，直到成本直接等于或高于您期望的路径成本被发现。只需使用它作为路径，因为没有其他方法可以实现另一条路径。
具有重复点的路径
找到具有基本 A* 的最短路径，然后，如果它小于所需成本，则通过前后移动来增加成本（通过前后移动，成本会增加 +2） ）按照您的方式或将一个简单的步骤转换为循环（每个循环的成本增加+2）。
First you need to understand that this is not a trivial question and therefore you're not gonna find the perfect answer in here, but you will find some good ideas.
First thing inherent to the problem is that as you cannot move through diagonals, some cost values will be impossible to achieve. I'm assuming that the grid has obstacle blocks that cannot be traversed through, if that's not the case, A* is not a good start point.
Your question needs more clarification, but I'll provide answers to both possibilities I have found:
Path without recurring spots:
Modify the A* algorithm to keep running until the path with cost directly equal or above your desired cost is found. Just use that as the path, as there's no other way to achieve another path.
Path with recurring spots
Find the shortest path with basic A*, then if it's less than the desired cost, increase the cost by either moving back and forth (you add +2 to the cost by going back forth) to your way or by transforming a simple step into a loop (you add +2 to the cost with each loop).