質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 2.7

Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

246閲覧

もっとも多くポイントをカバーする置局点を特定

yositigu

総合スコア17

Python 2.7

Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2018/06/12 09:45

base_points:置局点
points:ランダムポイント

①base_pointsとpointsの距離を計算
②距離が0.5以下ならカバーエリアと判定
③カバーしたポイント数をカウント
④もっともカバーした置局点を特定
⑤カバーされたポイントをpointsから除外
⑥①〜⑤を繰り返す。(とりあえず3回くらい)

③までプログラムをかけたのですが、④以降が書けず。
教えていただけるでしょうか。
言語はpython3でお願いいたします。

python

1 for i in range(len(base_points)): 2 cnt = 0 3 for j in range(len(points)): 4 distance = CAL_RHO(base_points[i][0],base_points[i][1],points[j][0],points[j][1]) 5 if distance < 0.5: 6 cnt = cnt + 1

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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:11

編集2018/06/13 12:52
mkgrei

総合スコア8560

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yositigu

2018/06/12 10:26

ありがとうございます。 余談の意味をもう少し詳しく教えていただけるでしょうか?
yositigu

2018/06/12 10:30

これだと、置局点のindexとカバーするポイント数はわかるのですが、どのポイントをカバーされたのかわからず、カバーされたポイントを取り除く処理をどのようにすれば良いでしょうか
yositigu

2018/06/12 10:38

points = list(set(points) - set(mcovered)) で unhashable type: 'numpy.ndarray'というエラーが出てしまいました。。
mkgrei

2018/06/12 10:41

mcnt同様mcoveredを使って記録しておいて、最後に取り除けばよいです。 コードに追記したものでは集合を使って取り除いています。 本当はリストに戻す必要もないのですが、既存のコード優先で。 リストとセットの切り替えで倍以上の時間を費やしているはずです。 --- 余談のところは、 今 def CAL_RHO(x1, x2, y1, y2): ....return math.sqrt((x1-x2)**2 + (y1-y2)**2) のように実装されているはずです。 これは誤って、CAL_RHO(x1,y1,x2, y2)のようにしてしまったときにエラーのないバグを引き起こします。 def CAL_RHO(p1, p2): ....return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) ならば上記のバグは起こしえません。 コードの書き方を工夫することで、意味はないがすごく時間のかかるデバッグから距離を置くことができます。
mkgrei

2018/06/12 10:42

numpyでしたか、それならもっとはやく計算できます。 コードを追記します。
yositigu

2018/06/12 10:44

余談について理解しました。ありがとうございます。 高速化できるところがあれば、教えていただけるでしょうか? かなりのボリュームがある処理をしたいと考えているためです。
mkgrei

2018/06/12 11:42

追記しました。 100000点くらいなら我慢できる時間で計算できます。
yositigu

2018/06/13 01:52

完璧なプログラムありがとうございます。 dist = np.linalg.norm(points - bp, axis=-1) で距離計算しているところを distance = CAL_RHO(base_points[i][0],base_points[i][1],points[j][0],points[j][1])に書き換えたいのですが、どうすればいいのか悩んでおります。 distance = CAL_RHO(bp[0],bp[i][1],points[j][0],points[j][1]) として、pointsのところをどう書けばいいのか...
mkgrei

2018/06/13 10:08

パフォーマンスを重視するのであれば、CAL_RHOのやっていることを全部ベクトル形式で書くしかありません。 for文を回すと10倍以上の計算時間がかかってしまいます。 def vCAL_RHO(p1s, p2): ..ans = np.zeros(p1s.shape[0]) ..for i, p1 in enumerate(p1s): ....ans[i] = CAL_RHO(p1, p2) ..return ans
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問