जावास्क्रिप्ट

Question

में सबसे छोटा रास्ता जावास्क्रिप्ट में सबसे कम पथों की गणना करने के लिए मैं सप्ताहों की खोज कर रहा हूं। मैं ग्रोनर (उपयुक्त नाम से) https://github.com/loiane/javascript-datastructures-algorithms/tree/master/chapter09 पर डेटा स्ट्रक्चर और एल्गोरिदम पुस्तक के साथ खेल रहा हूं।

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

को सी से पूर्ण कोड यहाँ है: http://jsfiddle.net/8cn7e2x8/

किसी को भी मदद कर सकते हैं?

var graph = new Graph(); 
var myVertices = ['A','B','C','D','E','F']; 
for (var i=0; i<myVertices.length; i++) { 
    graph.addVertex(myVertices[i]); 
} 
graph.addEdge('A', 'B'); 
graph.addEdge('B', 'C'); 
graph.addEdge('B', 'E'); 
graph.addEdge('C', 'D'); 
graph.addEdge('C', 'E'); 
graph.addEdge('C', 'G'); 
graph.addEdge('D', 'E'); 
graph.addEdge('E', 'F'); 

graph.dfs(); 

console.log('********* sortest path - BFS ***********'); 
var shortestPathA = graph.BFS(myVertices[0]); 

//from A to all other vertices 
var fromVertex = myVertices[0]; 

for (i = 1; i < myVertices.length; i++) { 
    var toVertex = myVertices[i], 
    path = new Stack(); 
    for (var v = toVertex; v !== fromVertex; v = shortestPathA.predecessors[v]) { 
     path.push(v); 
    } 
    path.push(fromVertex); 
    var s = path.pop(); 
    while (!path.isEmpty()) { 
     s += ' - ' + path.pop(); 
    } 
    console.log(s); 
} 

Answer 1

हमें यह टिप्पणी करके शुरू करें कि ग्राफ़ असीमित होने पर चौड़ाई वाली पहली खोज (बीएफएस) किसी दिए गए स्रोत वर्टेक्स से सबसे कम पथों की गणना करती है। दूसरे शब्दों में, हम पथ में किनारों की संख्या होने के लिए पथ की लंबाई पर विचार करते हैं।

function Graph() { 
    var neighbors = this.neighbors = {}; // Key = vertex, value = array of neighbors. 

    this.addEdge = function (u, v) { 
    if (neighbors[u] === undefined) { // Add the edge u -> v. 
     neighbors[u] = []; 
    } 
    neighbors[u].push(v); 
    if (neighbors[v] === undefined) { // Also add the edge v -> u so as 
     neighbors[v] = [];    // to implement an undirected graph. 
    }         // For a directed graph, delete 
    neighbors[v].push(u);    // these four lines. 
    }; 

    return this; 
} 

ध्यान दें कि हम एक अनिर्दिष्ट ग्राफ को लागू किया है:

यहाँ एक अनिर्धारित ग्राफ का निर्माण करने के लिए एक आसान तरीका है। जैसा कि इनलाइन टिप्पणियों में बताया गया है, आप addEdge फ़ंक्शन से चार पंक्तियों को हटाकर निर्देशित ग्राफ़ बनाने के लिए कोड को संशोधित कर सकते हैं।

BFS के इस कार्यान्वयन एक निर्देशित ग्राफ पर समान रूप से काम करेगा:

function bfs(graph, source) { 
    var queue = [ { vertex: source, count: 0 } ], 
     visited = { source: true }, 
     tail = 0; 
    while (tail < queue.length) { 
    var u = queue[tail].vertex, 
     count = queue[tail++].count; // Pop a vertex off the queue. 
    print('distance from ' + source + ' to ' + u + ': ' + count); 
    graph.neighbors[u].forEach(function (v) { 
     if (!visited[v]) { 
     visited[v] = true; 
     queue.push({ vertex: v, count: count + 1 }); 
     } 
    }); 
    } 
} 

