gpt4 book ai didi

python - 最近对实现 Python

转载 作者:太空狗 更新时间:2023-10-29 21:52:38 24 4
gpt4 key购买 nike

我正在尝试使用分而治之的方法在 Python 中实现最近对问题,除了在某些输入情况下出现错误答案外,一切似乎都运行良好。我的代码如下:

def closestSplitPair(Px,Py,d):
X = Px[len(Px)-1][0]
Sy = [item for item in Py if item[0]>=X-d and item[0]<=X+d]
best,p3,q3 = d,None,None
for i in xrange(0,len(Sy)-2):
for j in xrange(1,min(7,len(Sy)-1-i)):
if dist(Sy[i],Sy[i+j]) < best:
best = (Sy[i],Sy[i+j])
p3,q3 = Sy[i],Sy[i+j]
return (p3,q3,best)

我通过递归函数调用上面的函数,如下所示:

def closestPair(Px,Py): """Px and Py are input arrays sorted according to
their x and y coordinates respectively"""
if len(Px) <= 3:
return min_dist(Px)
else:
mid = len(Px)/2
Qx = Px[:mid] ### x-sorted left side of P
Qy = Py[:mid] ### y-sorted left side of P
Rx = Px[mid:] ### x-sorted right side of P
Ry = Py[mid:] ### y-sorted right side of P
(p1,q1,d1) = closestPair(Qx,Qy)
(p2,q2,d2) = closestPair(Rx,Ry)
d = min(d1,d2)
(p3,q3,d3) = closestSplitPair(Px,Py,d)
return min((p1,q1,d1),(p2,q2,d2),(p3,q3,d3),key=lambda tup: tup[2])

其中 min_dist(P) 是具有 3 个或更少元素的列表 P 的最近对算法的强力实现,并返回包含最近点对及其距离的元组。

如果我的输入是 P = [(0,0),(7,6),(2,20),(12,5),(16,16),(5,8),( 19,7),(14,22),(8,19),(7,29),(10,11),(1,13)],那么我的输出是 ((5 ,8),(7,6),2.8284271) 这是正确的输出。但是当我的输入是 P = [(94, 5), (96, -79), (20, 73), (8, -50), (78, 2), (100, 63), ( -14, -69), (99, -8), (-11, -7), (-78, -46)] 我得到的输出是 ((78, 2), ( 94, 5), 16.278820596099706) 而正确的输出应该是 ((94, 5), (99, -8), 13.92838827718412)

最佳答案

您有两个问题,您忘记调用 dist 来更新最佳距离。但主要问题是发生了不止一个递归调用,因此当您找到更接近的默认拆分对时,您可能会最终覆盖,best,p3,q3 = d,None,None。我将 closest_pair 中的最佳对作为参数传递给 closest_split_pair,因此我不会潜在地覆盖该值。

def closest_split_pair(p_x, p_y, delta, best_pair): # <- a parameter
ln_x = len(p_x)
mx_x = p_x[ln_x // 2][0]
s_y = [x for x in p_y if mx_x - delta <= x[0] <= mx_x + delta]
best = delta
for i in range(len(s_y) - 1):
for j in range(1, min(i + 7, (len(s_y) - i))):
p, q = s_y[i], s_y[i + j]
dst = dist(p, q)
if dst < best:
best_pair = p, q
best = dst
return best_pair

closest_pair 的结尾如下所示:

    p_1, q_1 = closest_pair(srt_q_x, srt_q_y)
p_2, q_2 = closest_pair(srt_r_x, srt_r_y)
closest = min(dist(p_1, q_1), dist(p_2, q_2))
# get min of both and then pass that as an arg to closest_split_pair
mn = min((p_1, q_1), (p_2, q_2), key=lambda x: dist(x[0], x[1]))
p_3, q_3 = closest_split_pair(p_x, p_y, closest,mn)
# either return mn or we have a closer split pair
return min(mn, (p_3, q_3), key=lambda x: dist(x[0], x[1]))

您还有其他一些逻辑问题,您的切片逻辑不正确,我对您的代码做了一些更改,其中 brute 只是一个简单的 bruteforce 双循环:

def closestPair(Px, Py):
if len(Px) <= 3:
return brute(Px)

mid = len(Px) / 2
# get left and right half of Px
q, r = Px[:mid], Px[mid:]
# sorted versions of q and r by their x and y coordinates
Qx, Qy = [x for x in q if Py and x[0] <= Px[-1][0]], [x for x in q if x[1] <= Py[-1][1]]
Rx, Ry = [x for x in r if Py and x[0] <= Px[-1][0]], [x for x in r if x[1] <= Py[-1][1]]
(p1, q1) = closestPair(Qx, Qy)
(p2, q2) = closestPair(Rx, Ry)
d = min(dist(p1, p2), dist(p2, q2))
mn = min((p1, q1), (p2, q2), key=lambda x: dist(x[0], x[1]))
(p3, q3) = closest_split_pair(Px, Py, d, mn)
return min(mn, (p3, q3), key=lambda x: dist(x[0], x[1]))

我今天刚做了这个算法,所以毫无疑问需要做一些改进,但这会给你正确的答案。

关于python - 最近对实现 Python,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28237581/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com