K-centerアルゴリズム

Question

私は現在、k-centerアルゴリズムを解くためにpythonを使用しています。 コードを実行すると、ランタイムが制限時間（教師から提供された時間）を超えています。制限されたランタイムを通過できるようにコードを改善する方法はわかりません。 私のコードは以下の通りです：

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.）の多くのルックアップを取り除きました。