মনে করুন positions নামক একটি লিস্ট আছে যাতে কিছু বাড়ির কোঅর্ডিনেট পয়েন্ট থাকে। যদি আপনি (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 += sqrt((cx-x)^2 + (cy-y)^2)
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
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
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
