2015-10-10 13 views
5

सबसे पहले, मैं नहीं कोड के लिए पूछ रहा हूँ में अंक का एक सेट को कवर बहुभुज ढूँढना, मैं बस अपना दृष्टिकोण के बारे में स्पष्टीकरण चाहते हैं।छोटी से छोटी एक ग्रिड

दूसरे, अगर यह पूरी तरह से इतना संबंधित नहीं है, मैं सवाल सबसे अधिक प्रासंगिक स्टैक एक्सचेंज साइट पर आ जाएगा। मुझे यकीन है कि यह एक ग्राफ सिद्धांत से संबंधित समस्या है।

तो मैं एक परिभाषित बिंदु (0,0)

ग्रिड में क्षैतिज/ऊर्ध्वाधर लाइनों के बीच प्रत्येक चौराहे एक अन्य बिंदु (मूल से लाइनों की संख्या द्वारा दिए गए) को परिभाषित करता है के साथ एक असीम बड़ी ग्रिड की है।

(x,y) अंक का एक सेट को देखते हुए जहां प्रत्येक x,y एक पूर्णांक है: अंक के आसपास के सबसे छोटे बहुभुज की परिधि लौट आते हैं।

प्रतिबंध:

  • अंकों की संख्या अंक 100,000
  • से कम बहुभुज की परिधि पर स्थित नहीं हो सकता है।
  • बहुभुज के पक्ष केवल ग्रिड में लंबवत/क्षैतिज रेखाओं, या एक वर्ग में एक विकर्ण रेखा के अनुरूप हो सकते हैं।

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

मैं 80 शहरों दिया यात्रा विक्रेता के लिए एक एल्गोरिथ्म लिखा है।

इस प्रश्न में 100,000 अंक हो सकते हैं। इसलिए यह मुझे आश्चर्यचकित करता है कि यदि संभवतः बड़ी संख्या में नोड्स को हल करने के लिए एक संभावित एल्गोरिदम मौजूद है।

क्या कोई और दृष्टिकोण है। क्या मैं इस बारे में गलत तरीके से सोच रहा हूं?

किसी भी मदद के लिए धन्यवाद!

+0

बिल्कुल ग्राफ सिद्धांत या कोडिंग या एल्गोरिथ्म के बारे में सोच के बिना, मैं ज्यामिति कि एक बहुभुज एक चक्र के अंदर अच्छी तरह से फिट होना चाहिए से याद है। तो उस पर आधारित जो आप खोज रहे हैं वह एक सर्कल है। लेकिन फिर फिर आपने ** नियमित बहुभुज ** नहीं कहा लेकिन सिर्फ बहुभुज। और इसलिए शायद मेरा सर्कल विचार काम नहीं करेगा। लेकिन +1, अच्छा सवाल है। और हाँ, एक कोडिंग समाधान है। लेकिन यह लालची प्रोग्रामिंग हो सकता है क्योंकि लालची एल्गोरिदम के विपरीत। –

+0

अंक के सेट के * उत्तल हॉल * के अंदर 100,000 अंक कितने हैं? –

+0

आपकी समस्या अच्छी तरह से निर्दिष्ट नहीं है। चूंकि सभी बिंदुओं वाले सबसे छोटे बहुभुज में एक क्षेत्र होता है जो खाली होता है (यह केवल सबसे छोटा ग्राफ है)। क्या आपको दिए गए बिंदुओं के उत्तल ढक्कन को ढूंढना था? –

उत्तर

1

Convex hull इस समस्या को हल करने के लिए वास्तव में आवश्यक नहीं है।

सबसे अधिक समय कुशल convex hull एल्गोरिथ्म O(nlogh), जहां n अंकों की संख्या कुल मिलाकर है, और h है पतवार पर अंकों की संख्या है।

