यात्रा टिकट समस्या

Question

आपको विभिन्न परिवहनों के लिए यात्रा टिकटों का ढेर दिया जाता है जो आपको एक बिंदु ए से बिंदु बी से रास्ते पर कई स्टॉप के माध्यम से ले जाएगा। सभी टिकट आदेश से बाहर हैं और आप नहीं जानते कि आपकी यात्रा कहां से शुरू होती है, न ही यह कहां समाप्त होता है। अपनी यात्रा पूरी करने के लिए टिकटों को सही क्रम में क्रमबद्ध करें।

tickets = [ 
    {from: "Barcelona", to: "New York"} 
    {from: "Barcelona", to: "Gerona"}, 
    {from: "Madrid", to: "Barcelona"}, 
    {from: "Gerona", to: "Barcelona"} 
]

मुझे लगता है, सही क्रम है एक है कि:

tickets = [ 
    {from: "Madrid", to: "Barcelona"}, 
    {from: "Barcelona", to: "Gerona"}, 
    {from: "Gerona", to: "Barcelona"}, 
    {from: "Barcelona", to: "New York"} 
]

क्योंकि वहाँ मैड्रिड के लिए कोई टिकट, और न्यूयॉर्क से कोई टिकट है।

उस कार्य के लिए सबसे अच्छा एल्गोरिदम क्या होगा?

भाषा जावास्क्रिप्ट है, लेकिन भाषा-अज्ञेय समाधान पर्याप्त होगा।

अद्यतन: मैं नमूना डेटा पर One-way flight trip problem साथ भ्रमित नहीं होना बदल दिया है।

Answer 1

यदि आप एक से अधिक नोड (एक शहर) पर जा सकते हैं, तो यह eulerian path problem है।

Here आपके पास किस प्रकार के ग्राफ के आधार पर इसे हल करने के लिए दो सरल एल्गोरिदम हैं। आपके पास पृष्ठ 3 here पर एक पुनरावर्ती कार्यान्वयन है।

Answer 2

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

Answer 3

1. अपने टिकट से एक निर्देशित ग्राफ बनाएं प्रवेश के साथ शुरू करने से पढ़ें।
2. नोड है कि अपने परिणाम बनाने के लिए ग्राफ किनारों के माध्यम से सभी नोड पर indegree 0
3. दोहराएं किया है का पता लगाएं

अपडेट: मूल पोस्ट में जोड़े गए जानकारी के साथ, यह समाधान सही समस्या का समाधान नहीं करता है। इसके बजाय IVLad के response पर देखें।

Answer 4

आपको जो मिला है वह एक निर्देशित ग्राफ है, और आप इसमें Eulerian Path ढूंढना चाहते हैं। लिंक किए गए लेख से एक है, जो मूल रूप से है खोजने के लिए एल्गोरिथ्म का वर्णन: बाहर से में कम मार्गों के साथ

1. एक शहर का पता लगाएं एक टिकट (धार), जो जीता द्वारा
2. सफर (यदि वहाँ कोई भी कर रहे हैं, कहीं भी शुरू) ग्राफ को डिस्कनेक्ट नहीं किया गया है अगर यह वहां नहीं है; जब तक कि कोई टिकट मौजूद न हो, उस स्थिति में उस टिकट का उपयोग करें।
3. टिकट (धार) को हटाकर

आप पहुंचना चाहिए सभी टिकट का उपयोग कर लेने को दोहराने, और अंत गंतव्य पर।

Answer 5

निम्नलिखित जावास्क्रिप्ट कार्यान्वयन का नमूना है।

var un = 
[ 
{ from:'c',to:'d'}, 
{ from:'a',to:'b'}, 
{ from:'b',to:'c'}, 
{ from:'z',to:'a'}, 
{ from:'d',to:'m'}, 
] 

function buildTable(un){ 
return un.reduce(function(previousValue, currentValue, currentIndex){ 

//build the table. 
    previousValue.from[currentValue['from']] = currentValue; 
    previousValue.to[currentValue['to']] = currentValue; 

//to find start and end.  
    if(!previousValue.from[currentValue['to']]) previousValue.from[currentValue['to']]= false; 
    if(!previousValue.to[currentValue['from']]) previousValue.to[currentValue['from']]= false; 

    return previousValue; 

},{to:{},from:{}}); 


} 

function getStart(nodes){ 
//find start node indx. 
    for(var i in nodes) 
    if(!nodes[i])return i; 
} 


function print(start,nodes){ 


var sorted = []; 
//while detecting false from buildTable structure. 
    while(start){ 
     var node = nodes[start]; 
     sorted.push(node) 
     start = node['to']; 
//console.log(start) 
    } 

return sorted; 
} 

var sorted = buildTable(un); 
console.log(print(getStart(sorted.to),sorted.from));