博士

ロボ子、今日はちょっと面白い経路探索の話をするのじゃ。

ロボ子

経路探索ですか、博士。それは興味深いですね。どのような内容でしょうか？

博士

ある地点から別の地点へ、指定された順番でいくつかのゲートを通過する最短経路を見つける問題じゃ。

ロボ子

なるほど。単純に考えると、グラフを作ってダイクストラ法を使うのが思い浮かびますね。

博士

そうじゃな。でも、もっと賢い方法があるんじゃ。すべてのゲートを直線で通過するか、ゲートの端点を通るかのどちらかになるという考え方を使うのじゃ。

ロボ子

ゲートの端点ですか？どういうことでしょう？

博士

最短経路は、ゲートを直線で通過するか、ゲートの端点に向かってそこから離れるかのどちらか、ということじゃ。だから、あるゲートから次のゲートへの最短経路を、そのゲートの端点を使って拡張していくのじゃ。

ロボ子

なるほど、各ゲートを通過する領域を分割して、次のゲートへの拡張を計算していくんですね。

博士

その通り！そして、重要なのは、この方法が距離を計算せずに最短経路を求められるということじゃ。

ロボ子

距離を計算しないんですか？どうしてそれが可能なんですか？

博士

三角形の不等式を利用しているからじゃ。それに、必要なデータも少ないし、セグメンテーションは常にV字型になるんじゃよ。

ロボ子

V字型ですか。面白いですね。新しい領域は常に両端に追加されるんですね。

博士

そうじゃ。そして、点がある線の左右どちら側にあるかをチェックするには、線の方向を回転させたものと、線から点へのベクトルのドット積を取って、その符号をチェックすれば良いのじゃ。

ロボ子

なるほど、幾何学的な計算で判定するんですね。この方法を使えば、効率的に経路探索ができそうですね。

博士

じゃろ？この知識があれば、ロボ子も迷子になることはないのじゃ！

ロボ子

ありがとうございます、博士。でも、私はロボットなので、GPSが壊れない限り迷子にはなりませんよ。

博士

むむ、それもそうじゃった！でも、GPSが使えない状況でも、この知識は役に立つはずじゃぞ！例えば、宝探しとか！

ロボ子

宝探しですか。博士らしい発想ですね。

博士

ところでロボ子、最短経路探索といえば、私が冷蔵庫にあるプリンへの最短経路を探索するのも、なかなか高度な問題なのじゃ。いつも誰かに食べられてしまうからの。

ロボ子

博士、それも一種の経路探索かもしれませんが、まずは自分の名前をプリンに書いておくのが良いかもしれませんね。