कार्टेसियन अंक की व्यवस्था के लिए एल्गोरिदम

Question

मेरे पास फॉर्म के कुछ कार्टेशियन बिंदु हैं: (x, y)
जहां x और y दोनों गैर-ऋणात्मक पूर्णांक हैं।

उदा।
(0,0), (1,1), (0,1)

मैं एक एल्गोरिथ्म की जरूरत है इस तरह से ऊपर अंक
कि एक बिंदु से दूसरे
परिवर्तन या तो एक्स के लिए जा रहा व्यवस्था करने के लिए या द्वारा 1.

दूसरे शब्दों में y, मैं
विकर्ण आंदोलन से बचने के लिए चाहते हैं।

तो, ऊपर उल्लिखित बिंदुओं की व्यवस्था की जाएगी:
(0,0), (0,1), (1,1)।

इसी प्रकार (0,0), (1,1), (0,2)
ऐसी कोई व्यवस्था संभव नहीं है।

मैं क्या यह
कॉल करने के लिए लेकिन मैं इसे मैनहट्टन आदेश देने कहेंगे के बारे में निश्चित नहीं हूँ।

क्या कोई मदद कर सकता है?

Answer 1

आप एक व्यवस्था है कि कोने दोहराया नहीं जाता है के लिए देख रहे हैं।

यह सामान्य ग्रिड ग्राफ के लिए एनपी-पूर्ण होने के लिए जाना जाता है, Hamilton Paths in Grid Graphs देखें।

तो शायद आप हैमिल्टनियन पथ/यूक्लिडियन ट्रैवलिंग सेल्समैन समस्या के लिए जाने वाले अनुमानित/हेरिस्टिक/आदि एल्गोरिदम के साथ अपनी किस्मत आजमा सकते हैं।

---

आप एक व्यवस्था है कि दोहरा सकते हैं के लिए देख रहे हैं, लेकिन व्यवस्था में अंक के न्यूनतम संभव संख्या चाहते हैं:

यह फिर एनपी पूरा है। उपरोक्त समस्या को कम किया जा सकता है। ऐसा इसलिए होता है क्योंकि न्यूनतम संभव चलने में एन शिखर होते हैं यदि केवल ग्राफ में हैमिल्टनियन पथ होता है।

---

तुम सिर्फ अंक में से कुछ व्यवस्था के लिए देख रहे हैं,

फिर तुम सब अगर ग्राफ जुड़ा हुआ है की जाँच करने की जरूरत है। यदि यह कनेक्ट नहीं है, तो ऐसी कोई व्यवस्था नहीं हो सकती है।

आप इसे समझने के लिए पहली बार गहराई से खोज कर सकते हैं। ग्राफ़ कनेक्ट होने पर पहली बार गहराई से आपको ऐसी व्यवस्था भी मिल जाएगी।

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

Answer 2

इसे प्रत्येक बिंदु के बीच की दूरी को कम करने के रूप में सरल बनाया जा सकता है। (0,0) से (0,1) तक जाकर बस 1 इकाई है, लेकिन (0,0) से (1,1) तक जा रहा है वास्तव में sqrt (2) है। तो यदि आप अंक को ग्राफ में व्यवस्थित करते हैं, और फिर एक साधारण न्यूनतम-कुल-दूरी ट्रैवर्सल (यात्रा विक्रेता) करते हैं, तो उन्हें सही तरीके से व्यवस्थित करना चाहिए।

संपादित करें: यदि आप कभी भी एक कदम नहीं चाहते हैं जो 1 से बड़ा होगा, तो बस 1 से अधिक वाले किसी भी किनारे को न जोड़ें। ट्रैवर्सल अभी भी सही तरीके से काम करेगा, और किसी भी पथ को अनदेखा करने की आवश्यकता है> 1.

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

Answer 3

ऐसा करने का एक तरीका निर्देशांक की दो क्रमबद्ध सूचियां बनाना है। एक एक्स द्वारा क्रमबद्ध एक और वाई द्वारा क्रमबद्ध एक। फिर, एक समाधान खोजने के लिए।

