समस्या आसन्न तार के बीच कम है:छंटाई तार इतना है कि आलोचनात्मक दूरी
मैं एन (~ 100k-1m) प्रत्येक डी तार (जैसे 2000) वर्ण लंबा और एक कम वर्णमाला के साथ (जैसे 3 संभव पात्रों)। मैं इन तारों को क्रमबद्ध करना चाहता हूं कि आसन्न तारों के बीच कुछ संभावित परिवर्तन हैं (उदाहरण के लिए हथौड़ा दूरी कम है)। समाधान सबसे अच्छा संभव नहीं है लेकिन बेहतर के करीब होना चाहिए।
उदाहरण
N=4
D=5
//initial strings
1. aaacb
2. bacba
3. acacb
4. cbcba
//sorted so that hamming distance between adjacent strings is low
1. aaacb
3. acacb (Hamming distance 1->3 = 1)
4. cbcba (Hamming distance 3->4 = 4)
2. bacba (Hamming distance 4->2 = 2)
समस्या
के बारे में विचार मैं यह एक गैर तुच्छ समस्या यह है बुरा विचार है। यदि हम प्रत्येक स्ट्रिंग को नोड के रूप में सोचते हैं और किनारों के रूप में अन्य तारों की दूरी के बारे में सोचते हैं, तो हम एक यात्रा विक्रेता की समस्या को देख रहे हैं। स्ट्रिंग्स की बड़ी संख्या का मतलब है कि पहले जोड़ी की दूरी की गणना पहले से ही संभावित रूप से अक्षम है, मुझे लगता है कि समस्या को Canadian Traveller Problem की तरह कुछ और बदलना है।
फिलहाल मेरी समाधान एक VP tree उपयोग करने के लिए समस्या
curr_string = a randomly chosen string from full set
while(tree not empty)
found_string = find nearest string in tree
tree.remove(found_string)
sorted_list.add(curr_string)
curr_string = found_string
लेकिन प्रारंभिक परिणाम गरीब होने के लिए प्रकट करने के लिए एक लालची निकटतम पड़ोसी प्रकार समाधान खोजने के लिए किया गया है। तारों को धक्का देना ताकि अधिक समान लोग निकट हो जाएं, लेकिन मुझे यह पता नहीं है कि यह कितना अच्छा समाधान प्रदान करेगा या यह इस आकार के डेटा को कितना अच्छा करेगा।