A*(A-star) 算法给出错误的路径和崩溃 [英] A*(A-star) algorithm gives wrong path and crashes

查看:28
本文介绍了A*(A-star) 算法给出错误的路径和崩溃的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我正在 react.js 中实现 A*(A-star) 算法,但只要 startNode(green) 或 destinationNode(blue) 有多个邻居,或者图中存在循环,我的程序就会崩溃.从/向 openList 添加和删除邻居或在 getPath() 函数中更新 parentId 时,会出现问题.我什至看不到控制台,因为网站宕机了.每个节点有:id、name、x、y、connectedToIdsList:[]、gcost:Infinity、fcost:0、heuristic:0、parentId:null.我正在将路径发送到另一个组件TodoList";打印出路径.我的程序不应该返回路径,而是在我向列表中添加节点和边时不断更新路径.请帮忙,我已经被困了几个小时了:/

我的代码:

导出默认类 TurnByTurnComponent extends React.PureComponent {构造函数(道具){超级(道具);this.state = { 最短路径:[] }}使成为() {常量{目的地位置 ID,地点,起始位置标识} = this.props;让路径 = []if (destinationLocationId != null && originLocationId != null) {if (originLocationId == destinationLocationId) {//检查startNode节点是否为结束节点返回 originLocationId;}var openList = [];让 startNode = getNodeById(originLocationId);让 destinationNode = getNodeById(destinationLocationId)if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {//检查起始节点和目标节点是否先连接startNode.gcost = 0startNode.heuristic = manhattanDistance(startNode, destinationNode)startNode.fcost = startNode.gcost + startNode.heuristic;//执行A*openList.push(startNode);//从startNode开始而 (openList.length > 0) {console.log("inside while")var currentNode = getNodeOfMinFscore(openList);//获取openList中所有节点的f代价最小的节点如果(currentIsEqualDistation(currentNode)){路径 = getPath(currentNode);}deleteCurrentFromOpenList(currentNode, openList);for(让当前节点的邻居ID.connectedToIds){var neighborNode = getNodeById(neighborId);currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighborNode);如果(currentNode.gcost < neighborNode.gcost){neighborNode.parentId = currentNode.id;//跟踪路径//在neighbor.g 中节省的总成本neighborNode.gcost = currentNode.gcost;neighborNode.heuristic = manhattanDistance(邻居节点,目的地节点);邻居节点.fcost = 邻居节点.gcost + 邻居节点.启发式;//计算邻居节点的f成本addNeighbourNodeToOpenList(邻居节点,openList);}}}path = path.reverse().join("->");}}函数 addNeighbourNodeToOpenList(邻居节点,openList){//将neighborNode加入待发现的open list如果(!openList.includes(邻居节点)){openList.push(邻居节点);}}函数 deleteCurrentFromOpenList(currNode, openList) {const currIndex = openList.indexOf(currNode);openList.splice(currIndex, 1);//从openList中删除currentNode}函数 currentIsEqualDistation(currNode) {//检查我们是否伸出了距离节点返回(currNode.id == destinationLocationId)}函数 getNodeById(nid) {无功节点;for (let i = 0; i 

);}}TurnByTurnComponent.propTypes = {destinationLocationId:PropTypes.number,位置:PropTypes.arrayOf(PropTypes.shape({id: PropTypes.number.isRequired,名称:PropTypes.string.isRequired,x: PropTypes.number.isRequired,y: PropTypes.number.isRequired,connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired})),originLocationId: PropTypes.number};

更新新问题链接新节点之前和之后的图片.当我更新图形并添加一个新节点时,路径消失了.如果我仍然向图中添加新节点和边,有时会返回等等.正如我所说,每个节点都有:id、name、x、y、connectedToIdsList:[]、gcost:Infinity、fcost:0、heuristic:0、parentId:null.我现在的新代码是:

导出默认类 TurnByTurnComponent extends React.PureComponent {构造函数(道具){超级(道具);this.state = { 最短路径:[] }}使成为() {常量{目的地位置 ID,地点,起始位置标识} = this.props;让路径 = []if (destinationLocationId != null && originLocationId != null) {console.log(JSON.stringify(locations))path = [getNodeById(originLocationId).namne];如果(originLocationId != destinationLocationId){var openList = [];让 startNode = getNodeById(originLocationId);让 destinationNode = getNodeById(destinationLocationId)如果 (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {startNode.gcost = 0startNode.heuristic = manhattanDistance(startNode, destinationNode)startNode.fcost = startNode.gcost + startNode.heuristic;openList.push(startNode);//从startNode开始而 (openList.length > 0) {var currentNode = getNodeOfMinFscore(openList);//获取openList中所有节点的f代价最小的节点如果(currentIsEqualDistation(currentNode)){路径 = getPath(currentNode);休息;}deleteCurrentFromOpenList(currentNode, openList);for(让当前节点的邻居ID.connectedToIds){var neighborNode = getNodeById(neighborId);让 gcost = currentNode.gcost + manhattanDistance(currentNode, neighborNode);if (gcost < (neighborNode.gcost ?? Infinity)) {neighborNode.parentId = currentNode.id;//跟踪路径//在neighbor.g 中节省的总成本neighborNode.gcost = gcost;neighborNode.heuristic = manhattanDistance(邻居节点,目的地节点);邻居节点.fcost = 邻居节点.gcost + 邻居节点.启发式;//计算邻居节点的f成本addNeighbourNodeToOpenList(邻居节点,openList);}}}}}}path = path.reverse().join("->");函数 addNeighbourNodeToOpenList(邻居节点,openList){//将neighborNode加入待发现的open list如果(!openList.includes(邻居节点)){openList.push(邻居节点);}}函数 deleteCurrentFromOpenList(currentNode, openList) {const currIndex = openList.indexOf(currentNode);openList.splice(currIndex, 1);//从openList中删除currentNode}函数 currentIsEqualDistation(currentNode) {//检查我们是否伸出了距离节点返回(currentNode.id == destinationLocationId)}函数 getNodeById(id) {无功节点;for (let i = 0; i 

);}}TurnByTurnComponent.propTypes = {destinationLocationId:PropTypes.number,位置:PropTypes.arrayOf(PropTypes.shape({id: PropTypes.number.isRequired,名称:PropTypes.string.isRequired,x: PropTypes.number.isRequired,y: PropTypes.number.isRequired,connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired})),originLocationId: PropTypes.number};

解决方案

您的代码中存在一些问题:

  • return originLocationId; 不应该发生.当源与目标相等时,则设置路径,并确保执行此函数最后的return,因为要返回div 元素.

  • 当在循环中找到目标时,不仅应该构建path,还应该退出循环.所以添加一个 break

  • currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighborNode); 不对:你不想修改currentNode.gcost:它的值不应取决于该邻居的传出边缘.而是将这个总和存储在一个临时变量中(如 gcost)

  • 当该节点还没有 gcost 成员时,与 neighborNode.gcost 的比较将不起作用.我在你的代码中没有看到它有一个确保这个条件成立的默认值,所以你应该在这里使用一个默认值,比如 (neighborNode.gcost ?? Infinity)

  • path = path.reverse().join("->"); 最好总是执行,即使没有解决方案(所以 path 是一个字符串)或者当源和目标是同一个节点时.

这是一个更正后的版本,稍微调整为在这里作为可运行的代码段运行:

function render() {常量{目的地位置 ID,地点,起始位置标识} = this.props;让路径 = [];if (destinationLocationId != null && originLocationId != null) {路径 = [originLocationId];//下一个 if 条件不成立时的值如果(originLocationId != destinationLocationId){var openList = [];让 startNode = getNodeById(originLocationId);让 destinationNode = getNodeById(destinationLocationId)如果 (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {startNode.gcost = 0startNode.heuristic = manhattanDistance(startNode, destinationNode)startNode.fcost = startNode.gcost + startNode.heuristic;openList.push(startNode);而 (openList.length > 0) {var currentNode = getNodeOfMinFscore(openList);如果(currentIsEqualDistation(currentNode)){路径 = getPath(currentNode);休息;//应该在这里结束搜索!}deleteCurrentFromOpenList(currentNode, openList);for(让当前节点的邻居ID.connectedToIds){var neighborNode = getNodeById(neighborId);//不应修改当前节点的 gcost.改用变量:让 gcost = currentNode.gcost + manhattanDistance(currentNode, neighborNode);//当邻居还没有 gcost 时,条件也应该有效:if (gcost < (neighborNode.gcost ?? Infinity)) {neighborNode.parentId = currentNode.id;neighborNode.gcost = gcost;//使用变量neighborNode.heuristic = manhattanDistance(邻居节点,目的地节点);邻居节点.fcost = 邻居节点.gcost + 邻居节点.启发式;addNeighbourNodeToOpenList(邻居节点,openList);}}}}}}//在所有情况下将路径转换为字符串:path = path.reverse().join("->");函数 addNeighbourNodeToOpenList(邻居节点,openList){如果(!openList.includes(邻居节点)){openList.push(邻居节点);}}函数 deleteCurrentFromOpenList(currNode, openList) {const currIndex = openList.indexOf(currNode);openList.splice(currIndex, 1);}函数 currentIsEqualDistation(currNode) {返回(currNode.id == destinationLocationId)}函数 getNodeById(nid) {无功节点;for (let i = 0; i 

I'm implementing A*(A-star) algorithm in react.js but my program crashes whenever startNode(green) or destinationNode(blue) have more than one neighbour or if there is a cycle in the graph. There is something wrong when adding and deleting the neighbours from/to openList or when updating the parentId in the getPath() function. I cant even see the console because the website goes down. Each node has: id, name, x, y, connectedToIdsList:[], gcost:Infinity, fcost:0, heuristic:0, parentId:null. I'm sending the path to another component "TodoList" which prints out the path. My program should not return the path but keeps updating the path as i'm adding nodes and edges to the list. Please help, I've been stuck for hours now:/

My code:

export default class TurnByTurnComponent extends React.PureComponent {
    constructor(props) {
        super(props);
        this.state = { shortestPath: [] }
    }


    render() {
        const {
            destinationLocationId,
            locations,
            originLocationId
        } = this.props;
        let path = []

        if (destinationLocationId != null && originLocationId != null) {

            if (originLocationId == destinationLocationId) { //check if the startNode node is the end node
                return originLocationId;
            }

            var openList = [];
            let startNode = getNodeById(originLocationId);
            let destinationNode = getNodeById(destinationLocationId)
            if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) { //check if start and destination nodes are connected first

                startNode.gcost = 0
                startNode.heuristic = manhattanDistance(startNode, destinationNode)
                startNode.fcost = startNode.gcost + startNode.heuristic;

                //perform A*
                openList.push(startNode); //starting with the startNode 
                while (openList.length > 0) {
                    console.log("inside while")
                    var currentNode = getNodeOfMinFscore(openList); //get the node of the minimum f cost of all nodes in the openList
                    if (currentIsEqualDistanation(currentNode)) {
                        path = getPath(currentNode);
                    }
                        deleteCurrentFromOpenList(currentNode, openList);
                    for (let neighbourId of currentNode.connectedToIds) { 
                        var neighbourNode = getNodeById(neighbourId);
                        currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
                        if (currentNode.gcost < neighbourNode.gcost) {
                            neighbourNode.parentId = currentNode.id; // keep track of the path
                            // total cost saved in neighbour.g
                            neighbourNode.gcost = currentNode.gcost;
                            neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
                            neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic; //calculate f cost of the neighbourNode
                            addNeighbourNodeToOpenList(neighbourNode, openList);
                        }
                    }

                }
                path = path.reverse().join("->");
            }
        }

        function addNeighbourNodeToOpenList(neighbourNode, openList) {
            //add neighbourNode to the open list to be discovered later
            if (!openList.includes(neighbourNode)) {
                openList.push(neighbourNode);
            }
        }


        function deleteCurrentFromOpenList(currNode, openList) {
            const currIndex = openList.indexOf(currNode);
            openList.splice(currIndex, 1); //deleting currentNode from openList
        }

        function currentIsEqualDistanation(currNode) {
            //check if we reached out the distanation node
            return (currNode.id == destinationLocationId)
        }

        function getNodeById(nid) {
            var node;
            for (let i = 0; i < locations.length; i++) {
                if (locations[i].id == nid) {
                    node = locations[i]
                }
            }
            return node
        }

       function getPath(destNode) {
        console.log("inside getpath")
        var parentPath = []
        var parent;
        while (destNode.parentId != null) {
            parentPath.push(destNode.name)
            parent = destNode.parentId;
            destNode = getNodeById(parent);
        }
        //adding startNode to the path
        parentPath.push(getNodeById(originLocationId).name)
        return parentPath;
    }

        function getNodeOfMinFscore(openList) {
            var minFscore = openList[0].fcost; //initValue
            var nodeOfminFscore;
            for (let i = 0; i < openList.length; i++) {
                if (openList[i].fcost <= minFscore) {
                    minFscore = openList[i].fcost //minFvalue
                    nodeOfminFscore = openList[i]
                }
            }

            return nodeOfminFscore
        }

        //manhattan distance is for heuristic and gScore. Here I use Manhattan instead of Euclidean 
        //because in this example we dont have diagnosal path.
        function manhattanDistance(stNode, dstNode) {
            var x = Math.abs(dstNode.x - stNode.x);
            var y = Math.abs(dstNode.y - stNode.y);
            var dist = x + y;
            return dist;
        }


        return (
            <div className="turn-by-turn-component">
                <TodoList
                    
                    list={"Shortest path: ", [path]}
                />
                <TodoList
                   
                    list={[]}
                />
            </div>
        );
    }
}

TurnByTurnComponent.propTypes = {
    destinationLocationId: PropTypes.number,
    locations: PropTypes.arrayOf(PropTypes.shape({
        id: PropTypes.number.isRequired,
        name: PropTypes.string.isRequired,
        x: PropTypes.number.isRequired,
        y: PropTypes.number.isRequired,
        connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
    })),
    originLocationId: PropTypes.number
};

Update new issue Pictures of before and after linking a new node. When I update the graph and add a new node the path disappears. And sometimes come back and so on if I still add new nodes and edges to the graph. As I said, each node has: id, name, x, y, connectedToIdsList:[], gcost:Infinity, fcost:0, heuristic:0, parentId:null. My new code now is:

export default class TurnByTurnComponent extends React.PureComponent {
    constructor(props) {
        super(props);
        this.state = { shortestPath: [] }
    }


    render() {
        const {
            destinationLocationId,
            locations,
            originLocationId
        } = this.props;
        let path = []

        if (destinationLocationId != null && originLocationId != null) {
            console.log(JSON.stringify(locations))
            path = [getNodeById(originLocationId).namne];
            if (originLocationId != destinationLocationId) {
                var openList = [];
                let startNode = getNodeById(originLocationId);
                let destinationNode = getNodeById(destinationLocationId)
                if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {
                    startNode.gcost = 0
                    startNode.heuristic = manhattanDistance(startNode, destinationNode)
                    startNode.fcost = startNode.gcost + startNode.heuristic;

                    openList.push(startNode); //starting with the startNode 
                    while (openList.length > 0) {
                        var currentNode = getNodeOfMinFscore(openList); //get the node of the minimum f cost of all nodes in the openList
                        if (currentIsEqualDistanation(currentNode)) {
                            path = getPath(currentNode);
                            break;
                        }
                        deleteCurrentFromOpenList(currentNode, openList);
                        for (let neighbourId of currentNode.connectedToIds) {
                            var neighbourNode = getNodeById(neighbourId);
                            let gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
                            if (gcost < (neighbourNode.gcost ?? Infinity)) {
                                neighbourNode.parentId = currentNode.id;
                                // keep track of the path
                                // total cost saved in neighbour.g
                                neighbourNode.gcost = gcost;
                                neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
                                neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic; //calculate f cost of the neighbourNode
                                addNeighbourNodeToOpenList(neighbourNode, openList);
                            }
                        }
                    }
                }

            }
        }
        path = path.reverse().join("->");

        function addNeighbourNodeToOpenList(neighbourNode, openList) {
            //add neighbourNode to the open list to be discovered later
            if (!openList.includes(neighbourNode)) {
                openList.push(neighbourNode);
            }
        }


        function deleteCurrentFromOpenList(currentNode, openList) {
            const currIndex = openList.indexOf(currentNode);
            openList.splice(currIndex, 1); //deleting currentNode from openList
        }

        function currentIsEqualDistanation(currentNode) {
            //check if we reached out the distanation node
            return (currentNode.id == destinationLocationId)
        }

        function getNodeById(id) {
            var node;
            for (let i = 0; i < locations.length; i++) {
                if (locations[i].id == id) {
                    node = locations[i]
                }
            }
            return node
        }

        function getPath(destinationNode) {
            console.log("inside getpath")
            var parentPath = []
            var parent;
            while (destinationNode.parentId != null) {
                parentPath.push(destinationNode.name)
                parent = destinationNode.parentId;
                destinationNode = getNodeById(parent);
            }
            //adding startNode to the path
            parentPath.push(getNodeById(originLocationId).name)
            return parentPath;
        }

        function getNodeOfMinFscore(openList) {
            var minFscore = openList[0].fcost; //initValue
            var nodeOfminFscore;
            for (let i = 0; i < openList.length; i++) {
                if (openList[i].fcost <= minFscore) {
                    minFscore = openList[i].fcost //minFvalue
                    nodeOfminFscore = openList[i]
                }
            }

            return nodeOfminFscore
        }

        //manhattan distance is for heuristic and gScore. Here I use Manhattan instead of Euclidean 
        //because in this example we dont have diagnosal path.
        function manhattanDistance(startNode, destinationNode) {
            var x = Math.abs(destinationNode.x - startNode.x);
            var y = Math.abs(destinationNode.y - startNode.y);
            var dist = x + y;
            return dist;
        }


        return (

            <div className="turn-by-turn-component">

                <TodoList
                    title="Mandatory work"
                    list={[path]}
                />
                <TodoList
                    title="Optional work"
                    list={[]}
                />
            </div>
        );
    }
}

TurnByTurnComponent.propTypes = {
    destinationLocationId: PropTypes.number,
    locations: PropTypes.arrayOf(PropTypes.shape({
        id: PropTypes.number.isRequired,
        name: PropTypes.string.isRequired,
        x: PropTypes.number.isRequired,
        y: PropTypes.number.isRequired,
        connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
    })),
    originLocationId: PropTypes.number
};

解决方案

There are a few issues in your code:

  • return originLocationId; should not happen. When the source is equal to the target, then set the path, and make sure the final return of this function is executed, as you want to return the div element.

  • When the target is found in the loop, not only should the path be built, but the loop should be exited. So add a break

  • currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode); is not right: you don't want to modify currentNode.gcost: its value should not depend on the outgoing edge to that neighbour. Instead store this sum in a temporary variable (like gcost)

  • The comparison with neighbourNode.gcost will not work when that node does not yet have a gcost member. I don't see in your code that it got a default value that makes sure this condition is true, so you should use a default value here, like (neighbourNode.gcost ?? Infinity)

  • path = path.reverse().join("->"); should better be executed always, also when there is no solution (so path is a string) or when the source and target are the same node.

Here is a corrected version, slightly adapted to run here as a runnable snippet:

function render() {
    const {
        destinationLocationId,
        locations,
        originLocationId
    } = this.props;
    let path = [];
    
    if (destinationLocationId != null && originLocationId != null) {
        path = [originLocationId]; // The value for when the next if condition is not true 
        if (originLocationId != destinationLocationId) {
            var openList = [];
            let startNode = getNodeById(originLocationId);
            let destinationNode = getNodeById(destinationLocationId)
            if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {

                startNode.gcost = 0
                startNode.heuristic = manhattanDistance(startNode, destinationNode)
                startNode.fcost = startNode.gcost + startNode.heuristic;
                
                openList.push(startNode);
                while (openList.length > 0) {
                    var currentNode = getNodeOfMinFscore(openList);
                    if (currentIsEqualDistanation(currentNode)) {
                        path = getPath(currentNode);
                        break; // Should end the search here!
                    }
                    deleteCurrentFromOpenList(currentNode, openList);
                    for (let neighbourId of currentNode.connectedToIds) { 
                        var neighbourNode = getNodeById(neighbourId);
                        // Should not modify the current node's gcost. Use a variable instead:
                        let gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
                        // Condition should also work when neighbour has no gcost yet:
                        if (gcost < (neighbourNode.gcost ?? Infinity)) {
                            neighbourNode.parentId = currentNode.id;
                            neighbourNode.gcost = gcost; // Use the variable
                            neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
                            neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
                            addNeighbourNodeToOpenList(neighbourNode, openList);
                        }
                    }
                }
            }
        }
    }
    // Convert the path to string in ALL cases:
    path = path.reverse().join("->");

    function addNeighbourNodeToOpenList(neighbourNode, openList) {
        if (!openList.includes(neighbourNode)) {
            openList.push(neighbourNode);
        }
    }


    function deleteCurrentFromOpenList(currNode, openList) {
        const currIndex = openList.indexOf(currNode);
        openList.splice(currIndex, 1);
    }

    function currentIsEqualDistanation(currNode) {
        return (currNode.id == destinationLocationId)
    }

    function getNodeById(nid) {
        var node;
        for (let i = 0; i < locations.length; i++) {
            if (locations[i].id == nid) {
                node = locations[i]
            }
        }
        return node
    }

    function getPath(destNode) {
        var parentPath = []
        var parentId;
        while (destNode.parentId != null) {
            parentPath.push(destNode.name)
            parentId = destNode.parentId;
            destNode = getNodeById(parentId);
        }
        parentPath.push(getNodeById(originLocationId).name)
        return parentPath;
    }

    function getNodeOfMinFscore(openList) {
        var minFscore = openList[0].fcost;
        var nodeOfminFscore;
        for (let i = 0; i < openList.length; i++) {
            if (openList[i].fcost <= minFscore) {
                minFscore = openList[i].fcost
                nodeOfminFscore = openList[i]
            }
        }

        return nodeOfminFscore
    }

    function manhattanDistance(stNode, dstNode) {
        var x = Math.abs(dstNode.x - stNode.x);
        var y = Math.abs(dstNode.y - stNode.y);
        var dist = x + y;
        return dist;
    }

    return "Shortest path: " + path;
}

// Demo
let props = {
    locations: [
        { id: 1, x: 312, y: 152, connectedToIds: [4,2], name: "Thetaham" },
        { id: 2, x: 590, y: 388, connectedToIds: [1,3], name: "Deltabury" },
        { id: 3, x: 428, y: 737, connectedToIds: [2], name: "Gammation" },
        { id: 4, x: 222, y: 430, connectedToIds: [1], name: "Theta City" },
    ],
    originLocationId: 1,
    destinationLocationId: 3, 
};

console.log(render.call({props}));

这篇关于A*(A-star) 算法给出错误的路径和崩溃的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