दो ट्री नोड्स

Question

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

एक दो शब्दों के साथ प्रदान की दी गई है:

मैं 150,000 शब्दों का एक शब्दकोश, एक Trie कार्यान्वयन में संग्रहीत है, यहाँ मेरी विशेष कार्यान्वयन दिखता है की तरह है। प्रारंभ शब्द से लेकर अंतिम शब्द तक अन्य अंग्रेजी शब्दों का सबसे छोटा मार्ग (एक चरित्र द्वारा बदला गया) का लक्ष्य प्राप्त करने के लक्ष्य के साथ।

उदाहरण के लिए:

प्रारंभ: कुत्ता

अंत: बिल्ली

पथ: कुत्ता, डॉट, खाट, बिल्ली

पथ: कुत्ता, कॉग, प्रवेश करें, दलदल, बॉट, कोट, बिल्ली

पथ: कुत्ता, डो, जो, जॉय, जोट, कोट, बिल्ली

---

मेरे वर्तमान कार्यान्वयन कई पुनरावृत्तियों के माध्यम से चला गया है, लेकिन सबसे सरल मैं के लिए स्यूडोकोड प्रदान कर सकते हैं (जैसा कि वास्तविक कोड कई फ़ाइलों है):

var start = "dog"; 
var end = "cat"; 
var alphabet = [a, b, c, d, e .... y, z]; 
var possible_words = []; 

for (var letter_of_word = 0; letter_of_word < start.length; letter_of_word++) { 
    for (var letter_of_alphabet = 0; letter_of_alphabet < alphabet.length; letter_of_alphabet++) { 
     var new_word = start; 
     new_word.characterAt(letter_of_word) = alphabet[letter_of_alphabet]; 
     if (in_dictionary(new_word)) { 
      add_to.possible_words; 
     } 
    } 
} 

function bfs() { 
    var q = []; 
    ... usual bfs implementation here .. 
} 

---

नोंस:

• एक प्रारंभ शब्द और एक फिनिश शब्द
• शब्द समान लंबाई के हैं
• शब्द अंग्रेज़ी शब्द हैं
• यह संभव है वहाँ के लिए एक रास्ता

नहीं होने के लिए

---

प्रश्न:

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

दूसरा, क्या मुझे एक अलग खोज एल्गोरिदम का उपयोग करना चाहिए, मैंने ए * और बेस्ट फर्स्ट सर्च को संभावनाओं के रूप में देखा है, लेकिन उनको वजन की आवश्यकता है, जो मेरे पास नहीं है।

विचार?

Answer 1

टिप्पणियों में अनुरोध के रूप में, यह दर्शाता है कि पूर्णांक के बिट्स में लिंक किए गए शब्दों को एन्कोडिंग करके मेरा क्या मतलब है।

सी ++ में, ऐसा कुछ ऐसा दिख सकता है ...

// populate a list of known words (or read from file etc)... 
std::vector<std::string> words = { 
    "dog", "dot", "cot", "cat", "log", "bog" 
}; 

// create sets of one-letter-apart words... 
std::unordered_map<std::string, int32_t> links; 
for (auto& word : words) 
    for (int i = 0; i < word.size(); ++i) 
    { 
     char save = word[i]; 
     word[i] = '_'; 
     links[word] |= 1 << (save - 'a'); 
     word[i] = save; 
    } 

ऊपर कोड चलने के बाद, links[x] - जहां x एक अंडरस्कोर एक ला d_g के साथ बदल दिया एक पत्र के साथ एक शब्द है - एक पूर्णांक पत्र है कि जाना जाता है शब्द रचना के अंडरस्कोर जगह ले सकता है यह दर्शाता है प्राप्त करता है। यदि कम से कम महत्वपूर्ण बिट चालू है, तो 'डैग' एक ज्ञात शब्द है, यदि अगली-से-कम-से-कम महत्वपूर्ण बिट चालू है, तो 'डीबीजी' शब्द ज्ञात है ..

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

std::unordered_map<std::string, std::vector<const char*>> links; 
for (auto& word : words) 
    for (int i = 0; i < word.size(); ++i) 
    { 
     char save = word[i]; 
     word[i] = '_'; 
     links[word].push_back(word.c_str()); 
     word[i] = save; 
    } 

किसी भी तरह से, आप तो एक ग्राफ उन यह एकल चरित्र में परिवर्तन के साथ के रूप में बदल सकते हैं करने के लिए प्रत्येक शब्द को जोड़ने की है। फिर आप किसी भी दो शब्दों के बीच सबसे छोटा रास्ता खोजने के लिए Dijkstra's algorithm का तर्क लागू कर सकते हैं।

Answer 2

इस प्रश्न को तारांकित करने वाले लोगों के लिए एक अपडेट जोड़ने के लिए, मैंने इस विशेष डेटा-संरचना के लिए जावास्क्रिप्ट में कार्यान्वयन के लिए एक गिथब भंडार जोड़ा है।

https://github.com/acupajoe/Lexibit.js

आप सभी मदद और विचारों के लिए धन्यवाद!