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

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

新規登録して質問してみよう
ただいま回答率
85.45%
Matplotlib

MatplotlibはPythonのおよび、NumPy用のグラフ描画ライブラリです。多くの場合、IPythonと連携して使われます。

Visual Studio

Microsoft Visual StudioはMicrosoftによる統合開発環境(IDE)です。多種多様なプログラミング言語に対応しています。

Python

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

pandas

Pandasは、PythonでRにおけるデータフレームに似た型を持たせることができるライブラリです。 行列計算の負担が大幅に軽減されるため、Rで行っていた集計作業をPythonでも比較的簡単に行えます。 データ構造を変更したりデータ分析したりするときにも便利です。

Q&A

1回答

395閲覧

経緯度情報を基にした最大被覆問題を解きたい

退会済みユーザー

退会済みユーザー

総合スコア0

Matplotlib

MatplotlibはPythonのおよび、NumPy用のグラフ描画ライブラリです。多くの場合、IPythonと連携して使われます。

Visual Studio

Microsoft Visual StudioはMicrosoftによる統合開発環境(IDE)です。多種多様なプログラミング言語に対応しています。

Python

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

pandas

Pandasは、PythonでRにおけるデータフレームに似た型を持たせることができるライブラリです。 行列計算の負担が大幅に軽減されるため、Rで行っていた集計作業をPythonでも比較的簡単に行えます。 データ構造を変更したりデータ分析したりするときにも便利です。

0グッド

0クリップ

投稿2024/04/09 11:08

実現したいこと

数理最適化の一つである最大被覆問題において,198個の経緯度情報(X座標,Y座標)を基にしたポ集合(点)をカバー(円に含む)する入力した値の数だけの集合とそれを中心とした円(需要範囲)が描画される実行結果を導出したい.

発生している問題・分からないこと

経緯度情報を持つ198個の点と入力した値の数だけの点とそれを中心とした円は描画される状態にあるが、ただ入力した値の数だけの点がランダムに配置されてしまう。全ての集合をカバーするような実行結果を算出するためにどうすればいいか知りたい。

該当のソースコード

Python