ऊपर टिप्पणियों के माध्यम से देख रहे हैं, m69 यह किसी न किसी! वह एल्गोरिदम वर्णन करता है (शीर्ष पर थोड़ा अतिरिक्त के साथ) O(n) समय में हासिल किया जा सकता है। Convex Hull विचार स्क्रैप करें !!

  • न्यूनतम वर्ग बनाएं ताकि यह सभी बिंदुओं को घेरे। यह अंक मिनटों की सूची
  • वर्ग में प्रत्येक कोने के लिए, अनुमति दी गई विकर्ण रेखा को खींचें जो सबसे बाहरी बिंदु के सबसे नज़दीक है। यह अंक के माध्यम से लूपिंग और यूक्लिडियन लंबवत दूरी सूत्र का उपयोग करके किया जाता है।यह O(n)
  • मूल वर्ग और विकर्ण रेखाओं के बीच चौराहे का उपयोग करके, बहुभुज के समग्र परिधि की गणना करें।

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

from math import * 
N = int(raw_input()) 
pts = [] 

for i in xrange(N): 
    p1,p2 = map(int, raw_input().split(' ')) 
    pts.append((p1,p2)) 

def isBetween(a, b, c): 
    ab = sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2) 
    ac = sqrt((a[0]-c[0])**2 + (a[1]-c[1])**2) 
    bc = sqrt((b[0]-c[0])**2 + (b[1]-c[1])**2) 
    return abs(ac + bc - ab) < 0.01 # epsilon precision, needs < 1 in grid case 

def getPoints(c): 

    lines = [(-1, c[0][1]+c[0][0]),(1, c[1][1]-c[1][0]),(-1,c[2][1]+c[2][0]),(1,c[3][1]-c[3][0])] 
    maxes = [[0,0],[0,0],[0,0],[0,0]] 

    for count, line in enumerate(lines): 

     pdist = (abs(line[0]*CH[0][0] - CH[0][1] + line[1]))/(sqrt((line[0]*line[0]) + 1)) 
     maxes[count][0] = pdist 
     maxes[count][1] = CH[0] 

    for elem in CH[1:]: 

     for count, line in enumerate(lines): 

      pdist = (abs(line[0]*elem[0] - elem[1] + line[1]))/(sqrt((line[0]*line[0]) + 1)) 
      if pdist < maxes[count][0]: 
       maxes[count][0] = pdist 
       maxes[count][1] = elem 

    for greg in range(4): 
     maxes[greg][1] = list(maxes[greg][1]) 

    maxes[0][1][0] -=1 
    maxes[1][1][0] +=1 
    maxes[2][1][0] +=1 
    maxes[3][1][0] -=1 

    gregarr = [] 

    for i in range(4): 

     y = lines[i][0]*(c[i][0]-maxes[i][1][0]) + maxes[i][1][1] 
     cornerdist = abs(c[i][1] - y) 

     if i == 0: 
      gregarr.append((c[i][0], c[i][1]+cornerdist)) 
      gregarr.append((c[i][0]+cornerdist, c[i][1])) 
     elif i == 1: 
      gregarr.append((c[i][0]-cornerdist, c[i][1])) 
      gregarr.append((c[i][0], c[i][1]+cornerdist)) 
     elif i == 2: 
      gregarr.append((c[i][0], c[i][1]-cornerdist)) 
      gregarr.append((c[i][0]-cornerdist, c[i][1])) 
     else: 
      gregarr.append((c[i][0]+cornerdist, c[i][1])) 
      gregarr.append((c[i][0], c[i][1]-cornerdist)) 

    return gregarr 

def distance(p0, p1): 

    return ((p0[0] - p1[0])*(p0[0] - p1[0]) + (p0[1] - p1[1])*(p0[1] - p1[1]))**(0.5) 

def f7(seq): 
    seen = set() 
    seen_add = seen.add 
    return [ x for x in seq if not (x in seen or seen_add(x))] 

CH = pts 
H = len(CH) 

if H == 0: 
    print('0.000') 
elif H == 1: 
    print('5.656') 
else: 
    per = 0 
    minx = min(CH, key = lambda x: x[0])[0]-1 
    miny = min(CH, key = lambda x: x[1])[1]-1 
    maxx = max(CH, key = lambda x: x[0])[0]+1 
    maxy = max(CH, key = lambda x: x[1])[1]+1 
    corners = [(minx,miny),(maxx, miny),(maxx,maxy),(minx,maxy)] 
    arr = getPoints(corners) 
    arr = f7(arr) 
    arr.append(arr[0]) 
    T = len(arr) 

    for i in range(1,T): 

     per += distance(arr[i-1], arr[i]) 

    print(per) 
संबंधित मुद्दे