在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)
在收益率
关键字类似于返回
,除了功能,可过了收益率来获得一个解决方案。为了获得最佳三:
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.