回答編集履歴

5

edit

2018/06/13 12:52

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -16,9 +16,9 @@
16
16
 
17
17
  for _ in range(3):
18
18
 
19
- mcnt = 0
19
+ mcnt = -1
20
20
 
21
- best = 0
21
+ best = -1
22
22
 
23
23
  mcovered = None
24
24
 
@@ -82,7 +82,7 @@
82
82
 
83
83
  mcnt = -1
84
84
 
85
- best = 0
85
+ best = -1
86
86
 
87
87
  mcovered = []
88
88
 

4

edit

2018/06/13 12:51

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -6,9 +6,9 @@
6
6
 
7
7
  np.random.seed(2018)
8
8
 
9
- points = np.random.random((100, 2))*2
9
+ points = np.random.random((1000, 2))*10
10
10
 
11
- base_points = np.random.random((10, 2))*2
11
+ base_points = np.random.random((1000, 2))*10
12
12
 
13
13
 
14
14
 
@@ -42,15 +42,25 @@
42
42
 
43
43
  points = points[np.logical_not(mcovered)]
44
44
 
45
+ print(best)
46
+
47
+ print(mcnt)
48
+
49
+ print(points.shape)
50
+
45
51
 
46
52
 
47
53
  centers = np.array(centers)
48
54
 
49
55
  import matplotlib.pyplot as plt
50
56
 
51
- plt.scatter(points[:, 0], points[:, 1])
57
+ fig, ax = plt.subplots(dpi=200)
52
58
 
59
+ ax.set_aspect('equal')
60
+
61
+ ax.scatter(points[:, 0], points[:, 1], s=10)
62
+
53
- plt.scatter(centers[:, 0], centers[:, 1], c='red', s=10**3)
63
+ ax.scatter(centers[:, 0], centers[:, 1], c='red', s=15**2)
54
64
 
55
65
  plt.show()
56
66
 

3

edit

2018/06/12 11:41

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -1,3 +1,73 @@
1
+ ```python
2
+
3
+ import numpy as np
4
+
5
+
6
+
7
+ np.random.seed(2018)
8
+
9
+ points = np.random.random((100, 2))*2
10
+
11
+ base_points = np.random.random((10, 2))*2
12
+
13
+
14
+
15
+ centers = []
16
+
17
+ for _ in range(3):
18
+
19
+ mcnt = 0
20
+
21
+ best = 0
22
+
23
+ mcovered = None
24
+
25
+ for i, bp in enumerate(base_points):
26
+
27
+ dist = np.linalg.norm(points - bp, axis=-1)
28
+
29
+ covered = dist < 0.5
30
+
31
+ cnt = np.sum(covered)
32
+
33
+ if cnt > mcnt:
34
+
35
+ mcovered = covered
36
+
37
+ mcnt = cnt
38
+
39
+ best = i
40
+
41
+ centers.append(base_points[best])
42
+
43
+ points = points[np.logical_not(mcovered)]
44
+
45
+
46
+
47
+ centers = np.array(centers)
48
+
49
+ import matplotlib.pyplot as plt
50
+
51
+ plt.scatter(points[:, 0], points[:, 1])
52
+
53
+ plt.scatter(centers[:, 0], centers[:, 1], c='red', s=10**3)
54
+
55
+ plt.show()
56
+
57
+ ```
58
+
59
+
60
+
61
+ 一般的にpythonは遅くて、高速化するためには外部ライブラリを使用して一気に処理します。
62
+
63
+ 今の場合、点の集合から置局までの距離を一気に計算することができます。
64
+
65
+
66
+
67
+ ---
68
+
69
+
70
+
1
71
  ```python
2
72
 
3
73
  mcnt = -1

2

edit

2018/06/12 11:34

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -4,9 +4,13 @@
4
4
 
5
5
  best = 0
6
6
 
7
+ mcovered = []
8
+
7
9
  for i in range(len(base_points)):
8
10
 
9
11
  cnt = 0
12
+
13
+ covered = []
10
14
 
11
15
  for j in range(len(points)):
12
16
 
@@ -16,11 +20,17 @@
16
20
 
17
21
  cnt = cnt + 1
18
22
 
23
+ covered.append(j)
24
+
19
25
  if cnt > mcnt:
20
26
 
21
27
  mcnt = cnt
22
28
 
23
29
  best = i
30
+
31
+ mcovered = covered
32
+
33
+ points = list(set(points) - set(mcovered))
24
34
 
25
35
  ```
26
36
 
@@ -30,7 +40,9 @@
30
40
 
31
41
 
32
42
 
33
- 取り除くのはpopでも使えばよいでしょう。
43
+ ~~取り除くのはpopでも使えばよいでしょう。~~
44
+
45
+ setの引き算にしました。
34
46
 
35
47
 
36
48
 

1

edit

2018/06/12 10:35

投稿

mkgrei
mkgrei

スコア8560

test CHANGED
@@ -42,24 +42,6 @@
42
42
 
43
43
 
44
44
 
45
- 再度計算する際に置局のカバーする点の数が変わらないことに気づけば、カバーできる点の個数を配列にして、それをソートすることでより高速に解を求めることができます。
46
-
47
-
48
-
49
- 使うものはsorted, itemgetter, zipあたりでしょう。
50
-
51
- http://please-sleep.cou929.nu/python-sorted-function-interface.html
52
-
53
-
54
-
55
- さらにはやくするのなら、numpyを使って、sortargsを使います。
56
-
57
-
58
-
59
- ---
60
-
61
-
62
-
63
45
  余談ですが、CAL_RHOの設計が悪いです。
64
46
 
65
47
  2点間の距離を計算する関数ですから、x1,x2,y1,y2を引数にすると順番をミスると大変なことになります。