javascript - A*(A-star) 算法给出错误的路径并崩溃

Question

我正在 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”。我的程序不应该返回路径，而是在向列表中添加节点和边时不断更新路径。请帮忙，我已经被困了几个小时了：/

我的代码：

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:[]、gcost:Infinity、fcost:0、heuristic:0、parentId:null。 我现在的新代码是：

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

标签： javascriptreactjsdata-structuresgrapha-star

Answer 1

您的代码中有几个问题：

• return originLocationId;不应该发生。当源等于目标时，然后设置路径，并确保return执行该函数的final，因为您要返回div元素。

• 当在循环中找到目标时，不仅应该path构建，而且应该退出循环。所以添加一个break

• currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);是不对的：您不想修改currentNode.gcost：它的值不应该取决于该邻居的传出边缘。而是将此总和存储在临时变量中（如gcost）

• neighbourNode.gcost当该节点还没有成员时，与的比较将不起作用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}));