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で質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
彼女とハグをする時胸は当たる...
-
Excelについての質問です。 2点...
-
私は学校で4人グループです。...
-
話す時に顔を必要以上に近づける人
-
ACCESS VBAの実行時エラーなん...
-
里は実際には何キロなのか
-
放す と 離す
-
200V 30A IHクッキ...
-
接道と接面距離の違いについて
-
|-5| + |2| っていう式の計算を...
-
4kmって例えばどこからどこまで...
-
距離を置く意味 距離を置いてお...
-
距離が離れると小さくなる計算...
-
アメリカとフランスはどちらが...
-
クロネコヤマトに伝票番号で問...
-
嫌われた人に距離を置こうと思...
-
TNT(トリニトロトルエン)1...
-
負の距離
-
なぜ楕円の中心=焦点の中点とな...
-
綺麗すぎて同性から距離を置か...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
彼女とハグをする時胸は当たる...
-
Excelについての質問です。 2点...
-
話す時に顔を必要以上に近づける人
-
4kmって例えばどこからどこまで...
-
|-5| + |2| っていう式の計算を...
-
綺麗すぎて同性から距離を置か...
-
嫌われた人に距離を置こうと思...
-
私は学校で4人グループです。...
-
絶対値についてです |a+b|^2 ...
-
岐阜から東京まで距離はどのく...
-
距離を置く意味 距離を置いてお...
-
アメリカとフランスはどちらが...
-
里は実際には何キロなのか
-
ACCESS VBAの実行時エラーなん...
-
距離が離れると小さくなる計算...
-
日本海側に避難完了するまで何...
-
眼前有限距離とはなにかわかる...
-
友達(同性)と並んで歩く時、並...
-
クロネコヤマトに伝票番号で問...
-
今の時期特◯電車で他地域に行き...
おすすめ情報