मैं प्रतिक्रिया.जेएस में ए * एल्गोरिदम को लागू करने की कोशिश कर रहा हूं लेकिन जब एफस्कोर फ़ंक्शन को लागू करने की बात आती है तो मैं काफी फंस जाता हूं। मुझे पता है कि f=g+h जहां g प्रारंभ नोड से वर्तमान नोड तक gScore है और h वर्तमान नोड से अंत नोड तक अनुमानी दूरी है। मैंने यूक्लिडियन दूरी का उपयोग करके अनुमानी की गणना की जहां मैं वर्तमान और अंत नोड्स के निर्देशांक भेज रहा हूं लेकिन मुझे नहीं पता कि जीस्कोर की गणना कैसे करें। मेरे ग्राफ में प्रत्येक नोड में है: पहचान, नाम, एक्स, वाई, ConnectedToIds:[] // neihbours या ConnectedNodes की सूची। अपडेट: मैंने प्रत्येक नोड में वेरिएबल पैरेंटआईड, एफएसकोर, जीएसकोर, एचस्कोर जोड़े हैं। तो अब प्रत्येक नोड में चर हैं: आईडी, नाम, एक्स, वाई, कनेक्टेड टॉड्स: [], एफस्कोर: 0, जीएसकोर: 0, एचस्कोर: 0, अभिभावक आईडी: शून्य। अपडेट2: OriginLocationId प्रारंभ नोड की आईडी है। गंतव्य स्थान आईडी अंतिम नोड की आईडी है। स्थान सभी नोड्स की एक सूची है। मेरा कोड:

export default class TurnByTurnComponent extends React.PureComponent {
    constructor(props) {
        super(props);
    }

    render() {
        const {
            destinationLocationId,
            locations,
            originLocationId
        } = this.props;
        console.log(locations)
        console.log(originLocationId)
        console.log(destinationLocationId)


        var openedList = [];
        var closedList = [];

        if (destinationLocationId != null && originLocationId != null) {
            openedList.push(originLocationId);
            while (openedList.length != 0) {
                var currentLoc = openedList[0]; //minFvalue
                const currIndex = openedList.indexOf(currentLoc);
                openedList.splice(currIndex, 1); //deleting currentNode from openedList
                closedList.push(currentLoc) //adding currentNode to closedList

                if (currentLoc == destinationLocationId) {
                    //return path
                }

                

            }

        }

        function heuristic(currentNode, endNode) { //euclidean distance
            var x = Math.pow(endNode.x - currentNode.x, 2);
            var y = Math.pow(endNode.y - currentNode.y, 2);
            var dist = Math.sqrt(x + y);
            return dist;
        }

        function gScore(startNode, currentNode) {

        }




        return (
            <div className="turn-by-turn-component">
                {locations.map(loc => (
                    <li key={loc.id}>
                        {loc.name}
                    </li>
                ))}

                <TodoList
                    title="Mandatory work"
                    list={[
                      
                    ]}
                />
                <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
};

अपडेट3: मेरे कोड का नया संस्करण

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


    render() {
        const {
            destinationLocationId,
            locations,
            originLocationId
        } = this.props;


        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 endNode = getNodeById(destinationLocationId)

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


            //start A*
            openList.push(startNode); //starting with the startNode 
            while (openList.length) {
                console.log("inside while")

                var currentNode = getNodeOfMinFscore(openList);

                if (currentIsEqualDistanation(currentNode)) {
                    var path = getPath(currentNode)
                    this.setState({
                        shortestPath: path,
                    });
                    return path //todo
                }
                deleteCurrentFromOpenList(currentNode, openList);

                for (let neighbourId of currentNode.connectedToIds) {

                    var neighbourNode = getNodeById(neighbourId);
                    var currentNodeGcost = currentNode.gcost + manhattanDistance(currentNode,         neighbourNode);
                    console.log(currentNodeGcost)
                    console.log(neighbourNode.gcost)
                    if (currentNodeGcost < neighbourNode.gcost) {
                        console.log("Helloooo")
                        neighbourNode.parentId = currentNode.id;
                        // keep track of the path
                        // total cost saved in neighbour.g
                        neighbourNode.gcost = currentNodeGcost;
                        neighbourNode.heuristic = manhattanDistance(neighbourNode, endNode);
                        neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
                        if (!openList.includes(neighbourId)) {
                            openList.push(neighbourNode);
                        }
                    }
                }
            }
            return null;
        }


        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(endNode) {
            var path = []
            while (endNode.parentId) {
                path.push(endNode.name)
                endNode = endNode.parentId;
            }
            return path;
        }

        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, endNode) {
            var x = Math.abs(endNode.x - startNode.x);
            var y = Math.abs(endNode.y - startNode.y);
            var dist = x + y;
            return dist;
        }


