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

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

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

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

numIter := 50
एक फ़ंक्शन total() परिभाषित करें। यह cx, cy, positions लेगा
- total := 0.0
- positions में प्रत्येक p के लिए, करें
  - x, y := p
  - total := total + (cx, cy) और (x, y) के बीच यूक्लिडियन दूरी
- total वापस करें
एक फ़ंक्शन fy() परिभाषित करें। यह x, positions लेगा
- l := 0, r := 101
- res := 0
- i को 0 से numIter तक के लिए, करें
  - y1 := l + (r - l) / 3
  - y2 := r - (r - l) / 3
  - t1 := total(x, y1, positions)
  - t2 := total(x, y2, positions)
  - res := t1 और t2 का न्यूनतम
  - यदि t1 < t2, तो
    - r := y2
  - अन्यथा,
    - l := y1
- res वापस करें
एक फ़ंक्शन fx() परिभाषित करें। यह positions लेगा
- l := 0, r := 101
- res := 0
- i को 0 से numIter तक के लिए, करें
  - x1 := l + (r - l) / 3
  - x2 := r - (r - l) / 3
  - t1 := fy(x1, positions)
  - t2 := fy(x2, positions)
  - res := t1 और t2 का न्यूनतम
  - यदि t1 < t2, तो
    - r := x2
  - अन्यथा,
    - l := x1
- res वापस करें

मुख्य विधि से, 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