python
1import numpy as np
2
3np.random.seed(2018)
4points = np.random.random((1000, 2))*10
5base_points = np.random.random((1000, 2))*10
6
7centers = []
8for _ in range(3):
9 mcnt = -1
10 best = -1
11 mcovered = None
12 for i, bp in enumerate(base_points):
13 dist = np.linalg.norm(points - bp, axis=-1)
14 covered = dist < 0.5
15 cnt = np.sum(covered)
16 if cnt > mcnt:
17 mcovered = covered
18 mcnt = cnt
19 best = i
20 centers.append(base_points[best])
21 points = points[np.logical_not(mcovered)]
22print(best)
23print(mcnt)
24print(points.shape)
25
26centers = np.array(centers)
27import matplotlib.pyplot as plt
28fig, ax = plt.subplots(dpi=200)
29ax.set_aspect('equal')
30ax.scatter(points[:, 0], points[:, 1], s=10)
31ax.scatter(centers[:, 0], centers[:, 1], c='red', s=15**2)
32plt.show()
一般的にpythonは遅くて、高速化するためには外部ライブラリを使用して一気に処理します。
今の場合、点の集合から置局までの距離を一気に計算することができます。
python
1mcnt = -1
2best = -1
3mcovered = []
4for i in range(len(base_points)):
5 cnt = 0
6 covered = []
7 for j in range(len(points)):
8 distance = CAL_RHO(base_points[i][0],base_points[i][1],points[j][0],points[j][1])
9 if distance < 0.5:
10 cnt = cnt + 1
11 covered.append(j)
12 if cnt > mcnt:
13 mcnt = cnt
14 best = i
15 mcovered = covered
16points = list(set(points) - set(mcovered))
古典的な方法。
今までの1番カバーしている置局の番号と、そこでカバーできる点の数を記録して、新しい置局でより多くの点をカバーできるのなら、ベストの置局を更新する方法です。
取り除くのはpopでも使えばよいでしょう。
setの引き算にしました。
これを入れ子に行うことで最低限の要求が満たされます。
余談ですが、CAL_RHOの設計が悪いです。
2点間の距離を計算する関数ですから、x1,x2,y1,y2を引数にすると順番をミスると大変なことになります。
それよりも、p=(x,y)としてp1,p2を引数にした方がバグを防げます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/06/12 10:26
2018/06/12 10:30
2018/06/12 10:38
2018/06/12 10:41
2018/06/12 10:42
2018/06/12 10:44
2018/06/12 11:42
2018/06/13 01:52
2018/06/13 10:08
2018/06/13 11:28