如何使用A *算法找到最好的三条路线 [英] how to find the best three routes using A* algorithm

问题描述

在A *通常是你得到的结果是只有一条路径。是否有可能，虽然对于给定的起点和终点，根据A *有3个推荐路径？所以第二个返回的第二个最佳路径，第三个是第三最佳路径。

In A* usually the result that you get is only one path. Is it possible though for a given origin and destination to have 3 recommended path according to A*? So the second returned is the second best path, and the third is the third best path..

我在想，也许修改启发式某种程度上反映了这第二个和第三个最佳路径..你们有什么感想？

I was thinking of maybe modifying the heuristic somehow to reflect this second and third best path.. What do you guys think?

更新： 我的实现是在PHP和我使用的是闭集。因此，如果有一种方法可以做到这一点，让我知道。

UPDATE: My implementation is in PHP and I am using a closed set. So if there's a way to do this, let me know.

推荐答案

这可以很容易，如果你的语言具有回溯/发电机/迭代器/协同程序支持完成的。

This can be done quite easily if your language has support for backtracking/generators/iterators/coroutines.

# Python code
def astar(start):
    q = [start]    # priority queue
    while len(q) > 0:
        node = heappop(q)
        if isGoal(node):
            yield node
        for x in successors(node):
            heappush(q, x)

在收益率关键字类似于返回，除了功能，可过了<$重新输入C $ C>收益率来获得一个解决方案。为了获得最佳三：

The yield keyword is similar to return, except that the function may be re-entered after a yield to get the next solution. To get the best three:

solutions = []
i = 0
for sol in astar(start):
    solutions.append(sol)
    if i == 3:
        break
    i += 1

然而，这不会，如果你使用一个工作的闭集的（即的拉塞尔和放大器;弱势族群的图搜索的算法），自那时以来，部分非最佳的解决方案可能是切断寻找最优的时候。

However, this will not work if you use a closed set (i.e., Russell & Norvig's graph search algorithm), since then part of the non-optimal solutions may be "cut off" when searching for the optimal one.

这篇关于如何使用A *算法找到最好的三条路线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！