1import pandas as pd 2import numpy as np 3import matplotlib.pyplot as plt 4import matplotlib.patches as patches 5import random, math, time 6import pulp 7 8 9#1.入力データ生成:住居の設置点を読み込む 10def make_data_ad(): 11 #1-1.住居の位置情報を格納したcsvファイルを読み込む 12 df = pd.read_csv("X_Y_data(rep_housing).csv", encoding="utf-8") 13 #1-2.変数[X]に設置する住居のX座標値(経度)を代入 14 X = df["X_CODE"] 15 #1-3.変数[Y]に設置する住居のY座標値(緯度)を代入 16 Y = df["Y_CODE"] 17 #1-4.変数[X_ad]・[Y_ad],を値として返す 18 return X,Y 19 20#2.入力データ生成:資源回収物拠点の設置可能点を生成 21def make_data_si(sigen, upper_x, upper_y): 22 random.seed(10) 23 #2-1.変数[si_X]に資源回収物拠点の設置可能点を代入 24 si_X = [random.uniform(137.689, upper_x) for i in range(sigen)] 25 #2-2.変数[si_X]に資源回収物拠点の設置可能点を代入 26 si_Y =[random.uniform(34.682, upper_y) for i in range(sigen)] 27 #2-3.[si_X]・[si_Y]を値として返す 28 return [si_X, si_Y] 29 30#3.住居と資源回収物拠点間の直線距離を測定する 31def distance(si): 32 ad1,ad2 = make_data_ad() 33 for X_ad, Y_ad in zip(ad1, ad2): 34 unit_ad = [X_ad, Y_ad] 35 #3-1.変数[dx]に住居のX座標値から資源回収物拠点のX座標値を引いたx軸方向の距離を代入 36 dx = unit_ad[0] - si[0] 37 #3-2.変数[dy]に住居のY座標値から資源回収物拠点のY座標値を引いたy軸方向の距離を代入 38 dy = unit_ad[1] - si[1] 39 #3-3.x軸方向の距離の二乗とy軸方向の距離の二乗の和の平方根を求める 40 return math.sqrt(dx **2 + dy **2) 41 42#4.需要変数(二値変数)行列を生成 43def make_matrix(ps, r): 44 #5.許容領域内に分析対象(住居)が収まっているかを判断する 45 def check(a): 46 #5-1.「もし施設間の距離が許容領域の半径以下なら,要素(資源回収物拠点)を1に、それ以外は0にする」 47 if a <= r: 48 return 1 49 else: 50 return 0 51 #4-1.フィールド上にプロットするためにn次正方行列に整形する用のリスト[unit_list]を作成 52 unit_list = [] 53 #4-2.変数[n,m]に[X]と[Y]の座標値を一つにまとめたものを代入する 54 for n, m in zip(ps[0], ps[1]): 55 #4-3.変数[unit]に変数[n,m]を代入 56 unit = (n, m) 57 #4-4.変数[unit_list]に[unit]を追加 58 unit_list.append(unit) 59 #4‐5.[unit_list]から変数p1,p2にそれぞれX・Y座標値を代入し、変数[distance(p1, p2)]に入っている距離が許容領域の半径に収まるかどうか判断する 60 return [check(distance(p1)) for p1 in unit_list] 61 62#6.グラフ上に結果を描写する 63def draw(ps, fs, r): 64 #6-0.make_data_adを実行 65 ad1,ad2 = make_data_ad() 66 #6-1.変数[fig]にx軸、y軸における描画領域の大きさを代入する 67 plt.figure(figsize=(5, 5)) 68 #6-2.変数[ax]にグラフの設定を保存するための枠を作成 69 ax = plt.axes() 70 #6-3.変数[x]にグラフ軸の数値幅と増幅単位の設定を保存 71 x = np.arange(137.69, 137.76, 0.1) 72 #6-4.住居の位置をグラフ上に描画する 73 plt.scatter(ad1, ad2) 74 #6-5.for文を用いて資源回収物拠点のX・Y座標値を変数[(i, j)]に,変数[k]に住宅の代表点から資源回収物拠点までの距離を代入する 75 for k, (i, j) in zip(fs, zip(ps[0], ps[1])): 76 #6-6.もし資源回収物拠点を設置する場合の描画設定を行う 77 if k.value() == 1: 78 #6-6-1.資源回収物拠点の色は赤色 79 plt.scatter(i, j, s=2, color='red') 80 #6-6-2.許容領域の描画設定を行う 81 c = patches.Circle(xy=(i, j), radius=r, fill=False) 82 #6-6-3.許容領域を描画する 83 ax.add_patch(c) 84 #6-7.資源回収物拠点を設置しない場合の設定を行う 85 else: 86 #6-7-1.passする 87 pass 88 #6-8.縦横比が同じ長さになるように調整。 89 plt.axis('scaled') 90 ax.set_aspect('equal') 91 #6-9.グリッド線を表示 92 plt.grid() 93 #6-10.ⅹ軸のラベルを設定 94 ax.set_xlabel('経度', fontname="MS Gothic") 95 #6-11.y軸のラベルを設定 96 ax.set_ylabel('緯度', fontname="MS Gothic") 97 #6-12.x軸の下限値と上限値とその間隔を設定 98 ax.set_xticks(np.linspace(137, 138, 10)) 99 #6-13.y軸の下限値と上限値とその間隔を設定 100 ax.set_yticks(np.linspace(34, 35, 10)) 101 #6-14.グラフを描画 102 plt.show() 103 104#7.住居と資源回収物拠点における集合被覆問題を解く 105def solver_set(ps, r): 106 #7-1.変数[size]に資源回収物拠点のx座標値の個数を代入 107 size = len(ps[0]) 108 #7-2.変数[cs]に「#3需要変数(二値変数)を作成」の関数を代入 109 cs = make_matrix(ps, r) 110 #7-3.変数[prob]に集合被覆問題を解く命令を代入 111 prob = pulp.LpProblem('max-cover', sense = pulp.LpMaximize) 112 #7-4.変数[fs]に変数[size]に格納されている値を変数[i]に移行し,この問題で解く際に必要となる関数を作成 113 fs = [pulp.LpVariable('f{}'.format(i), lowBound=0, cat = 'Binary') for i in range(size)] 114 #7-5.変数[prob]にも目的関数を追加 115 prob += pulp.lpSum(fs) 116 #7-6.変数[cs]から変数[c]に制約条件を追加 117 for c in cs: 118 prob += pulp.lpDot(c, fs) >= fs[c] 119 #7-7.変数[s]に時間計測の命令を代入 120 s = time.time() 121 #7-8.変数[status]に集合被覆問題が解けたかどうかの確認を行う命令を代入 122 status = prob.solve() 123 #7-9.変数[status]の結果を表示 124 print('Status', pulp.LpStatus[status]) 125 #7-10.設置された資源回収物拠点の数を表示 126 print('z 施設数:', prob.objective.value()) 127 #7-11.集合被覆問題の回答処理に掛かった時間を表示 128 print('処理時間', time.time() - s) 129 #7-12.関数[draw(ps, fs, r)]を実行 130 draw(ps, fs, r) 131 132#許容領域の半径 133r = 0.03 134#資源回収物拠点の個数 135sigen = 10 136#乱数上限 137upper_x = 137.758 138upper_y = 34.778 139#実行 140solver_set(make_data_si(sigen, upper_x, upper_y), r)

