Cho danh sách tọa độ nhà. Muốn đặt trung tâm dịch vụ (xc, yc) minim hóa tổng khoảng cách Euclid đến các nhà. Tìm tổng khoảng cách tối thiểu.
Ví dụ: positions = [(10,11),(11,10),(11,12),(12,11)], đầu ra = 4.0.
Giải pháp
Tìm kiếm tam phân (ternary search) 2D trên hàm lồi (tổng khoảng cách Euclid):
- numIter := 50
- total(cx, cy, positions): tính tổng sqrt((cx-x)^2 + (cy-y)^2)
- fy(x, positions): ternary search trên y với x cố định
- fx(positions): ternary search trên x, mỗi lần gọi fy
- Trả về fx(positions)
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
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) ** 2 + (cy - y) ** 2)
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))
Đầu vào
[(10,11),(11,10),(11,12),(12,11)]
Đầu ra
4.0