कोड आ रहा है (सुनिश्चित नहीं है कि अभी तक कौन सी भाषा है; शायद छद्म कोड?) ... संपादित करें - कभी नहीं, क्योंकि मेरा जवाब किसी अन्य के रूप में उतना अच्छा नहीं है।

Answer 4

आप अपने अंक होने वाले चरम के साथ एक ग्राफ बना सकते हैं, और किनारों को वैध चरण हैं।

इस ग्राफ के लिए आप क्या देख रहे हैं Hamiltonian path है। यह, अपने सामान्य रूप में, एक एनपी-पूर्ण समस्या है, जिसका अर्थ है कि कोई ज्ञात कुशल समाधान नहीं है (यानी वह जो अंक की संख्या के साथ अच्छी तरह से स्केल करता है)।

एक यादृच्छिक शिखर से

प्रारंभ, और अगर वहाँ नहीं दौरा एक पड़ोसी है जारी रखने के लिए: विकिपीडिया एक randomized algorithm "सबसे रेखांकन पर तेजी से" है और काम का हो सकता है कि वर्णन करता है।यदि कोई और अधिक अनजान पड़ोसियों नहीं हैं, और गठित पथ हैमिल्टनियन नहीं है, तो यादृच्छिक रूप से एक पड़ोसी को समान रूप से चुनें, और उस पड़ोसी को पिवट के रूप में घुमाएं। (यानी, उस पड़ोसी को किनारे जोड़ें, और उस पड़ोसी से मौजूदा किनारों में से एक को हटा दें ताकि लूप न बनें।) फिर, पथ के नए छोर पर एल्गोरिदम जारी रखें।

हालांकि, इस विशेष स्थिति के लिए एक और अधिक कुशल समाधान मौजूद हो सकता है।

Answer 5

इसे एक ग्राफ के रूप में सोचें जहां प्रत्येक नोड अधिकतम चार किनारों पर है। फिर गहराई/चौड़ाई - पहली खोज करें।

क्या आप के लिए देख लग रहे एक ग्रिड ग्राफ में एक Hamiltonian पथ है:

Answer 6

एक ब्रूट फोर्स रिकर्सिव आरईओक्स दिनचर्या के बारे में कैसे ... सभी संभव पथों को आजमाएं और काम करने वाले लोगों को प्रिंट करें।

/* rexx */ 
point. = 0 /* Boolean for each existing point */ 
say 'Enter origin x and y coordinate:' 
pull xo yo 
point.xo.yo = 1 /* Point exists... */ 
say 'Enter destination x and y coordinate:' 
pull xd yd 
point.xd.yd = 1 /* Point exists... */ 
say 'Enter remaining x and y coordinates, one pair per line:' 
do forever 
    pull x y 
    if x = '' then leave 
    point.x.y = 1 
end 

path = '' 
call findpath xo yo path 
say 'All possible paths have been displayed' 
return 

findpath: procedure expose point. xd yd 
arg x y path 
if \point.x.y then return    /* no such point */ 
newpoint = '(' || x y || ')' 
if pos(newpoint, path) > 0 then return /* abandon on cycle */ 
if x = xd & y = yd then     /* found a path */ 
    say path newpoint 
else do         /* keep searching */ 
    call findpath x+1 y path newpoint 
    call findpath x-1 y path newpoint 
    call findpath x y+1 path newpoint 
    call findpath x y-1 path newpoint 
    end 
return 

उदाहरण सत्र:

Path.rex 
Enter origin x and y coordinate: 
0 0 
Enter destination x and y coordinate: 
2 2 
Enter remaining x and y coordinates, one pair per line: 
0 1 
1 1 
2 1 
1 2 

(0 0) (0 1) (1 1) (2 1) (2 2) 
(0 0) (0 1) (1 1) (1 2) (2 2) 
All possible paths have been displayed 

हालांकि कुछ भी बड़ा पर इस कोशिश मत करो - एक बहुत लंबे समय ले सकता है! लेकिन फिर सवाल ने इष्टतम समाधान होने के बारे में कुछ भी नहीं बताया।