inarizuuuushi https://blog.hatena.ne.jp/inarizuuuushi/ Sabrou-mal サブロウ丸 https://inarizuuuushi.hatenablog.com/ 数学 上記のグラフのstartからgoalまでの最短路を求めたいとします。 (グラフの枝の重みは枝の長さ) 直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、それをどう厳密に表現するか?という話になります。 今回は楕円を用いてそのような最短路に絶対含まれることがない枝を探索します。 まず、startからgoalまでの道を一つ見つけます。 図中緑色の道を見つけたとします。(このとき、このパスが最短路である必要はありません) 次に長軸が「startとgoalを通り、長さが上で見つけたパス長」で、startとgoalが… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finarizuuuushi.hatenablog.com%2Fentry%2F2017%2F06%2F23%2F071342" title="最短路計算における、楕円を用いたグラフの枝刈り - Sabrou-mal サブロウ丸" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20170605/20170605115347.png Hatena Blog https://hatena.blog 2017-06-23 07:13:42 rich https://inarizuuuushi.hatenablog.com/entry/2017/06/23/071342 1.0 100%