        return (
            <div className="turn-by-turn-component">
                {locations.map(loc => (
                    <li key={loc.id}>
                        {JSON.stringify(loc.name)},
                    </li>
                ))}
                <TodoList
                    title="Mandatory work"
                    list={
                        this.state.shortestPath
                    }
                />
                <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
};
2
AdamA 5 नवम्बर 2021, 01:56

1 उत्तर

सबसे बढ़िया उत्तर

जबकि h अनुमानी है, अंतिम नोड तक पहुंचने के लिए इसकी संभावित लागत का एक प्रशंसनीय अनुमान है, g वर्तमान नोड तक पहुंचने के लिए खर्च की गई वास्तविक लागत है। आपके मामले में यह वही यूक्लिडियन दूरी भी हो सकती है जिसका उपयोग आप h के लिए करते हैं।

वास्तविक स्थिति में, यूक्लिडियन दूरी का उपयोग करते हुए, विभिन्न शहरों को जोड़ने वाला एक ग्राफ, h दो शहरों की हवाई-दूरी है जबकि g उनकी सड़क-दूरी है।

इसके अलावा, यदि आप एक मोनोटोनिक ह्युरिस्टिक (या एक कम आंकने वाली अनुमानी, जैसे कि यूक्लिडियन दूरी) का उपयोग कर रहे हैं, तो आपको करीबी सूची की आवश्यकता नहीं होगी, क्योंकि यह साबित होता है कि पहला पाया गया पथ भी सबसे छोटा होगा: लंबा या पहले से ही देखा गया पथ होगा खोजे जाने से पहले गिरा दिया जाएगा।

संभवतः जो भ्रमित करने वाला है वह यह है कि आपको ग्राफ़ की खोज के दौरान g का ट्रैक रखने की आवश्यकता है, जबकि h केवल करंट और एंड नोड्स के बीच एक सीधी रेखा को मापें, g सभी को मापें आपके द्वारा खोजे गए नोड्स के बीच की रेखाएं वर्तमान तक पहुंचने के लिए।

// h
function heuristic(n1, n2) {
    return Math.sqrt(
        Math.pow(n1.x - n2.x, 2) +
        Math.pow(n1.y - n2.y, 2)
    );
}
// g - actually is the same as h
const cost = heuristic;
function astar(start, end, graph, h, g) {
    if (start.id == end.id) { return [ start.id ] }

    // omitted CLEAN-UP of the graph

    // close is not needed with an optimistic heuristic 
    // so I've commented the "close" parts.
    // An optimistic heuristic works also if you decomment them

    // var close = [];
    var open  = [];

    start.g = 0;
    start.h = h(start, end);
    start.f = start.g + start.h;

    open.push(start);

    while (open.length) {
        // since open is sorted, by popping
        // the last element we take the cheapest node
        var curr = open.pop();

        if (curr == end) { return resolvePath(curr, graph); }
        // close.push(curr);
        for (let nid of curr.connectedToIds) {
            // if (close.some(n => n.id == nid)) { continue; }
            var neighbour = graph.find(n => n.id == nid);
            
            // HERE you compute and store
            // the current g of the node 
            var current_g = curr.g + g(curr, neighbour);

            var isBetter_g = false;
            var isInOpen = open.some(n => n.id == nid);

            // Some implementations skip this check 
            // because they assume that the cost function
            // is a non-negative distance.
            // if so you could check just the two nodes g
            // and insert the node if not already in the open set
            // because the default g of a node is 0
            if (!isInOpen) {
                // unexplored node, maybe we should explore it
                // later, so we add to the open set and
                // we update it with the current path cost
                open.push(neighbour)
                isBetter_g = true;
            }
            else if (current_g < neighbour.g) {
                // the current path is better than
                // those already explored, we need to 
                // update the neighbour with the current path cost
                isBetter_g = true;
            }
            if (isBetter_g) {
                // === path cost update ===

                // track current path
                neighbour.parent = curr.id;
           
                // HERE you keep track of the path
                // total cost saved in neighbour.g
                neighbour.g = current_g;
           
                // neighbour.h is redundant, can be stored directly in f
                // but keep it for debugging purpose
                neighbour.h = h(neighbour, end);

                neighbour.f = neighbour.g + neighbour.h;
                
                if (!isInOpen) {
                    // sorting makes the last element of
                    // open the cheapest node. We sort after
                    // the path cost update to ensure this property
                    open.sort((n1, n2) => n2.f - n1.f)
                }
            }
        }
    }

    // failure
    return []; // or return null
}
// utility to retrieve an array of ids
// from the tracked path
function resolvePath(end, graph) {
    let path = [ end.id ];
    while (end && end.parent >= 0) {
        path.unshift(end.parent);
        end = graph.find(n => n.id == end.parent);
    }
    return path;
}
// example of using the function
astar(startNode, endNode, locations, heuristic, cost);
2
DDomen 5 नवम्बर 2021, 17:58
धन्यवाद। क्या आप कृपया बताएंगे कि आप isBest_g चर का किस प्रकार उपयोग कर रहे हैं? मेरा मतलब है कि हमें इसकी आवश्यकता क्यों है? क्या हम केवल न्यूनतम लागत की जांच नहीं कर सकते?
 – 
AdamA
5 नवम्बर 2021, 16:35
1
यदि आपका आंदोलन विकर्ण यात्रा की अनुमति नहीं देता है, तो आपके अनुमानी को नोड्स के बीच मैनहट्टन दूरी का उपयोग करना चाहिए, जिसकी गणना sqrt या pow के बिना की जा सकती है। H = Math.abs(ax - bx) + Math.abs(ay - by)
 – 
Phaelax z
5 नवम्बर 2021, 17:03
isBest_g, शायद सबसे अच्छा वैरिएबल नाम नहीं है (isBetter_g शायद "बेहतर" होगा), अगर पड़ोसी को अपडेट किया जाना चाहिए या अनदेखा किया जाना चाहिए, तो यह ट्रैक करता है। हां, हमें f लागत की जांच करनी चाहिए, कोड को पोर्ट करते समय मैंने गलती की है, क्योंकि खुले सेट को f द्वारा क्रमबद्ध किया जाना चाहिए, जैसे कि हर बार जब आप open.pop करते हैं तो आपको वास्तव में मिल रहा है सबसे सस्ता नोड। ध्यान दें कि यदि आप एक अस्पष्टीकृत नोड पाते हैं, तो आपको इसे खुली सूची में जोड़ना होगा (बिना f की जांच किए), यही isBest_g का उद्देश्य है। मैं स्पष्ट करने के लिए उत्तर संपादित करूँगा
 – 
DDomen
5 नवम्बर 2021, 17:35
मैनहट्टन के लिए सच है, लेकिन अगर आप यूक्लिडियन को लागत के रूप में उपयोग करते हैं, तो मैनहट्टन मोनोटोनिक संपत्ति खो देगा। मामले में उन्हें मिश्रण करने के लिए अतिरिक्त देखभाल की जरूरत है।
 – 
DDomen
5 नवम्बर 2021, 17:38
1
मैं निम्नलिखित लिंक के माध्यम से पढ़ने को प्रोत्साहित करूंगा, क्योंकि मैं ऐसे कई लोगों को जानता हूं जिन्होंने इन लेखों के आधार पर ए * कार्यान्वयन लिखा है। redblobgames.com
 – 
Phaelax z
5 नवम्बर 2021, 23:26