-
masashinakata
- 975
- 1
- 0
- 0
-
- いいね！0
江崎貴裕@『データ可視化学』kindle発売！
@tkEzaki
巡回セールスマン問題の最短経路長は、もしノードの位置が一様ランダムに決まると仮定すると、その領域の面積とノード数の平方根に比例する式で近似できるということが知られているらしいのだが、試しに計算してみたら思ったよりいい近似で驚いた。 pic.twitter.com/fWc7VrJhmw
2020-08-15 19:17:50
拡大
そすうぽよ
@_primenumber
ユークリッド平面上に頂点を一様ランダムに置き、各頂点間に対してその最短距離の辺を張り、巡回セールスマン問題を解いたときの答え、がその領域の面積(全頂点の凸包の面積)、およびグラフの頂点数、の平方根に比例する関数で近似できるってこと…？マジ？ twitter.com/tkEzaki/status…
2020-08-16 04:25:13
江崎貴裕@『データ可視化学』kindle発売！
@tkEzaki
@_primenumber 曖昧な書き方をしてしまいましたが、凸包の面積ではなくて、面積Aの領域（例えば正方形）を最初に用意して、その中の点をN個ランダムに選ぶ、の意味でした。
2020-08-16 08:22:11
江崎貴裕@『データ可視化学』kindle発売！
@tkEzaki
曖昧な書き方でしたが、「その領域の面積」というのはランダムに点を生成する領域全体の面積のことで、最短経路の中の面積ではないのでご注意下さい。後で詳しく補足します。
2020-08-16 09:29:05