สมมติว่าเรามีรายชื่อตำแหน่ง ซึ่งมีรายการจุดพิกัดที่มีบ้านบางหลังตั้งอยู่ หากคุณต้องการสร้างศูนย์บริการที่ (xc, yc) เพื่อให้ผลรวมของระยะทางแบบยุคลิดจากจุดใดก็ตามที่กำหนดถึง (xc, yc) มีค่าน้อยที่สุด เราจึงต้องหาผลรวมของระยะทางขั้นต่ำ
ดังนั้น หากอินพุตเหมือนกับตำแหน่ง =[(10,11),(11,10),(11,12),(12,11)] ผลลัพธ์จะเป็น 4.0
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
numIter :=50
-
กำหนดฟังก์ชัน total() นี่จะใช้เวลา cx, cy, ตำแหน่ง
-
รวม :=0.0
-
สำหรับแต่ละ p ในตำแหน่ง ทำ
-
x, y :=p
-
รวม :=ทั้งหมด + ระยะห่างแบบยุคลิดระหว่าง (cx, cy) และ (x, y)
-
-
ผลตอบแทนรวม
-
กำหนดฟังก์ชัน fy() นี่จะใช้เวลา x ตำแหน่ง
-
l :=0, r :=101
-
res :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง numIter ทำ
-
y1 :=l + (r - l) / 3
-
y2 :=r - (r - l) / 3
-
t1 :=รวม (x, y1, ตำแหน่ง)
-
t2 :=รวม (x, y2, ตำแหน่ง)
-
res :=ขั้นต่ำ t1 และ t2
-
ถ้า t1
-
r :=y2
-
-
มิฉะนั้น
-
ล :=y1
-
-
ผลตอบแทน
-
กำหนดฟังก์ชัน fx() ซึ่งจะเข้ารับตำแหน่ง
-
l :=0, r :=101
-
res :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง numIter ทำ
-
x1 :=l + (r - l) / 3
-
x2 :=r - (r - l) / 3
-
t1 :=fy(x1, ตำแหน่ง)
-
t2 :=fy(x2, ตำแหน่ง)
-
res :=ขั้นต่ำ t1 และ t2
-
ถ้า t1
-
r :=x2
-
-
มิฉะนั้น
-
l :=x1
-
-
-
ผลตอบแทน
-
จากวิธีหลัก คืนค่า fx(ตำแหน่ง)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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
