No.1ベストアンサー
- 回答日時:
先日久しぶりに、ダイクストラ法のサブルーティンを書いたばかりです^^。
A*に関しては、
http://www.weblio.jp/content/A*%E3%82%A2%E3%83%A …
を参考にしています。
ダイクストラさんのオリジナルでは、探索パスを現時点での既知の最最短経路に絞る事で、不要に遠い点への探索を避け、効率化をはかっていると思います。特にそういう事をせず、現時点で行ける点を全て探索し、最小コストのパスを選んでも、ダイクストラ法は成立するはずです。これを勝手に、基本ダイクストラと呼んでます(こっちの方が、論理がわかりやすいので)。
ダイクストラ法は、A*のヒューリスティック関数h*を、現時点での既知の最最短経路評価が最適と仮定するのと、等価と思えます。h*をどうやって推定するかをおいとけば、もっと最適なh*があるなら、不要に遠い点をより無視できて、もっと探索効率は上がるはずです。というわけで効率は、
基本ダイクストラ(最適化なし)<ダイクストラ(暫定最適化)<A*(もっと最適化)
となり、理屈の上では、A*のデメリットはない気がします。
とすれば後は、実際上の問題です。
(1)単純な最短路検索の場合
参考URLによれば、この場合、h*として2点間の直線距離でもとれば良いと書いてますので、是非A*という事になりますが、自分は何故かダイクストラ(オリジナルの)をとりたいです。理由は次で述べます。
(2)時間最短経路の場合
例えば道路ネットワークを考えた場合、距離最短に従ってドライバーの皆さんがある道路に集中すると、その道路は混んで渋滞し、走行速度が下がります。ご存知かも知れませんが、幹線道路には設計交通量というのがあり、それを越えた場合の走行速度降下曲線みたいなものまで用意されてます。
こういう場合は、時間最短です。この時、h*の推定はかなり鬱陶しい気がします(サブルーティンが数個増える!)。対して、ダイクストラを時間最短用にするのは、きわめて簡単です。というか、距離最短でも時間最短でも、そのまんまダイクストラが使えます。
自分はもともと土木系で、現在は、上流から下流までたった一人のApplicationプログラマーをやってますが(つまり、この部署はたった一人^^)、状況に応じて方法を切り替えるApplicationというのは、嫌です。コーディング量,Bugの量,テスト量,仕様書の文書量,メンテナンス量まで全部増加するからです。単純明解がいい~~!。
(3)対話型Application
(1)と(2)の答えは、どんな方法を使っても一つです。そうでない場合は対話型になります。例えば「この道路を通ると、何故か速いんだよね~」といった経験事実がある場合です。これh*に使えますよね?。しかも(1)と(2)のような紋切り型の解でなく、現場の状況をより反映した応答を出せます。この時は、A*だと思います。
参考URL:http://www.weblio.jp/content/A*%E3%82%A2%E3%83%A …
この回答へのお礼
お礼日時:2010/12/10 17:39
理屈上ではA*にはデメリットはないのですね
A*の粗さがしをしていたので少々残念です。
回答ありがとうございました!
詳しい回答で大変参考になりました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) プログラミング能力とアルゴリズム能力って違うのでしょうか? プログラミングの能力の一部にアルゴリズム 10 2023/03/31 14:34
- その他(プログラミング・Web制作) プログラミングの能力とアルゴリズムの能力は別物だと言われたのですが、これは本当ですか? プログラミン 1 2023/03/09 02:37
- ビデオカード・サウンドカード 1つのマザボでAMD&NVIDIAを同時使用できますか? 3 2022/04/22 14:36
- 数学 M種類の部品からN種類の部品を抽出する効率的なアルゴリズム 2 2022/04/22 16:51
- 教えて!goo 【回答が書きにくいのはなぜ】投稿内容に不適切な表現など・(中略)・投稿内容の修正をお願いいたします 9 2023/05/09 08:41
- 計算機科学 アルゴリズムについて 1 2023/01/01 19:43
- その他(プログラミング・Web制作) アルゴリズムってプログラミング以外にも使えますか? 4 2022/04/16 18:32
- その他(プログラミング・Web制作) プログラミングスクールについて 5 2022/05/12 23:51
- 情報処理技術者・Microsoft認定資格 基本情報技術者試験について知りたい! こんにちは! 今年基本情報技術者試験を受験するつもりです。 今 2 2023/07/17 21:23
- その他(就職・転職・働き方) 鉄道会社の採用で上手くオタ排除が機能してるように思えますが、 1 2022/05/23 10:29
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
彼女とハグをする時胸は当たる...
-
Excelについての質問です。 2点...
-
話す時に顔を必要以上に近づける人
-
4kmって例えばどこからどこまで...
-
私は学校で4人グループです。...
-
綺麗すぎて同性から距離を置か...
-
里は実際には何キロなのか
-
岐阜から東京まで距離はどのく...
-
|-5| + |2| っていう式の計算を...
-
CRZの航続可能距離の表示が切り...
-
A*アルゴリズムとダイクストラ...
-
絶対値についてです |a+b|^2 ...
-
負の距離
-
距離が離れると小さくなる計算...
-
台形の中に平行線を引いた、そ...
-
Excelで角度を求めたい・・・
-
友達(同性)と並んで歩く時、並...
-
「点F(0,1)からの距離と、直線y...
-
仲のいい既婚女性 自分(既婚者)...
-
正12面体の中心から頂点までの...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
彼女とハグをする時胸は当たる...
-
Excelについての質問です。 2点...
-
話す時に顔を必要以上に近づける人
-
私は学校で4人グループです。...
-
|-5| + |2| っていう式の計算を...
-
綺麗すぎて同性から距離を置か...
-
4kmって例えばどこからどこまで...
-
ACCESS VBAの実行時エラーなん...
-
絶対値についてです |a+b|^2 ...
-
いちおう元彼に解いてもらった...
-
距離を置く意味 距離を置いてお...
-
嫌われた人に距離を置こうと思...
-
4人グループにハブられてる気が...
-
岐阜から東京まで距離はどのく...
-
射程距離
-
里は実際には何キロなのか
-
排水管勾配
-
物理的に距離が近い男性って何...
-
クロネコヤマトに伝票番号で問...
-
Twitterで知り合い、直接お会い...
おすすめ情報