A*(A星)算法给出错误的路径和崩溃

Question

我正在react.js中实现A*(A-星形)算法，但是每当startNode(绿色)或destinationNode(蓝色)有多个邻接或图形中有循环时，我的程序就会崩溃。在从openList中添加和删除邻居时，或者在getPath()函数中更新parentId时，出现了一些错误。我甚至看不到控制台，因为网站崩溃了。每个节点都有: id、name、x、y、connectedToIdsList:[]、g申办:无穷大、f成本:0、启发式:0、parentId:null。我将路径发送到另一个组件"TodoList“，该组件输出路径。我的程序不应该返回路径，而是在向列表中添加节点和边时不断更新路径。请帮帮忙，我已经困了好几个小时了

我的代码：

​

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
};

​

更新链接新节点之前和之后的新问题图片。当我更新图形并添加一个新节点时，路径就消失了。有时还会回来，以此类推，如果我还在图中添加新的节点和边。正如我说过的，每个节点都有: id、name、x、y、connectedToIdsList:[]、g申办:无穷大、f成本:0、启发式:0、parentId:空。我现在的新代码是：

​

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
};

​

​

​

Answer 1

您的代码中有几个问题：

• return originLocationId;不应该发生。当源与目标相等时，设置路径，并确保执行此函数的最终return，因为您希望返回div元素.

。

当在循环中找到目标时，

• 不仅应该构建path，而且应该退出循环。所以添加一个break

• currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);是不对的:您不想修改currentNode.gcost：它的值不应该依赖于该邻居的传出边缘。相反，将此和存储在临时变量中(如gcost)

)。

• 当该节点还没有gcost成员时，与neighbourNode.gcost的比较将无法工作。在您的代码中，我没有看到它得到了一个确保此条件为真的默认值，因此您应该在这里使用默认值，比如(neighbourNode.gcost ?? Infinity)

最好始终执行

• path = path.reverse().join("->");，也可以在没有解决方案(因此path是字符串)或源和目标是同一个节点时执行。

下面是一个经过修正的版本，稍微适合作为一个可运行的片段在这里运行：

​

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}));

​