試したこと・調べたこと

  • teratailやGoogle等で検索した
  • ソースコードを自分なりに変更した
  • 知人に聞いた
  • その他
上記の詳細・結果

google上で「数理最適化 最大被覆問題 Python」と検索し、最大被覆問題を取り扱うPythonのプログラムを参照し、変更を加えた。
下記が変更したコードの部分
def solver_set(ps, r, sigen):
#7-1.変数[size]に資源回収物拠点のx座標値の個数を代入
size = len(ps[0])
#7-2.変数[cs]に「#3需要変数(二値変数)を作成」の関数を代入
cs = make_matrix(ps, r)
#7-3.変数[prob]に集合被覆問題を解く命令を代入
prob = pulp.LpProblem('max-cover', sense = pulp.LpMaximize)
#7-4.変数[fs]に変数[size]に格納されている値を変数[i]に移行し,この問題で解く際に必要となる関数を作成
fs = [pulp.LpVariable('f{}'.format(i), lowBound=0, cat = 'Binary') for i in range(size)]
xs = [pulp.LpVariable('x{}'.format(i), lowBound=0, cat = 'Binary') for i in range(size)]
prob += pulp.lpSum(xs) == sigen
#7-6.変数[cs]から変数[c]に制約条件を追加
for i in range(size):
prob += pulp.lpDot(cs[i], fs) >= xs[i]
#7-7.変数[s]に時間計測の命令を代入
s = time.time()
#7-8.変数[status]に集合被覆問題が解けたかどうかの確認を行う命令を代入
status = prob.solve()
#7-9.変数[status]の結果を表示
print('Status', pulp.LpStatus[status])
#7-10.設置された資源回収物拠点の数を表示
print('z 施設数:', prob.objective.value())
#7-11.集合被覆問題の回答処理に掛かった時間を表示
print('処理時間', time.time() - s)
#7-12.関数[draw(ps, fs, r)]を実行
draw(ps, fs, r)

補足

PythonのVersionは2023.22.1であり、ソルバーにはpulpを使用しています。

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

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

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

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

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

ikedas

2024/04/09 13:27

