首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >将A*改为dijkstra

将A*改为dijkstra
EN

Stack Overflow用户
提问于 2017-12-08 14:28:14
回答 0查看 231关注 0票数 1
代码语言:javascript
复制
function A*(start, goal)

closedSet := {}

openSet := {start}

cameFrom := an empty map

gScore := map with default value of Infinity

gScore[start] := 0

fScore := map with default value of Infinity

fScore[start] := heuristic_cost_estimate(start, goal)

while openSet is not empty
    current := the node in openSet having the lowest fScore[] value
    if current = goal
        return reconstruct_path(cameFrom, current)

    openSet.Remove(current)
    closedSet.Add(current)

    for each neighbor of current
        if neighbor in closedSet
            continue    

        if neighbor not in openSet  
            openSet.Add(neighbor)

        tentative_gScore := gScore[current] + dist_between(current, neighbor)
        if tentative_gScore >= gScore[neighbor]
            continue        

        cameFrom[neighbor] := current
        gScore[neighbor] := tentative_gScore
        fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal) 

return failure

function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
    current := cameFrom[current]
    total_path.append(current)
return total_path

如果我取这个A* alorgithim,而不是取openset中最低的fScore,取最低的gscore,甚至不考虑fScore,这会有效地使这个dijksta's吗?

EN

回答

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/47708889

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档