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