पायथन में सेवा केंद्र के लिए सर्वोत्तम स्थान खोजने का कार्यक्रम

मान लीजिए कि हमारे पास पदों की एक सूची है, जिसमें समन्वय बिंदुओं की एक सूची है जहां कुछ घर स्थित हैं। यदि आप (xc, yc) पर एक सेवा केंद्र बनाना चाहते हैं, तो किसी दिए गए बिंदु से (xc, yc) तक यूक्लिडियन दूरी का योग न्यूनतम है। इसलिए हमें न्यूनतम दूरी का योग ज्ञात करना होगा।

इसलिए, यदि इनपुट स्थिति की तरह है =[(10,11),(11,10),(11,12),(12,11)], तो आउटपुट 4.0 होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अंक :=50

• कुल () फ़ंक्शन को परिभाषित करें। यह cx, cy, स्थिति लेगा

• कुल:=0.0

• पदों में प्रत्येक पी के लिए, करें

  • एक्स, वाई:=पी

  • कुल :=कुल + यूक्लिडियन दूरी (cx, cy) और (x, y) के बीच

• कुल वापसी

• फ़ंक्शन fy() को परिभाषित करें। यह x, स्थिति लेगा

• एल:=0, आर:=101

• रेस :=0

• मेरे लिए 0 से numIter की सीमा में, करें

  • y1:=एल + (आर - एल) / 3

  • y2 :=r - (r - l) / 3

  • t1 :=कुल(x, y1, स्थिति)

  • t2 :=कुल(x, y2, स्थिति)

  • रेस :=न्यूनतम t1 और t2

  • अगर t1

    • आर:=y2

  • अन्यथा,

    • एल :=y1

  • रिटर्न रेस

  • फ़ंक्शन fx() को परिभाषित करें। यह स्थान लेगा

  • एल:=0, आर:=101

  • रेस :=0

  • मेरे लिए 0 से numIter की सीमा में, करें

    • x1 :=एल + (आर - एल) / 3

    • x2 :=r - (r - l) / 3

    • t1 :=fy(x1, पोजीशन)

    • t2 :=fy(x2, position)

    • रेस :=न्यूनतम t1 और t2

    • अगर t1

      • आर:=x2

    • अन्यथा,

      • एल :=x1

  • रिटर्न रेस

मुख्य विधि से, वापसी fx(positions)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

from math import sqrt
def solve(points):
   numIter = 50

   def total(cx, cy, positions):
      total = 0.0
      for p in positions:
         x, y = p
         total += sqrt((cx - x) * (cx - x) + (cy - y) * (cy - y))
      return total

   def fy(x, positions):
      l, r = 0, 101
      res = 0
      for i in range(numIter):
         y1 = l + (r - l) / 3
         y2 = r - (r - l) / 3
         t1 = total(x, y1, positions)
         t2 = total(x, y2, positions)
         res = min(t1, t2)
         if t1 < t2:
            r = y2
         else:
            l = y1
      return res

   def fx(positions):
      l, r = 0, 101
      res = 0
      for i in range(numIter):
         x1 = l + (r - l) / 3
         x2 = r - (r - l) / 3
         t1 = fy(x1, positions)
         t2 = fy(x2, positions)
         res = min(t1, t2)
         if t1 < t2:
            r = x2
         else:
            l = x1
      return res

   return fx(positions)

positions = [(10,11),(11,10),(11,12),(12,11)]
print(solve(positions))

इनपुट

[(10,11),(11,10),(11,12),(12,11)]

आउटपुट

4.0