参考までに聞きたいのですが、この問題を解こうと思った動機は何かありますか。
退会済みユーザー

退会済みユーザー

2024/04/09 14:22

卒業研究で施設の最適配置に関連するテーマに設定していて、その最適配置を導出する方法として最大被覆問題を選んだのが動機です。
ikedas

2024/04/09 14:46 編集

そうですか。 大学には学術研究と教育の機能がありますから、卒業研究をサポートすることもその機能の一部なんですよね。 卒業研究も含め大学でやる学習・研究の相談は、大学で然るべき対応をしているはずですから、そちらを頼ってください。 たとえば研究室の教員や院生などの先輩に相談するとか、同級生とディスカッションするとかです。そう言った支援を受けて当然なだけのお金をあなたは大学に払っているはずです。 大学で学んでいる方なら、当サイトに質問しにこないでください。そうではなく、大学で学んだ成果を活かして近い将来に当サイトで質問に回答できるようになってください。
fana

2024/04/10 02:33

質問するにしても,もう少し話を整理した方が良いのでは. 例えば現状が > 入力した値の数だけの点がランダムに配置されてしまう という結果になるのは何故なのか? という話とか, あとは,この問題の何が難しい箇所なのか? みたいな話とか. (緯度と経度 という話だとこれを単純な2次元平面上の点としては扱えない,みたいな部分が難しいのかな?)
ikedas

2024/04/10 03:02

いや、質問の内容が云々以前に、卒研の「正解」を質問しに来ているのがそもそもおかしい。卒業研究がなんなのかわかってないんじゃないですか。
bsdfan

2024/04/10 08:27

コード全体をみていませんが、何を最大化したいのか、そのときの制約がなにか、あたりがちゃんと設定できていないように見えます。
ikedas

2024/04/10 09:46

> 何を最大化したいのか 単に「最大被覆問題」という問題の類型があるというだけでしょう。ググると、「COVID-19のワクチン接種施設 (複数) を自治体内のどこに配置すれば、一定の距離内で利用可能な世帯の数を最大化できるか」みたいな例が出てきます。 質問の日本語も突っ込みどころ満点ですが、大学の卒業研究を丸投げしてくるとはteratail史上最大級の丸投げ質問ではないでしょうか。
bsdfan

2024/04/10 11:23

今のコードではfsの合計を最大化しようとしていますが、おそらく最大化したいものはそれじゃないはず。それに続く制約条件も何を意味しているのかちょっと不明です。 (さすがに、このコードを完成させるだけの内容が卒業研究のすべてだとは思いたくないのでコメントしています。が、マルチポストっぽいのでこれ以上は控えます)
ikedas

2024/04/10 21:25 編集

元にしたと見られるネット上のコードを見ると、距離の合計を最大化するという意図で正しいようです (距離を直線で測っているとかみんな砂漠か草原にテントでも張って住んでるのかという単純化されたモデルなので、あまり深く考えてもしかたがないのかと。資源回収拠点の稼働率の指標としてはありかもしれない)。あと、制約条件のコードはなくてもいいみたいな説明もある。 マルチポストのもう一方の投稿を見ると「いつも同じ結果しか出ない」というのが質問者さんが抱えている問題のようですが、そうなるように改変してあるコードなのだから当たり前ですね。 現状の延長に、質問者さんの得たい結果が出るコードはないと思います。というかそれを考えるのが研究でしょ。
guest

回答1

0

これは回答ではありませんが、後述する理由からあえて投稿しています。


全ての集合をカバーするような実行結果を算出するためにどうすればいいか知りたい。

それは質問者さんの卒業研究のテーマそのものではないですか。それを考えるのはあなたです。

ところで、ご質問の問題は卒業研究の対象なのですよね。 あなたが行うのは「研究」であって、その成果をもってあなたは卒業資格を得るのですよね。

