0

我实现了一个最接近的配对算法，我试图找出随机大小的随机点列表中的哪些点是最接近的。我没有得到有问题的分数，我要么让它再次返回距离，要么什么都没有。我对任何批评持开放态度，但我对为什么会遇到这些问题感到困惑，因为理论上当距离是新低并且温度表明这一点时，我可以将这对点附加或设置为变量或在列表中。

import math
from math import*
from random import *
from graphics import*

def ClosestPair(P,N):
    #Closest Pair of Points are compared, and the distance between the two pairs
    #is output as a number.
    #
    ret = []
    d = math.inf
    for i in range(N):
        for j in range(i+1,N):
            temp = -1
            d = min(d,sqrt((((P[i].getX() - P[j].getX())**2) + ((P[i].getY() - P[j].getY())**2))))
            if temp < d:
                temp = d
            else:
                ret.append(P[i])
                ret.append(P[j])
    return ret

def main():
    #X&Y is lists that get filled with N values of N size
    #X&Y are appended as the X's and Y's of a Point to Array.
    #Then If ClosestPair = 0 prints closest pair saying points are 
    #overlapping
    #Else prints the Distance and Pair of Points that are Closest
    x = []
    y = []
    array = []

    print('Enter A Size for N')
    n = int(input('N = '))
    for a in range(n):
        x.append(randrange(n))
        y.append(randrange(n))
        array.append(Point(x[a],y[a]))
    #print(array)

    if ClosestPair(array,n) == 0:
        print("The Closest Pair of Points are On top of One another!")
    else:
        print("The Distance between the Closest Points is: ", ClosestPair(array,n), "Points Away")

main()
4

1 回答 1

0

内循环是错误的。它应该是这样的：

   temp = min(d,sqrt((((P[i].getX() - P[j].getX())**2) + ((P[i].getY() - P[j].getY())**2))))
   if temp < d:
       temp = d
       ret = [P[i], P[j]]

您的函数现在也返回一对。将其与 0 进行比较是没有意义的。如果需要或重新计算距离，请返回距离和点。

于 2018-01-23T12:28:56.240 回答