दिए गए दो कोने बीच कम से कम पथ खोजने के लिए और मार्ग के किनारे कोने प्रदर्शित करने के लिए, हम प्रत्येक शिखर की पूर्ववर्ती याद के रूप में हम ग्राफ का पता लगाने:

function shortestPath(graph, source, target) { 
    if (source == target) { // Delete these four lines if 
    print(source);   // you want to look for a cycle 
    return;     // when the source is equal to 
    }       // the target. 
    var queue = [ source ], 
     visited = { source: true }, 
     predecessor = {}, 
     tail = 0; 
    while (tail < queue.length) { 
    var u = queue[tail++], // Pop a vertex off the queue. 
     neighbors = graph.neighbors[u]; 
    for (var i = 0; i < neighbors.length; ++i) { 
     var v = neighbors[i]; 
     if (visited[v]) { 
     continue; 
     } 
     visited[v] = true; 
     if (v === target) { // Check if the path is complete. 
     var path = [ v ]; // If so, backtrack through the path. 
     while (u !== source) { 
      u = predecessor[u]; 
      path.push(u); 
     } 
     path.reverse(); 
     print(path.join(' &rarr; ')); 
     return; 
     } 
     predecessor[v] = u; 
     queue.push(v); 
    } 
    } 
    print('there is no path from ' + source + ' to ' + target); 
} 

निम्नलिखित स्निपेट ग्राफ है कि आप अपने प्रश्न में दिया पर इन आपरेशनों को दर्शाता है। सबसे पहले हमें A से पहुंचने योग्य सभी शीर्षकों के सबसे छोटे पथ मिलते हैं। फिर हमें B से G और G से A तक सबसे छोटा रास्ता मिलता है।

function Graph() { 
 
    var neighbors = this.neighbors = {}; // Key = vertex, value = array of neighbors. 
 

 
    this.addEdge = function (u, v) { 
 
    if (neighbors[u] === undefined) { // Add the edge u -> v. 
 
     neighbors[u] = []; 
 
    } 
 
    neighbors[u].push(v); 
 
    if (neighbors[v] === undefined) { // Also add the edge v -> u in order 
 
     neighbors[v] = [];    // to implement an undirected graph. 
 
    }         // For a directed graph, delete 
 
    neighbors[v].push(u);    // these four lines. 
 
    }; 
 

 
    return this; 
 
} 
 

 
function bfs(graph, source) { 
 
    var queue = [ { vertex: source, count: 0 } ], 
 
     visited = { source: true }, 
 
     tail = 0; 
 
    while (tail < queue.length) { 
 
    var u = queue[tail].vertex, 
 
     count = queue[tail++].count; // Pop a vertex off the queue. 
 
    print('distance from ' + source + ' to ' + u + ': ' + count); 
 
    graph.neighbors[u].forEach(function (v) { 
 
     if (!visited[v]) { 
 
     visited[v] = true; 
 
     queue.push({ vertex: v, count: count + 1 }); 
 
     } 
 
    }); 
 
    } 
 
} 
 

 
function shortestPath(graph, source, target) { 
 
    if (source == target) { // Delete these four lines if 
 
    print(source);   // you want to look for a cycle 
 
    return;     // when the source is equal to 
 
    }       // the target. 
 
    var queue = [ source ], 
 
     visited = { source: true }, 
 
     predecessor = {}, 
 
     tail = 0; 
 
    while (tail < queue.length) { 
 
    var u = queue[tail++], // Pop a vertex off the queue. 
 
     neighbors = graph.neighbors[u]; 
 
    for (var i = 0; i < neighbors.length; ++i) { 
 
     var v = neighbors[i]; 
 
     if (visited[v]) { 
 
     continue; 
 
     } 
 
     visited[v] = true; 
 
     if (v === target) { // Check if the path is complete. 
 
     var path = [ v ]; // If so, backtrack through the path. 
 
     while (u !== source) { 
 
      path.push(u); 
 
      u = predecessor[u]; 
 
     } 
 
     path.push(u); 
 
     path.reverse(); 
 
     print(path.join(' &rarr; ')); 
 
     return; 
 
     } 
 
     predecessor[v] = u; 
 
     queue.push(v); 
 
    } 
 
    } 
 
    print('there is no path from ' + source + ' to ' + target); 
 
} 
 

 
function print(s) { // A quick and dirty way to display output. 
 
    s = s || ''; 
 
    document.getElementById('display').innerHTML += s + '<br>'; 
 
} 
 

 
window.onload = function() { 
 
    var graph = new Graph(); 
 
    graph.addEdge('A', 'B'); 
 
    graph.addEdge('B', 'C'); 
 
    graph.addEdge('B', 'E'); 
 
    graph.addEdge('C', 'D'); 
 
    graph.addEdge('C', 'E'); 
 
    graph.addEdge('C', 'G'); 
 
    graph.addEdge('D', 'E'); 
 
    graph.addEdge('E', 'F'); 
 

 
    bfs(graph, 'A'); 
 
    print(); 
 
    shortestPath(graph, 'B', 'G'); 
 
    print(); 
 
    shortestPath(graph, 'G', 'A'); 
 
};