「研究」とは、「物事を深く考えたり、詳しく調べたりして、真理、理論、事実などを明らかにすること。」(日本国語大辞典) です。特に学術研究の場合、調査や実験の結果を解釈し考察した結果、今までになかった独自の知見をもたらすような営為を指します。

「研究」は今までの勉強と違って、正解があることが最初からわかっていてそれを当てれば合格、なのではありません。あなた自身が、他の人がまだ発見していない新たな真理、理論、事実を提示できなければ「研究」とは言えません。

逆にいうと、他の人の発見を自分の研究として発表したらそれは「盗用」となります。

どの大学・学術機関にも「研究者倫理規程」のようなものがあります。あなたも「研究」をするのですから、当然このような倫理規程の対象となります。その規定の中で、盗用は最も厳しく禁じられている行為の一つです。

さて、今後この質問に回答がついたとします。そしてあなたがその回答の内容を使って卒業研究の論文を書いたとします。論文が受理された後に学校関係者の誰かがこちらの回答を見つけ、内容が一致すると判断されれば、それは「盗用」と認定される可能性があります。——たとえ回答を投稿した人が「自分の回答は自由に使ってもらって構わない」と思っていたとしても関係ありません。内容が一致するのなら客観的に見てそれは「盗用」です。

盗用と認定されれば、基本的にはその論文は撤回されます。卒業研究という場合、大抵はその研究の成果が学位授与をはじめとした卒業資格の条件になりますから、卒業も取り消されるかもしれないということです。

ですので、もしもこの質問に回答がついたら、質問者さんはその内容を自分の卒業研究に取り入れないように細心の注意を払うべきでしょう。このことを言いたいためにこの投稿をしました。


当サイトでも、学校の授業での課題を質問しにくる学生が残念ながらなくならないのですが (勉強は学校でやるべきですし、個人的にはカンニングとみなされるおそれが高いと考えるので、本人自身のためにもやめてほしいです)、研究となるとそれより格段に慎重さが要求されます。これから「研究」を始める以上、あなたも研究者の仲間入りをするのであり、研究倫理を守らなければなりません。

研究倫理について詳しいことは、あなたが指導を受けている教員の方に聞いてください。

あと、もう一つ指摘しておきます。文章でもソースコードでも、他人の書いたものを参考にしたのなら出所を明記するのが約束です。学校でそう指導しているはずですよ。

投稿2024/04/10 11:27

ikedas

総合スコア4413

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

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

fana

2024/04/11 01:25

まぁ訊き方ですよね. 質問内容が研究としての 独自性/新規性/etc 的な主張部分そのものに関わるようだとNGでしょうけど, そうでない( 例えば,結局のところ質問内容が pulp とかいう何かの使い方でしかない,みたいな)場合であれば問題ない,みたいな. 本件の問題を pulp とかいう何かを用いて解くことが研究と言えるのか? すなわちそこに 独自性/新規性/etc が存在するのか否か,私には分かりませんが…… 本件で示されている問題は「最大被覆問題」とかいうジャンルの単なるシンプルな例題の1つでしかなくて,研究内容はもっと先のところにあるのではないだろうか…? という気もします. いずれにせよ,教員etc に質問することを考えるべきであろうと思いますが.
ikedas

2024/04/11 03:13

> 研究内容はもっと先のところにあるのではないだろうか そうだと思いますよ。「PuLPを使って問題を解きました」だけでは研究にならないので。では親身になって相談に乗ってやればいいのかというと、それで味を占められては困る。 ネットで得た半端な知識をもとに適当に書き飛ばした卒業研究なんて、通してもらえるわけがない。だからさっさと学校に戻ってほしいです。というか、まず学校で勉強のしかたを勉強してくれと思う。 でも、「なんか叱られたみたいだけどアカウント消して行方をくらませばいいや」と思ってるんなら、見通しは暗いかもしれませんね。まあ私の知ったことではないですが。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.45%

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

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

質問する

関連した質問