ベストアンサー

A*アルゴリズムとダイクストラ法について

2010/12/09 21:16

A*アルゴリズムとダイクストラ法について質問です。 (1)A*アルゴリズムは万能のように思えるのですが、どのようなデメリットがありますか？ (2)ダイクストラ法がA*より優れている点はありますか？ A*アルゴリズムを調べてみたのですが主なデメリットは見つけられなかったので疑問に思いました。回答よろしくお願いします

aroha_2010
お礼率36% (4/11)

数学・算数
回答数1
ありがとう数2

みんなの回答 （1）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

noname#221368

2010/12/10 11:30 回答No.1

　先日久しぶりに、ダイクストラ法のサブルーティンを書いたばかりです^^。　A*に関しては、　　http://www.weblio.jp/content/A*%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 を参考にしています。　ダイクストラさんのオリジナルでは、探索パスを現時点での既知の最最短経路に絞る事で、不要に遠い点への探索を避け、効率化をはかっていると思います。特にそういう事をせず、現時点で行ける点を全て探索し、最小コストのパスを選んでも、ダイクストラ法は成立するはずです。これを勝手に、基本ダイクストラと呼んでます（こっちの方が、論理がわかりやすいので）。　ダイクストラ法は、A*のヒューリスティック関数h*を、現時点での既知の最最短経路評価が最適と仮定するのと、等価と思えます。h*をどうやって推定するかをおいとけば、もっと最適なh*があるなら、不要に遠い点をより無視できて、もっと探索効率は上がるはずです。というわけで効率は、　　基本ダイクストラ（最適化なし）＜ダイクストラ（暫定最適化）＜A*（もっと最適化）となり、理屈の上では、A*のデメリットはない気がします。　とすれば後は、実際上の問題です。 (1)単純な最短路検索の場合　参考URLによれば、この場合、h*として2点間の直線距離でもとれば良いと書いてますので、是非A*という事になりますが、自分は何故かダイクストラ（オリジナルの）をとりたいです。理由は次で述べます。 (2)時間最短経路の場合　例えば道路ネットワークを考えた場合、距離最短に従ってドライバーの皆さんがある道路に集中すると、その道路は混んで渋滞し、走行速度が下がります。ご存知かも知れませんが、幹線道路には設計交通量というのがあり、それを越えた場合の走行速度降下曲線みたいなものまで用意されてます。　こういう場合は、時間最短です。この時、h*の推定はかなり鬱陶しい気がします（サブルーティンが数個増える！）。対して、ダイクストラを時間最短用にするのは、きわめて簡単です。というか、距離最短でも時間最短でも、そのまんまダイクストラが使えます。　自分はもともと土木系で、現在は、上流から下流までたった一人のApplicationプログラマーをやってますが（つまり、この部署はたった一人^^）、状況に応じて方法を切り替えるApplicationというのは、嫌です。コーディング量，Bugの量，テスト量，仕様書の文書量，メンテナンス量まで全部増加するからです。単純明解がいい～～！。 (3)対話型Application 　(1)と(2)の答えは、どんな方法を使っても一つです。そうでない場合は対話型になります。例えば「この道路を通ると、何故か速いんだよね～」といった経験事実がある場合です。これh*に使えますよね？。しかも(1)と(2)のような紋切り型の解でなく、現場の状況をより反映した応答を出せます。この時は、A*だと思います。