body { 
 
    font-family: 'Source Code Pro', monospace; 
 
    font-size: 12px; 
 
}

<link rel="stylesheet" type="text/css" 
 
href="https://fonts.googleapis.com/css?family=Source+Code+Pro"> 
 

 
<div id="display"></id>

Answer 2

अपने प्रश्न पढ़ना, मैं इसे दो तरह से ... या तो आप चीजों की मात्रा की जाँच करता है कम करने के लिए कोशिश कर रहे हैं या आप अपने आप को चर में पारित करने के लिए अनुमति देने के लिए कोशिश कर रहे हैं पढ़ सकते हैं अंत बिंदु बदलें। मैं पूर्व को मानने जा रहा हूं और किसी और को बाद के मामले को संभालने दूंगा।

समस्या पर एक सरसरी नज़र डालने पर, ऐसा लगता है कि आप कॉम्प साइंस में "यात्रा विक्रेता की समस्या" के रूप में जाना जाता है। यह कंप्यूटर प्रोग्रामिंग में एक शास्त्रीय समस्या है जिसे तर्कसंगत असंभव माना जाता है, और यह "अच्छे के दुश्मन होने का सही उदाहरण" है।

शास्त्रीय यात्रा विक्रेता समस्या यह है, "एक विक्रेता के लिए सबसे कम समय में एक मानचित्र पर अपने सभी गंतव्य शहरों तक पहुंचने का एक तरीका है। ऐसा करने के लिए हर संभव मार्ग की जांच किए बिना ऐसा करें।" बात यह है कि ऐसा करने के लिए तार्किक तरीका (अभी तक) कभी भी खोजा जा सकता है (यह साबित होना अभी तक साबित हुआ है कि यह असंभव या संभव है)। उस ने कहा, अगर इसे सबसे छोटा नहीं होना चाहिए, लेकिन केवल एक छोटा रास्ता है, तो कई शॉर्टकट्स ले जा सकते हैं। एक उदाहरण सिर्फ शुरुआत से खत्म करने के लिए एक रेखा की गणना कर रहा है, और उसके बाद निकटतम शिखर के साथ मिलान करने के लिए विचलन में धक्का। दूसरा एक त्रिकोण में पथ को तोड़ना है जो प्रत्येक कोने को केवल अगले निकटतम दो शीर्षकों तक जोड़ता है और फिर सभी शीर्षकों को कनेक्ट होने तक क्लंप को उसी तरह कनेक्ट करता है और फिर केवल उन सबसेट से अपने प्रारंभिक संभावित पथ की गणना करता है।

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