Petitverse

コミュニティアイコン プチコン 非公式コミュニティ トピック

アバター
こういち ◆ou0jbJnEJ0Kb
2019/10/2 12:44
質問
ダイクストラ法,A*,dfs,bfsなどについて
はるさんや初心者さんに便乗してA*の探索プログラムを書こうとしてるのですが、分からないことが2つほどあります。
(なお、頂点の個数を|V|,辺の個数を|E|とします。)

(1)ダイクストラ法やA*,dfsやbfsでは、探索する予定の頂点を記録するために、ヒープやスタック、キューなどに頂点の情報を格納しますが、最悪のケースではどれだけの要素が必要でしょうか。

(2)ダイクストラ法では、一度頂点が探索され、スタートからの距離が求まれば、その後より短い距離で上書きされることはないと思っているのですが、それは正しいでしょうか。また、ダイクストラでそれが成立したとして、A*でも同じことは成立しますか。
通報

コメント

アバター
こういち 2019/10/2 23:11 ◆ou0jbJnEJ0Kb
(1)に関しては、|V|あればいいということでもないような気がする。
例えば、|V|要素確保したとすると、完全グラフのようなグラフでは2つ目の頂点でOut of rangeが出る。

|E|あればいいのか|V|+|E|なのか|V|^2必要なのか…
アバター
初心者 2019/10/3 7:53 ◆ULvuffpmw1rp
(1)最悪のケースは計算わかんないけど、アルゴリズムを何回も実行させてその中で要素数が一番多かったやつを最大の要素数とすると良いんじゃない？

(2)
より短いのは出てこないと思うよ。等しいのはあるかもだけど。
アバター
こういち 2019/10/3 9:53 ◆ou0jbJnEJ0Kb
ちょっと考察。
(1)は(2)が成立した場合、|E|で済むような気がする。
(2)に関しては、ダイクストラやbfsでは成り立つ。A*に関しては反例を見つけたかもしれないので、後に検証してみる。dfsでは成立しない。

つまり、bfsやダイクストラではメモリは|E|あれば十分。
アバター
こういち 2019/10/3 10:00 ◆ou0jbJnEJ0Kb
初心者さん
回答ありがとうございます。
アルゴリズムを何度も実行するのは大変そうなので、とりあえず要素が足りなくなったら増やしていくことにします。
アバター
こういち 2019/10/3 10:11 ネタバレ ◆ou0jbJnEJ0Kb
このコメントはネタバレを含んでいます。
アバター
こういち 2019/10/3 10:28 ネタバレ ◆ou0jbJnEJ0Kb
このコメントはネタバレを含んでいます。
アバター
こういち 2019/10/12 22:07 ◆ou0jbJnEJ0Kb
あれっ？
もしかしてA*、メモリを無限に消費する？

結論:ダイクストラ強し。

コメントを書く

  • こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
  • プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
  • こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
  • ユーザー登録なしで書き込みができます
  • 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
  • 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
  • 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります

- WEB PATIO -