python - K中心算法

Question

我目前正在使用 python 来解决 k-center 算法。当我运行我的代码时，它的运行时间超过了限制时间(由我的老师提供)，我不太知道如何改进我的代码以使其能够通过有限的运行时间。我的代码如下:

import math

# 1.Import group
# 2.Find the most farthest point in this group.
# 3.reassign the rest points between two center points
# 4.Find the most farthest point from its center point, and make it the newest center point 
# 5.reassign points among all center points
# 6.Repeat 4 and 5 step untill the answer fits the condition

class point():
    def __init__(self,x,y,num,group=[]):
        self.x = x
        self.y = y
        self.id = num
        self.group = []

def range_cus(one,two):
    return math.sqrt(math.pow((one.x-two.x),2)+math.pow((one.y-two.y),2))

def reassign(all_points,all_answer):
    for i in range(len(all_answer)):
        all_answer[i].group = []
    for i in range(len(all_points)):
        if all_points[i] not in all_answer:
        min_length = 0
        for j in range(len(all_answer)):
            current_length = range_cus(all_answer[j],all_points[i])
            if min_length == 0:
                min_length = current_length
                current_group = all_answer[j]
            elif current_length < min_length:
                min_length = current_length
                current_group = all_answer[j]
        current_group.group.append(all_points[i])

def search(all_answer,seek_points_number):
    if seek_points_number == 0:
        return 0
    answer_range = 0
    for j in range(len(all_answer)):
        for i in range(len(all_answer[j].group)):
            if range_cus(all_answer[j],all_answer[j].group[i])>answer_range:
                answer_range = range_cus(all_answer[j].group[i],all_answer[j])
                answer_obj = all_answer[j].group[i]
    seek_points_number -= 1
    final_answer.append(answer_obj)
    reassign(group,final_answer)
    search(final_answer,seek_points_number)

info = raw_input().split(',')
info = [int(i) for i in info]
group = []
final_answer = []
for i in range(info[0]):
    x = raw_input().split(',')
    group.append(point(float(x[0]),float(x[1]),i+1))

final_answer.append(group[info[2]-1])
group[info[2]-1].group = [point for point in group if point not in final_answer]

search(final_answer,info[1]-1)
print ",".join([str(answer.id) for answer in final_answer])

请帮我检查一下应该在哪里修改函数以节省一些运行时间。

Example input:

10,3,10 #The first number denotes the sets of data.The second denotes the number of answer I want to return.The third denotes the first center point's id.                   
21.00,38.00
26.00,28.00
45.00,62.00
31.00,51.00
39.00,44.00
42.00,39.00
21.00,27.00
28.00,29.00
31.00,60.00
27.00,54.00

Example output

10,7,6

Answer 1

只需重写 range_cus 函数，您至少可以节省一些时间。当您在嵌套循环中调用此函数时，它应该是一个很好的攻击点。尝试将其替换为

def range_cus(one,two):
    return sqrt((one.x - two.x)**2 + (one.y - two.y)**2)

并记住在程序顶部执行 from math import sqrt。在此版本中，您摆脱了对 math 对象 (math.)

的大量查找