サブロウ丸

大学生です

最短路計算における、楕円を用いたグラフの枝刈り

f:id:inarizuuuushi:20170605115347p:plain:w600

上記のグラフのstartからgoalまでの最短路を求めたいとします。
(グラフの枝の重みは枝の長さ)
直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、
それをどう厳密に表現するか?という話になります。

今回は楕円を用いてそのような最短路に絶対含まれることがない枝を探索します。


まず、startからgoalまでの道を一つ見つけます。
f:id:inarizuuuushi:20170605121338p:plain:w500
図中緑色の道を見つけたとします。(このとき、このパスが最短路である必要な当然ありません)


次に長軸が「startとgoalを通り、長さが上で見つけたパス長」で、startとgoalが焦点であるような楕円を考えます。
f:id:inarizuuuushi:20170605122537p:plain:w500
このとき、startとgoalを結ぶ最短路はこの楕円の中に含まれていることがわかります。
(理由は後ほど)


なので、この楕円の外、もしくはこの楕円を横切るような点や枝は最短路には含まれません。
(例えば下図、バツ印)
f:id:inarizuuuushi:20170605123034p:plain:w500


そのような点、枝を取り除くと、以下のようにグラフを小さくすることができます。
f:id:inarizuuuushi:20170605134424p:plain:w500

上の例では、それほど削れていませんが、グラフが大きくなればなるほど削れる枝が多くなり、より効率的に最短路を探索できることになります。

さて、ではなぜstartとgoalを結ぶ最短路はこの楕円の中に含まれていると言えるのかというと、これは楕円の性質に依るものです。
楕円の性質(というよりはむしろ定義)により「楕円上の任意の点について、二つの焦点との距離の和は一定で、それは長軸の長さと等しい」ということが成り立ちます。

よって、この場合については、楕円上の任意の点について、startとgoalとの距離の和は、最初に見つけてきたパスの長さに等しいということが分かります。
これより、楕円の外に出るようなstart-goal間の道については、最初に見つけてきたパスの長さよりも確実に長くなることになるので、start-goal間の最短経路は必ず楕円の中に含まれることが言えるのです。