こんにちは！しゅんです！
今回は最近傍探索を分割統治法で解いていきます！
最近傍探索はグラフ理論の用語で、ある点に最も近い点を見つけることです。
また分割統治法はそのままでは解くのが難しい問題をいくつかの小問題に分割して答えを求めて、最後にそれを表せて元の問題を解く方法です。
マージソートの記事でも分割統治法について触れているのでこちらの記事もぜひ読んでみてください！
それでは解説していきましょう！
普段はNBAのデータ分析をしたりしています。
ぜひこちらの記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
最近傍探索ってなに？
最近傍探索(Nearest neighbor)はある点に最も近い点を見つけることです。例えば下のグラフを見てみましょう。
点が色んなところに散らばっています。ここで赤い点について考えてみましょう。赤い点に最も近い点はすぐ右にある(5,3)の点ですね。
このようにある点に最も近い点を見つけることを最近傍探索と言います。
最近傍探索をするためには2つの点の距離を計算する必要がありますが、この記事ではマンハッタン距離を使おうと思います。
マンハッタン距離についてはこちらの記事で解説しています！
ザックリ解説するとマンハッタン距離は直線距離じゃなくて直角に曲げて求める距離です。
距離の計算で最もよく使われているのはおそらくユークリッド距離で、2つの点を直線で結んだ長さを求めます。
上の図でいうと左図がユークリッド距離で値は\(\sqrt2\)になり、右図がマンハッタン距離で値は2になります。
最近傍探索に分割統治法を適用してみる
分割統治法は問題をいくつかの小問題に分けて、それぞれで答えを見つけて最後にそれらをまとめるという方法です。
例えば最近傍探索に分割統治法を適用すると以下のようになります。
- グラフを左側と右側に分割する
- それぞれで最も近い点を見つける
- 2つを比べてより近い方を採用する
例えばさっきのグラフの例で言うと、下図のようにxが5.5より大きいか小さいかでグラフを分割することができます。
グラフ上の黒い点における最近傍点を見つけることを考えてみましょう。今回は説明のため、自身より北西にある点に限って考えていきます。つまり下図の緑色の範囲に属す点の中から最も近い点を見つけます。
まず赤側に属す点の中で最近傍点を探すと下図の点が最も近いことが分かります。
マンハッタン距離でどれくらい離れているかを計算すると5になります。
次に青側に属す点の中で最近傍点を探すと下図の点が最も近いことが分かります。
マンハッタン距離でどれくらい離れているかを計算すると3になります。この二つが黒点の最近傍点の候補としてあがりました。
この2つの中で最も近傍なのは青側の方の点のため、黒点における最近傍点はこの青点であると言う風に求めることができました。
自分が赤側の点だったとしても最近傍点は青側ということもあるので、必ず最後に比較する必要があります。
なぜこのように分割した方が良いのかとかこれをアルゴリズムで表すにはどうすれば良いかなど色々興味深いことがありますが、かなり難しい話になってしまうので割愛します。
気になる人はRectilinear Minimum Spanning TreeとかNearest Neighborとかで調べてみてください！
おわりに
いかがでしたでしょうか。
今回の記事では最近傍探索について解説していきました。
ぼくが勉強している経営工学でも結構登場する重要な概念です。グラフ理論は難しいですが、勉強すると結構楽しい学問だと思います。
今後もこのような経営工学に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
